Montgomery reduction: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
Line 1,019: | Line 1,019: | ||
{{trans|D}} |
{{trans|D}} |
||
{{libheader|Phix/mpfr}} |
{{libheader|Phix/mpfr}} |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
<span style="color: #008080;">enum</span> <span style="color: #000000;">BASE</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">BITLEN</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">MODULUS</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">RRM</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">mpz</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">BITLEN</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">MODULUS</span><span style="color: #0000FF;">],</span> |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)>=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">Montgomery</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
enum BASE, BITLEN, MODULUS, RRM |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_sign</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"must be positive"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">mpz_odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"must be odd"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
function reduce(sequence mont, mpz a) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_sizeinbase</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
integer n = mont[BITLEN] |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">rrm</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
mpz m = mont[MODULUS], |
|||
<span style="color: #7060A8;">mpz_powm_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rrm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rrm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
r = mpz_init_set(a) |
|||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- BASE</span> |
|||
for i=1 to n do |
|||
<span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- BITLEN</span> |
|||
if mpz_odd(r) then |
|||
<span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- MODULUS</span> |
|||
mpz_add(r,r,m) |
|||
<span style="color: #000000;">rrm</span> <span style="color: #000080;font-style:italic;">-- 1<<(n*2) % m</span> |
|||
end if |
|||
<span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
end for |
|||
if mpz_cmp(r,m)>=0 then mpz_sub(r,r,m) end if |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"750791094644726559640638407699"</span><span style="color: #0000FF;">),</span> |
|||
return r |
|||
<span style="color: #000000;">x1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"540019781128412936473322405310"</span><span style="color: #0000FF;">),</span> |
|||
end function |
|||
<span style="color: #000000;">x2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"515692107665463680305819378593"</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span> |
|||
function Montgomery(mpz m) |
|||
<span style="color: #000000;">t2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span> |
|||
if mpz_sign(m)=-1 then crash("must be positive") end if |
|||
if not mpz_odd(m) then crash("must be odd") end if |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mont</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Montgomery</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
integer n = mpz_sizeinbase(m,2) |
|||
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RRM</span><span style="color: #0000FF;">])</span> |
|||
mpz rrm = mpz_init(2) |
|||
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RRM</span><span style="color: #0000FF;">])</span> |
|||
mpz_powm_ui(rrm,rrm,n*2,m) |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">r1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">),</span> |
|||
return {2, -- BASE |
|||
<span style="color: #000000;">r2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">),</span> |
|||
n, -- BITLEN |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span> |
|||
m, -- MODULUS |
|||
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">BITLEN</span><span style="color: #0000FF;">])</span> |
|||
rrm -- 1<<(n*2) % m |
|||
} |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"b : %d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">BASE</span><span style="color: #0000FF;">]})</span> |
|||
end function |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"n : %d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">BITLEN</span><span style="color: #0000FF;">]})</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"r : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)})</span> |
|||
mpz m = mpz_init("750791094644726559640638407699"), |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"m : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">MODULUS</span><span style="color: #0000FF;">])})</span> |
|||
x1 = mpz_init("540019781128412936473322405310"), |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"t1: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">)})</span> |
|||
x2 = mpz_init("515692107665463680305819378593"), |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"t2: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">)})</span> |
|||
t1 = mpz_init(), |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"r1: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r1</span><span style="color: #0000FF;">)})</span> |
|||
t2 = mpz_init() |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"r2: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r2</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span> |
|||
sequence mont = Montgomery(m) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Original x1 : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">)})</span> |
|||
mpz_mul(t1,x1,mont[RRM]) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Recovered from r1 : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r1</span><span style="color: #0000FF;">))})</span> |
|||
mpz_mul(t2,x2,mont[RRM]) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Original x2 : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">)})</span> |
|||
mpz r1 = reduce(mont,t1), |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Recovered from r2 : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r2</span><span style="color: #0000FF;">))})</span> |
|||
r2 = reduce(mont,t2), |
|||
r = mpz_init() |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nMontgomery computation of x1 ^ x2 mod m :"</span><span style="color: #0000FF;">)</span> |
|||
mpz_ui_pow_ui(r,2,mont[BITLEN]) |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">prod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RRM</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RRM</span><span style="color: #0000FF;">])</span> |
|||
printf(1,"b : %d\n", {mont[BASE]}) |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">base</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">),</span> |
|||
printf(1,"n : %d\n", {mont[BITLEN]}) |
|||
<span style="color: #000000;">expn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"r : %s\n", {mpz_get_str(r)}) |
|||
printf(1,"m : %s\n", {mpz_get_str(mont[MODULUS])}) |
|||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span> |
|||
printf(1,"t1: %s\n", {mpz_get_str(t1)}) |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expn</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
printf(1,"t2: %s\n", {mpz_get_str(t2)}) |
|||
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prod</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prod</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"r1: %s\n", {mpz_get_str(r1)}) |
|||
<span style="color: #000000;">prod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prod</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"r2: %s\n", {mpz_get_str(r2)}) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
printf(1,"\n") |
|||
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">expn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"Original x1 : %s\n", {mpz_get_str(x1)}) |
|||
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"Recovered from r1 : %s\n", {mpz_get_str(reduce(mont,r1))}) |
|||
<span style="color: #000000;">base</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"Original x2 : %s\n", {mpz_get_str(x2)}) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
printf(1,"Recovered from r2 : %s\n", {mpz_get_str(reduce(mont,r2))}) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prod</span><span style="color: #0000FF;">))})</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" alternate computation of x1 ^ x2 mod m :"</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"\nMontgomery computation of x1 ^ x2 mod m :") |
|||
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
mpz prod = reduce(mont,mont[RRM]) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)})</span> |
|||
mpz_mul(r,x1,mont[RRM]) |
|||
<!--</lang>--> |
|||
mpz base = reduce(mont,r), |
|||
expn = mpz_init_set(x2) |
|||
while mpz_cmp_si(expn,0)!=0 do |
|||
if mpz_odd(expn) then |
|||
mpz_mul(prod,prod,base) |
|||
prod = reduce(mont,prod) |
|||
end if |
|||
{} = mpz_fdiv_q_ui(expn,expn,2) |
|||
mpz_mul(base,base,base) |
|||
base = reduce(mont,base) |
|||
end while |
|||
printf(1,"%s\n",{mpz_get_str(reduce(mont,prod))}) |
|||
printf(1," alternate computation of x1 ^ x2 mod m :") |
|||
mpz_powm(r,x1,x2,m) |
|||
printf(1,"%s\n",{mpz_get_str(r)})</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |