Modular exponentiation: Difference between revisions

Content added Content deleted
(adding lambdatalk)
m (→‎{{header|REXX}}: added/changed whitespace and comments, optimized the function, simplified the function code, added wording in the REXX section header and the output section header.)
Line 1,214: Line 1,214:
=={{header|REXX}}==
=={{header|REXX}}==
===version 1===
===version 1===
This REXX program attempts to handle   ''any''   '''a''', '''b''', or '''m''',   but there are limits for any computer language.
This REXX program attempts to handle &nbsp; ''any'' <big> &nbsp; '''a''', &nbsp; '''b''', &nbsp; or &nbsp; '''m''', </big> &nbsp; but there are limits for any computer language.
⚫
<br>For some REXXes, it's around eight million digits for any arithmetic expression or value, which puts limitations on the
⚫
<br>values of &nbsp; <big>a<sup>2</sup></big> &nbsp; or &nbsp; <big>10<sup>m</sup></big>.


⚫
For some REXXes, it's around eight million digits for any arithmetic expression or value, which puts limitations on
⚫
There is REXX code (below) to automatically adjust the number of digits to accommodate huge numbers which are
⚫
<br>the values of &nbsp; <big>a<sup>2</sup></big> &nbsp; or &nbsp; <big>10<sup>m</sup></big>.
⚫
<br>computed when raising large numbers to some arbitrary power.

⚫
<lang rexx>/*REXX program displays the modular exponentiation of: a**b mod M */
⚫
This REXX program code has code to &nbsp; automatically &nbsp; adjust the number of decimal digits to accommodate huge
⚫
parse arg a b mm /*obtain optional args from the CL*/
⚫
<br>numbers which are computed when raising large numbers to some arbitrary power.
⚫
if a=='' | a=="," then a=2988348162058574136915891421498819466320163312926952423791023078876139
⚫
<lang rexx>/*REXX program displays the modular exponentiation of: a**b mod m */
⚫
if b=='' | b=="," then b=2351399303373464486466122544523690094744975233415544072992656881240319
if mm='' | mm="," then mm=40 /*MM not specified? Use default.*/
parse arg a b m /*obtain optional args from the CL*/
⚫
if a=='' | a=="," then a= 2988348162058574136915891421498819466320163312926952423791023078876139
⚫
say 'a=' a; say " ("length(a) 'digits)' /*display the value of A. */
⚫
if b=='' | b=="," then b= 2351399303373464486466122544523690094744975233415544072992656881240319
say 'b=' b; say " ("length(b) 'digits)' /* " " " " B. */
do j=1 for words(mm); y= word(mm, j) /*use one of the MM powers (list).*/
if m ='' | m ="," then m= 40 /*Not specified? Then use default.*/
say copies('═', linesize() - 1) /*show a nice separator fence line*/
say 'a=' a " ("length(a) 'digits)' /*display the value of A (&length)*/
⚫
say 'b=' b " ("length(b) 'digits)' /* " " " " B " */
⚫
say 'a**b (mod 10**'y")=" powerMod(a,b,10**y) /*display the answer ───► console.*/
do j=1 for words(m); y= word(m, j) /*use one of the MM powers (list).*/
⚫
end /*j*/
exit /*stick a fork in it, we're done. */
say copies('═', linesize() - 1) /*show a nice separator fence line*/
⚫
say 'a**b (mod 10**'y")=" powerMod(a,b,10**y) /*display the answer ───► console.*/
⚫
end /*j*/
⚫
exit 0 /*stick a fork in it, we're done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
powerMod: procedure; parse arg x,p,m /*fast modular exponentiation code*/
powerMod: procedure; parse arg x,p,mm /*fast modular exponentiation code*/
parse value max(x*x, p, m)'E0' with "E" e /*obtain the biggest of the three.*/
parse value max(x*x, p, mm)'E0' with "E" e /*obtain the biggest of the three.*/
numeric digits max(20, e+e) /*big enough to handle A². */
numeric digits max(20, e+e) /*ensure big enough to handle A².*/
$= 1 /*use this for the first value. */
$= 1 /*use this for the first value. */
do while p\==0 /*perform while P isn't zero.*/
do until p==0 /*perform until P is equal to zero*/
if p//2 then $= $ * x // m /*is P odd? (is ÷ remainder≡1).*/
if p // 2 then $= $ * x // mm /*is P odd? (is ÷ remainder ≡ 1?)*/
p= p % 2; x= x * x // m /*halve P; calculate x² mod n */
p= p % 2; x= x * x // mm /*halve P; calculate x² mod n */
end /*while*/; return $ /* [↑] keep mod'ing 'til equal 0.*/</lang>
end /*until*/; return $ /* [↑] keep mod'ing until P=zero.*/</lang>
This REXX program makes use of &nbsp; '''LINESIZE''' &nbsp; REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console).
This REXX program makes use of &nbsp; '''LINESIZE''' &nbsp; REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console).
<br>The BIF is used to determine the width of a line separator &nbsp; (which are used to separate different outputs).
<br>The &nbsp; '''LINESIZE.REX''' &nbsp; REXX program is included here &nbsp; ──► &nbsp; [[LINESIZE.REX]].<br>
<br>The &nbsp; '''LINESIZE.REX''' &nbsp; REXX program is included here &nbsp; ──► &nbsp; [[LINESIZE.REX]].<br>


{{out|output|text=&nbsp; when using the inputs of: &nbsp; <tt> &nbsp; , &nbsp; , &nbsp; 40 &nbsp; 80 &nbsp; 180 &nbsp; 888 </tt>}}
{{out|output|text=&nbsp; when using the inputs of: &nbsp; <tt> &nbsp; , &nbsp; , &nbsp; 40 &nbsp; 80 &nbsp; 180 &nbsp; 888 </tt>}}
<pre>
<pre>
a= 2988348162058574136915891421498819466320163312926952423791023078876139
a= 2988348162058574136915891421498819466320163312926952423791023078876139 (70 digits)
⚫
b= 2351399303373464486466122544523690094744975233415544072992656881240319 (70 digits)
(70 digits)
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
⚫
b= 2351399303373464486466122544523690094744975233415544072992656881240319
(70 digits)
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
a**b (mod 10**40)= 1527229998585248450016808958343740453059
a**b (mod 10**40)= 1527229998585248450016808958343740453059
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
a**b (mod 10**80)= 53259517041910225328867076245698908287781527229998585248450016808958343740453059
a**b (mod 10**80)= 53259517041910225328867076245698908287781527229998585248450016808958343740453059
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
a**b (mod 10**180)= 31857295076204937005344367438778481743660325586328069392203762862423884839076695547212682454523811053259517041910225328867076245698908287781527229998585248450016808958343740453059
a**b (mod 10**180)= 31857295076204937005344367438778481743660325586328069392203762862423884839076695547212682454523811053259517041910225328867076245698908287781527229998585248450016808958343740453059
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
a**b (mod 10**888)= 261284964380836515397030706363442226571397237057488951313684545241085642329943676248755716124260447188788530017182951051652748425560733974835944416069466176713156182727448301838517000343485327001656948285381173038339073779331230132340669899896448938858785362771190460312412579875349871655999446205426049662261450633448468931573506876255644749155348923523680730999869785472779116009356696816952771965930728940530517799329942590114178284009260298426735086579254282591289756840358811
a**b (mod 10**888)= 261284964380836515397030706363442226571397237057488951313684545241085642329943676248755716124260447188788530017182951051652748425560733974835944416069466176713156182727448301838517
822151307479352856856983393715348870715239020037962938019847992960978849852850613063177471175191444262586321233906926671000476591123695550566585083205841790404069511972417770392822283604206143472509425391114072344402850867571806031857295076204937005344367438778481743660325586328069392203762862423884839076695547212682454523811053259517041910225328867076245698908287781527229998585248450016808958343740453059
00034348532700165694828538117303833907377933123013234066989989644893885878536277119046031241257987534987165599944620542604966226145063344846893157350687625564474915534892352368073099986978547277911600
and took 5.97 seconds.
93566968169527719659307289405305177993299425901141782840092602984267350865792542825912897568403588118221513074793528568569833937153488707152390200379629380198479929609788498528506130631774711751914442
62586321233906926671000476591123695550566585083205841790404069511972417770392822283604206143472509425391114072344402850867571806031857295076204937005344367438778481743660325586328069392203762862423884
839076695547212682454523811053259517041910225328867076245698908287781527229998585248450016808958343740453059
</pre>
</pre>


===version 2===
===version 2===
This REXX version handles only up to 100 decimal digits.
This REXX version handles only up to 100 decimal digits.
<lang rexx>/* Modular exponentiation */
<lang rexx>
/* REXX Modular exponentiation */


numeric digits 100
numeric digits 100
Retrieved from "https://rosettacode.org/wiki/Modular_exponentiation"