1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
open Big_int
let p = big_int_of_string "32317006071311007300338913926423828248817941241140239112842009751400741706634354222619689417363569347117901737909704191754605873209195028853758986185622153212175412514901774520270235796078236248884246189477587641105928646099411723245426622522193230540919037680524235519125679715870117001058055877651038861847280257976054903569732561526167081339361799541336476559160368317896729073178384589680639671900977202194168647225871031411336429319536193471636533209717077448227988588565369208645296636077250268955505928362751121174096972998068410554359584866583291642136218231078990999448652468262416972035911852507045361090559"
let q = big_int_of_string "16158503035655503650169456963211914124408970620570119556421004875700370853317177111309844708681784673558950868954852095877302936604597514426879493092811076606087706257450887260135117898039118124442123094738793820552964323049705861622713311261096615270459518840262117759562839857935058500529027938825519430923640128988027451784866280763083540669680899770668238279580184158948364536589192294840319835950488601097084323612935515705668214659768096735818266604858538724113994294282684604322648318038625134477752964181375560587048486499034205277179792433291645821068109115539495499724326234131208486017955926253522680545279"
let g = big_int_of_string "2"
let rec powm a b p =
if le_big_int b zero_big_int then
unit_big_int
else if eq_big_int b unit_big_int then
mod_big_int a p
else
let r = powm a (shift_right_big_int b 1) p in
let z = mod_big_int (square_big_int r) p in
if eq_big_int zero_big_int (and_big_int b unit_big_int) then
z
else
mod_big_int (mult_big_int z a) p
let () = assert (eq_big_int unit_big_int (powm g q p))
|
