Rosetta Code

Montgomery reduction: Difference between revisions

Page Discussion

Montgomery reduction (view source)

Revision as of 03:36, 18 October 2023

34 bytes added ,  7 months ago
→‎Python
m (→‎{{header|11l}}: bits:length())
imported>Katsumi
Line 1,390:
 
=={{header|Python}}==
{{todo|python|Update the output}}
{{trans|D}}
<syntaxhighlight lang="python">class Montgomery:
class Montgomery:
BASE = 2
 
Line 1,422 ⟶ 1,424:
r = 1 << mont.n
 
print(▼
print f"b : ", {Montgomery.BASE}\n"
print "n : ", mont.n
f"n: {mont.n}\n"
print "r : ", r
print "m : f",r: mont.m{r}\n"
f"m: {mont.m}\n"
print "t1: ", t1
f"t1: {t1}\n"
print "t2: ", t2
f"t2: {t2}\n"
print "r1: ", r1
f"r1: {r1}\n"
print "r2: ", r2
f"r2: {r2}\n"
▲print
print f"Original x1 :", {x1}\n"
print f"Recovered from r1 :", {mont.reduce(r1)}\n"
print f"Original x2 :", {x2}\n"
print f"Recovered from r2 :", {mont.reduce(r2)}\n"
)
 
print ("\nMontgomeryMontgomery computation of x1 ^ x2 mod m:")
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 (mont.reduce(prod))
print (f"\nAlternate computation of x1 ^ x2 mod m : {pow(x1, x2, m)}")
print pow(x1, x2, m)</syntaxhighlight>
{{out}}
<pre>b : 2
b : 2
n : 100
r : 1267650600228229401496703205376
Line 1,467 ⟶ 1,471:
 
Alternate computation of x1 ^ x2 mod m :
151232511393500655853002423778</pre>
</pre>
 
=={{header|Racket}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/351377"