Montgomery reduction: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Thundergnat (talk | contribs) m (šyntax highlighting fixup automation) |
m (→{{header|Wren}}: Minor tidy) |
||
| (6 intermediate revisions by 3 users not shown) | |||
Line 27:
F (m)
.m = m
.n =
.rrm = (BigInt(2) ^ (.n * 2)) % m
Line 70:
V base = mont.reduce(x1 * mont.rrm)
V ex = x2
L
I (ex % 2) == 1
prod = mont.reduce(prod * base)
Line 1,390:
=={{header|Python}}==
{{todo|python|Update the output}}
{{trans|D}}
<syntaxhighlight lang="python">
class Montgomery:
BASE = 2
Line 1,422 ⟶ 1,424:
r = 1 << mont.n
print(▼
f"n: {mont.n}\n"
f"m: {mont.m}\n"
f"t1: {t1}\n"
f"t2: {t2}\n"
f"r1: {r1}\n"
f"r2: {r2}\n"
▲print
)
print
prod = mont.reduce(mont.rrm)
base = mont.reduce(x1 * mont.rrm)
Line 1,445 ⟶ 1,448:
exp = exp >> 1
base = mont.reduce(base * base)
print
print
{{out}}
<pre>
b : 2
n : 100
r : 1267650600228229401496703205376
Line 1,467 ⟶ 1,471:
Alternate computation of x1 ^ x2 mod m :
151232511393500655853002423778
</pre>
=={{header|Quackery}}==
{{trans|Factor}}
<code>**mod</code> is defined at [[Modular exponentiation#Quackery]].
<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
[ dip dup
over t1 rot / monred temp put
t1 monred ]
[ dup 0 != while
dup odd if
[ over temp take *
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>Original x1: 540019781128412936473322405310
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}}==
Line 1,759 ⟶ 1,818:
{{trans|Kotlin}}
{{libheader|Wren-big}}
<syntaxhighlight lang="
class Montgomery {
| |||