Montgomery reduction: Difference between revisions
Add Factor
(Added Wren) |
(Add Factor) |
||
Line 480:
Alternate computation of x1 ^ x2 mod m :
151232511393500655853002423778</pre>
=={{header|Factor}}==
{{trans|Sidef}}
{{works with|Factor|0.99 2020-08-14}}
<lang factor>USING: io kernel locals math math.bitwise math.functions
prettyprint ;
: montgomery-reduce ( m a -- n )
over bit-length [ dup odd? [ over + ] when 2/ ] times
swap mod ;
CONSTANT: m 750791094644726559640638407699
CONSTANT: t1 323165824550862327179367294465482435542970161392400401329100
CONSTANT: r1 440160025148131680164261562101
CONSTANT: r2 435362628198191204145287283255
CONSTANT: x1 540019781128412936473322405310
CONSTANT: x2 515692107665463680305819378593
"Original x1: " write x1 .
"Recovered from r1: " write m r1 montgomery-reduce .
"Original x2: " write x2 .
"Recovered from r2: " write m r2 montgomery-reduce .
nl "Montgomery computation of x1^x2 mod m: " write
[let
m t1 x1 / montgomery-reduce :> prod!
m t1 montgomery-reduce :> base!
x2 :> exponent!
[ exponent zero? ] [
exponent odd?
[ m prod base * montgomery-reduce prod! ] when
m base sq montgomery-reduce base! exponent 2/ exponent!
] until
m prod montgomery-reduce .
"Library-based computation of x1^x2 mod m: " write
x1 x2 m ^mod .
]</lang>
{{out}}
<pre>
Original x1: 540019781128412936473322405310
Recovered from r1: 540019781128412936473322405310
Original x2: 515692107665463680305819378593
Recovered from r2: 515692107665463680305819378593
Montgomery computation of x1^x2 mod m: 151232511393500655853002423778
Library-based computation of x1^x2 mod m: 151232511393500655853002423778
</pre>
=={{header|Go}}==
| |||