Montgomery reduction: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: replaced with gmp version) |
|||
Line 779: | Line 779: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|D}} |
{{trans|D}} |
||
{{libheader|mpfr}} |
|||
<lang Phix>include |
<lang Phix>include mpfr.e |
||
function bitLength(bigint v) |
|||
if bi_sign(v)=-1 then v = bi_neg(v) end if |
|||
integer result = 0 |
|||
⚫ | |||
⚫ | |||
result += 1 |
|||
end while |
|||
return result |
|||
end function |
|||
enum BASE, BITLEN, MODULUS, RRM |
enum BASE, BITLEN, MODULUS, RRM |
||
function reduce(sequence mont, |
function reduce(sequence mont, mpz a) |
||
integer n = mont[BITLEN] |
integer n = mont[BITLEN] |
||
mpz m = mont[MODULUS], |
|||
r = mpz_init_set(a) |
|||
for i=1 to n do |
for i=1 to n do |
||
if |
if mpz_odd(r) then |
||
mpz_add(r,r,m) |
|||
end if |
end if |
||
{ |
{} = mpz_fdiv_q_ui(r,r,2) |
||
end for |
end for |
||
if |
if mpz_cmp(r,m)>=0 then mpz_sub(r,r,m) end if |
||
return |
return r |
||
end function |
end function |
||
function Montgomery( |
function Montgomery(mpz m) |
||
if |
if mpz_sign(m)=-1 then crash("must be positive") end if |
||
if |
if not mpz_odd(m) then crash("must be odd") end if |
||
integer n = |
integer n = mpz_sizeinbase(m,2) |
||
mpz rrm = mpz_init(2) |
|||
mpz_powm_ui(rrm,rrm,n*2,m) |
|||
return {2, -- BASE |
return {2, -- BASE |
||
n, -- BITLEN |
n, -- BITLEN |
||
Line 818: | Line 811: | ||
end function |
end function |
||
mpz m = mpz_init("750791094644726559640638407699"), |
|||
x1 = mpz_init("540019781128412936473322405310"), |
|||
x2 = mpz_init("515692107665463680305819378593"), |
|||
t1 = mpz_init(), |
|||
t2 = mpz_init() |
|||
sequence mont = Montgomery(m) |
sequence mont = Montgomery(m) |
||
mpz_mul(t1,x1,mont[RRM]) |
|||
mpz_mul(t2,x2,mont[RRM]) |
|||
mpz r1 = reduce(mont,t1), |
|||
r2 = reduce(mont,t2), |
|||
r = mpz_init() |
|||
mpz_ui_pow_ui(r,2,mont[BITLEN]) |
|||
printf(1,"b : %d\n", {mont[BASE]}) |
printf(1,"b : %d\n", {mont[BASE]}) |
||
printf(1,"n : %d\n", {mont[BITLEN]}) |
printf(1,"n : %d\n", {mont[BITLEN]}) |
||
printf(1,"r : %s\n", { |
printf(1,"r : %s\n", {mpz_get_str(r)}) |
||
printf(1,"m : %s\n", { |
printf(1,"m : %s\n", {mpz_get_str(mont[MODULUS])}) |
||
printf(1,"t1: %s\n", { |
printf(1,"t1: %s\n", {mpz_get_str(t1)}) |
||
printf(1,"t2: %s\n", { |
printf(1,"t2: %s\n", {mpz_get_str(t2)}) |
||
printf(1,"r1: %s\n", { |
printf(1,"r1: %s\n", {mpz_get_str(r1)}) |
||
printf(1,"r2: %s\n", { |
printf(1,"r2: %s\n", {mpz_get_str(r2)}) |
||
printf(1,"\n") |
printf(1,"\n") |
||
printf(1,"Original x1 : %s\n", { |
printf(1,"Original x1 : %s\n", {mpz_get_str(x1)}) |
||
printf(1,"Recovered from r1 : %s\n", { |
printf(1,"Recovered from r1 : %s\n", {mpz_get_str(reduce(mont,r1))}) |
||
printf(1,"Original x2 : %s\n", { |
printf(1,"Original x2 : %s\n", {mpz_get_str(x2)}) |
||
printf(1,"Recovered from r2 : %s\n", { |
printf(1,"Recovered from r2 : %s\n", {mpz_get_str(reduce(mont,r2))}) |
||
printf(1,"\nMontgomery computation of x1 ^ x2 mod m :") |
printf(1,"\nMontgomery computation of x1 ^ x2 mod m :") |
||
mpz prod = reduce(mont,mont[RRM]) |
|||
mpz_mul(r,x1,mont[RRM]) |
|||
mpz base = reduce(mont,r), |
|||
expn = mpz_init_set(x2) |
|||
while bitLength(expn)>0 do |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
mpz_mul(prod,prod,base) |
|||
⚫ | |||
end if |
end if |
||
{ |
{} = mpz_fdiv_q_ui(expn,expn,2) |
||
base |
mpz_mul(base,base,base) |
||
⚫ | |||
end while |
end while |
||
printf(1,"%s\n",{ |
printf(1,"%s\n",{mpz_get_str(reduce(mont,prod))}) |
||
printf(1," |
printf(1," alternate computation of x1 ^ x2 mod m :") |
||
mpz_powm(r,x1,x2,m) |
|||
printf(1,"%s\n",{ |
printf(1,"%s\n",{mpz_get_str(r)})</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |