Modular exponentiation: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 872: / Line 872: @@
 =={{header|Lambdatalk}}==
-<lang scheme>
-{require lib_BN}
+Following scheme
-Using the lib_BN library for big numbers.
-Note that {BN.compare a b} returns 1 if a > b, 0 if a = b and -1 of a < b.
+<lang scheme>
-{def power_mod
+We will call the lib_BN library for big numbers:
+{require lib_BN}
- {def power_mod.r                     // recursive loop on x
-  {lambda {:b :e :m :x}
-   {if {= {BN.compare :e 0} 1}           // if e > 0
-    then {power_mod.r                    // then recurse with
-             {BN.% {BN.* :b :b} :m}         // b = (b*b)%2
-             {BN.intPart {BN./ :e 2}}       // e = e // 2
-             :m                             // m inchanged
-             {if {= {BN.compare {BN.% :e 2} 0} 1} // if e%2 > 0
-              then {BN.% {BN.* :b :x} :m}         // x = (b*x)%m
-              else :x}}                           // x inchanged
-    else :x}}}                           // else x
- {lambda {:b :e :m}
-  {power_mod :b :e :m 1}}}            // initialize x and loop
--> power_mod
+In this library {BN.compare a b} returns 1 if a > b, 0 if a = b and -1 if a < b.
-) we can use lib_BN for relatively small numbers
+For a better readability we define three small functions
+{def BN.= {lambda {:a :b} {= {BN.compare :a :b} 0}}}
-{BN.pow 2 100}
+-> BN.=
--> 1267650600228229401496703205376
-{BN.% {BN.pow 2 100} 1000000}
+{def BN.even? {lambda {:n} {= {BN.compare {BN.% :n 2} 0} 0}}}
--> 205376
+-> BN.even?
+{def BN.square {lambda {:n} {BN.* :n :n}}}
+-> BN.square
+{def mod-exp
-) we use power_mod for very big numbers
+ {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
-{power_mod
- 2988348162058574136915891421498819466320163312926952423791023078876139
+  2988348162058574136915891421498819466320163312926952423791023078876139
- 2351399303373464486466122544523690094744975233415544072992656881240319
+  2351399303373464486466122544523690094744975233415544072992656881240319
- {BN.pow 10 40}}
+  {BN.pow 10 40}}
--> 1527229998585248450016808958343740453059   // 2900ms
+-> 1527229998585248450016808958343740453059   // 3300ms
 </lang>