Montgomery reduction: Difference between revisions
→{{header|Quackery}}: multiple improvements
(Added Quackery.) |
(→{{header|Quackery}}: multiple improvements) |
||
Line 1,476:
=={{header|Quackery}}==
{{trans|Factor}}
[ dup while▼
dip 1+▼
1 >> again ]▼
<code>**mod</code> is defined at [[Modular exponentiation#Quackery]].
[ dup 1 & if▼
[ over + ]▼
1 >> ]▼
swap mod ] is monred ( n n --> n )▼
<syntaxhighlight lang="Quackery"> [ 0 swap [ dup while dip 1+ 1 >> again ] drop ] is bits ( n --> n )
[ 1 & ] is odd ( n --> b )
▲ [ over bits times [ dup odd if [ over + ] 1 >> ] swap mod ] is monred ( n n --> n )
[ 750791094644726559640638407699 ] is m ( --> n )
[ 323165824550862327179367294465482435542970161392400401329100 ] is t1 ( --> n )
[ 440160025148131680164261562101 ] is r1 ( --> n )
[ 435362628198191204145287283255 ] is r2 ( --> n )
[ 540019781128412936473322405310 ] is x1 ( --> n )
[ 515692107665463680305819378593 ] is x2 ( --> n )
[ unrot dip
over t1 rot / monred temp put
▲ [ dup 0 != while
m swap monred
temp put ]
dip [ dup * m swap monred ]
▲ 1 >> again ]
2drop temp take monred ] is **mon ( n n n --> n )
say "Original x1: " x1 echo cr
say "Recovered from r1: " m r1 monred echo cr
cr
say "Original x2: " x2 echo cr
say "Recovered from r2: " m r2 monred echo cr
cr
say "Montgomery computation of x1^x2 mod m: " x1 x2 m **mon echo cr
say "Modular exponentiation of x1^x2 mod m: " x1 x2 m **mod echo cr
</syntaxhighlight>
{{out}}
<pre>
Recovered from r1: 540019781128412936473322405310
Original x2: 515692107665463680305819378593
Recovered from r2: 515692107665463680305819378593
Montgomery computation of x1^x2 mod m: 151232511393500655853002423778
Modular exponentiation of x1^x2 mod m: 151232511393500655853002423778</pre>
=={{header|Racket}}==
| |||