28 lines
857 B
Text
28 lines
857 B
Text
We will call the lib_BN library for big numbers:
|
|
|
|
{require lib_BN}
|
|
|
|
In this library {BN.compare a b} returns 1 if a > b, 0 if a = b and -1 if a < b.
|
|
For a better readability we define three small functions
|
|
|
|
{def BN.= {lambda {:a :b} {= {BN.compare :a :b} 0}}}
|
|
-> BN.=
|
|
{def BN.even? {lambda {:n} {= {BN.compare {BN.% :n 2} 0} 0}}}
|
|
-> BN.even?
|
|
{def BN.square {lambda {:n} {BN.* :n :n}}}
|
|
-> BN.square
|
|
|
|
{def mod-exp
|
|
{lambda {:a :n :mod}
|
|
{if {BN.= :n 0}
|
|
then 1
|
|
else {if {BN.even? :n}
|
|
then {BN.% {BN.square {mod-exp :a {BN./ :n 2} :mod}} :mod}
|
|
else {BN.% {BN.* :a {mod-exp :a {BN.- :n 1} :mod}} :mod}}}}}
|
|
-> mod-exp
|
|
|
|
{mod-exp
|
|
2988348162058574136915891421498819466320163312926952423791023078876139
|
|
2351399303373464486466122544523690094744975233415544072992656881240319
|
|
{BN.pow 10 40}}
|
|
-> 1527229998585248450016808958343740453059 // 3300ms
|