Montgomery reduction: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) m (→{{header|11l}}: bits:length()) |
imported>Katsumi (→Python) |
||
| Line 1,390: | Line 1,390: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{todo|python|Update the output}} |
|||
{{trans|D}} |
{{trans|D}} |
||
<syntaxhighlight lang="python"> |
<syntaxhighlight lang="python"> |
||
class Montgomery: |
|||
BASE = 2 |
BASE = 2 |
||
| Line 1,422: | Line 1,424: | ||
r = 1 << mont.n |
r = 1 << mont.n |
||
| ⚫ | |||
f"b: {Montgomery.BASE}\n" |
|||
print "n : ", mont.n |
|||
f"n: {mont.n}\n" |
|||
print "r : ", r |
|||
f"r: {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" |
|||
| ⚫ | |||
f"Original x1: {x1}\n" |
|||
f"Recovered from r1: {mont.reduce(r1)}\n" |
|||
f"Original x2: {x2}\n" |
|||
f"Recovered from r2: {mont.reduce(r2)}\n" |
|||
) |
|||
print |
print("Montgomery computation of x1 ^ x2 mod m:") |
||
prod = mont.reduce(mont.rrm) |
prod = mont.reduce(mont.rrm) |
||
base = mont.reduce(x1 * mont.rrm) |
base = mont.reduce(x1 * mont.rrm) |
||
| Line 1,445: | Line 1,448: | ||
exp = exp >> 1 |
exp = exp >> 1 |
||
base = mont.reduce(base * base) |
base = mont.reduce(base * base) |
||
print |
print(mont.reduce(prod)) |
||
print |
print(f"\nAlternate computation of x1 ^ x2 mod m: {pow(x1, x2, m)}") |
||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
b : 2 |
|||
n : 100 |
n : 100 |
||
r : 1267650600228229401496703205376 |
r : 1267650600228229401496703205376 |
||
| Line 1,467: | Line 1,471: | ||
Alternate computation of x1 ^ x2 mod m : |
Alternate computation of x1 ^ x2 mod m : |
||
151232511393500655853002423778 |
151232511393500655853002423778 |
||
</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||