Montgomery reduction: Difference between revisions
Content added Content deleted
(add PicoLisp) |
|||
Line 878: | Line 878: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
<lang PicoLisp> |
<lang PicoLisp>(de **Mod (X Y N) |
||
(let M 1 |
|||
</lang> |
|||
(loop |
|||
(when (bit? 1 Y) |
|||
(setq M (% (* M X) N)) ) |
|||
(T (=0 (setq Y (>> 1 Y))) M) |
|||
(setq X (% (* X X) N)) ) ) ) |
|||
(de rrm (M) |
|||
(% (>> (- (* 2 Mbins)) 1) M) ) |
|||
(de reduce (A) |
|||
(do Mbins |
|||
(and (bit? 1 A) (inc 'A M)) |
|||
(setq A (>> 1 A)) ) |
|||
(and (>= A M) (dec 'A M)) |
|||
A ) |
|||
(let |
|||
(M 750791094644726559640638407699 |
|||
Mbins (length (bin M)) |
|||
RRM (rrm M) |
|||
X1 540019781128412936473322405310 |
|||
X2 515692107665463680305819378593 |
|||
T1 (* X1 RRM) |
|||
T2 (* X2 RRM) |
|||
R1 (reduce T1) |
|||
R2 (reduce T2) |
|||
R (>> (- Mbins) 1) |
|||
Prod (reduce RRM) |
|||
Base (reduce (* X1 RRM)) |
|||
Exp X2 ) |
|||
(println 'b ': 2) |
|||
(println 'n ': Mbins) |
|||
(println 'r ': R) |
|||
(println 'm ': M) |
|||
(println 't1 ': T1) |
|||
(println 't2 ': T2) |
|||
(println 'r1 ': R1) |
|||
(println 'r2 ': R2) |
|||
(prinl) |
|||
(prinl "Original x1 : " X1) |
|||
(prinl "Recovered from r1 : " (reduce R1)) |
|||
(prinl "Original x2 : " X2) |
|||
(prinl "Recovered from r2 : " (reduce R2)) |
|||
(prinl) |
|||
(prin "Montgomery computation of x1 \^ x2 mod m : ") |
|||
(while (gt0 Exp) |
|||
(and |
|||
(bit? 1 Exp) |
|||
(setq Prod (reduce (* Prod Base))) ) |
|||
(setq |
|||
Exp (>> 1 Exp) |
|||
Base (reduce (* Base Base)) ) ) |
|||
(prinl (reduce Prod)) |
|||
(prinl "Montgomery computation of x1 \^ x2 mod m : " (**Mod X1 X2 M)) )</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre>b : 2 |
||
n : 100 |
|||
</pre> |
|||
r : 1267650600228229401496703205376 |
|||
m : 750791094644726559640638407699 |
|||
t1 : 323165824550862327179367294465482435542970161392400401329100 |
|||
t2 : 308607334419945011411837686695175944083084270671482464168730 |
|||
r1 : 440160025148131680164261562101 |
|||
r2 : 435362628198191204145287283255 |
|||
Original x1 : 540019781128412936473322405310 |
|||
Recovered from r1 : 540019781128412936473322405310 |
|||
Original x2 : 515692107665463680305819378593 |
|||
Recovered from r2 : 515692107665463680305819378593 |
|||
Montgomery computation of x1 ^ x2 mod m : 151232511393500655853002423778 |
|||
Montgomery computation of x1 ^ x2 mod m : 151232511393500655853002423778</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |