90 lines
2.2 KiB
Text
90 lines
2.2 KiB
Text
#{
|
|
REFERENCE PYTHON:
|
|
|
|
def expmod(b,e,m):
|
|
if e == 0: return 1
|
|
r = expmod(b,e/2,m)**2 % m
|
|
if e & 1: r = (r*b) % m
|
|
return r
|
|
|
|
B 121666
|
|
E 57896044618658097711785492504343953926634992332820282019728792003956564819947
|
|
M 57896044618658097711785492504343953926634992332820282019728792003956564819949
|
|
|
|
R 37095705934669439343138083508754565189542113879843219016388785533085940283556
|
|
}#
|
|
(seed (time))
|
|
|
|
(de rnd ()
|
|
(let Big (| (rand 0 7) (>> -28 (rand 0 15)) (>> -57 (rand 0 7)))
|
|
(when (rand T)
|
|
(setq Big (| Big `(hex "1FFFFFF0FFFFFF8"))) )
|
|
(do (rand 0 2)
|
|
(let Dig (| (rand 0 7) (>> -30 (rand 0 15)) (>> -61 (rand 0 7)))
|
|
(when (rand T)
|
|
(setq Dig (| Dig `(hex "1FFFFFFC3FFFFFF8"))) )
|
|
(setq Big (| Dig (>> -64 Big))) ) )
|
|
Big ) )
|
|
(de modulo (X Y)
|
|
(% (+ Y (% X Y)) Y) )
|
|
(de expmod (B E M)
|
|
(if (=0 E)
|
|
1
|
|
(let R
|
|
(%
|
|
(** (expmod B (/ E 2) M) 2)
|
|
M )
|
|
(when (bit? 1 E)
|
|
(setq R (modulo (* R B) M))
|
|
)
|
|
R ) ) )
|
|
(de inv (X)
|
|
(expmod X (- *Q 2) *Q) )
|
|
(de xrecover (Y)
|
|
(let
|
|
(YY (* Y Y)
|
|
XX (* (dec YY) (inv (inc (* *D YY))))
|
|
X (expmod XX (/ (+ *Q 3) 8) *Q) )
|
|
(and
|
|
(n0 (% (- (* X X) XX) *Q))
|
|
(setq X (% (* *I X) *Q)) )
|
|
(and
|
|
(n0 (% X 2))
|
|
(setq X (- *Q X)) )
|
|
X ) )
|
|
(setq *S (0 -1 -2 -3 -4 -5 -6 -7 .))
|
|
(setq *B 256)
|
|
(setq *Q `(- (** 2 255) 19))
|
|
(setq *L `(+ (** 2 252) 27742317777372353535851937790883648493))
|
|
(setq *D `(* -121665 (inv 121666)))
|
|
(setq *I `(expmod 2 (/ (dec *Q) 4) *Q))
|
|
(setq *By `(* 4 (inv 5)))
|
|
(setq *Bxy
|
|
(cons
|
|
(% (xrecover *By) *Q)
|
|
(% *By *Q) ) )
|
|
|
|
(de steps (E)
|
|
(flip
|
|
(make
|
|
(while
|
|
(and
|
|
(link (swap 'E (/ E 2)))
|
|
(gt0 E) ) ) ) ) )
|
|
(de expmod-OLD (B E M)
|
|
(let R 1
|
|
(for I (steps E)
|
|
(and
|
|
(setq R (modulo (* R R) M))
|
|
(bit? 1 I)
|
|
(setq R (modulo (* R B) M))
|
|
) )
|
|
R ) )
|
|
(do 10000
|
|
(let (B (rnd) E (rnd) M (rnd))
|
|
(when (rand T) (setq B (- B)))
|
|
(test
|
|
(expmod-OLD B E M)
|
|
(expmod B E M) ) ) )
|
|
(msg 'ok)
|
|
(bye)
|