Modular exponentiation: Difference between revisions
Content deleted Content added
lambdatalk small change |
follow the scheme example |
||
Line 872: | Line 872: | ||
=={{header|Lambdatalk}}== |
=={{header|Lambdatalk}}== |
||
⚫ | |||
⚫ | |||
Following scheme |
|||
⚫ | |||
⚫ | |||
⚫ | |||
{def power_mod |
|||
⚫ | |||
⚫ | |||
{def power_mod.r // recursive loop on 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 |
|||
⚫ | |||
1) 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. |
{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 |
|||
2) we use power_mod for very big numbers |
|||
⚫ | |||
{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 |
|||
2351399303373464486466122544523690094744975233415544072992656881240319 |
|||
{BN.pow 10 40}} |
|||
-> 1527229998585248450016808958343740453059 // |
-> 1527229998585248450016808958343740453059 // 3300ms |
||
</lang> |
</lang> |
||