Tonelli-Shanks algorithm: Difference between revisions
→{{header|Phix}}
(Added c#) |
|||
Line 1,640:
Roots of 881398088036 are (791399408049, 208600591990) mod 1000000000039
Roots of 41660815127637347468140745042827704103445750172002 are (32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069) mod 100000000000000000000000000000000000000000000000577</pre>
=={{header|Phix}}==
{{trans|C#}}
<lang Phix>include bigatom.e
function ba_mod_exp(object base, exponent, modulus)
-- base/exponent/modulus can be integer/string/bigatom
-- returns mod(power(base,exponent),modulus) [aka b^e%m], but in bigatoms and faster.
bigatom res = BA_ONE
base = ba_mod(base,modulus)
while ba_compare(exponent,0)!=0 do
if ba_mod(exponent,2)=BA_ONE then
res = ba_mod(ba_multiply(res,base),modulus)
end if
base = ba_mod(ba_multiply(base,base),modulus)
exponent = ba_idivide(exponent,2)
end while
return res
end function
function ts(object n, p)
bigatom pm1 = ba_sub(p,1),
pm1o2 = ba_div(pm1,2)
if ba_mod_exp(n,pm1o2, p)!=BA_ONE then
return {0,0,false}
end if
bigatom q = pm1
integer ss = 0
while ba_mod(q,2)=BA_ZERO do
ss += 1
q = ba_div(q,2)
end while
if ss=1 then
bigatom r1 = ba_mod_exp(n,ba_div(ba_add(p,1),4),p)
return {r1,ba_sub(p,r1),true}
end if
integer z = 2
while ba_mod_exp(z,pm1o2,p)!=pm1 do
z += 1
end while
bigatom c = ba_mod_exp(z,q,p),
r = ba_mod_exp(n,ba_div(ba_add(q,1),2),p),
t = ba_mod_exp(n,q,p)
integer m = ss
while true do
if t=BA_ONE then
return {r,ba_sub(p,r),true}
end if
integer i = 0
bigatom zz = t
while zz!=BA_ONE and i<m-1 do
zz = ba_mod(ba_mul(zz,zz),p)
i += 1
end while
bigatom b = c
integer e = m-i-1
while e>0 do
b = ba_mod(ba_mul(b,b),p)
e -= 1
end while
r = ba_mod(ba_mul(r,b),p)
c = ba_mod(ba_mul(b,b),p)
t = ba_mod(ba_mul(t,c),p)
m = i
end while
end function
constant tests = {{10,13},
{56,101},
{1030,10009},
{1032,10009},
{44402,100049},
{665820697,1000000009},
{881398088036,1000000000039},
{"41660815127637347468140745042827704103445750172002",
ba_sprint(ba_add(ba_power(10,50),577))}}
for i=1 to length(tests) do
object {p1,p2} = tests[i]
sequence sol = ts(p1,p2)
if not string(p1) then p1 = sprintf("%d",p1) end if
if not string(p2) then p2 = sprintf("%d",p2) end if
if sol[3] then
sol = ba_sprint(sol[1])&" and "&ba_sprint(sol[2])
else
sol = "No solution exits"
end if
printf(1,"For n = %s and p = %s, %s\n",{p1,p2,sol})
end for</lang>
{{out}}
<pre>
For n = 10 and p = 13, 7 and 6
For n = 56 and p = 101, 37 and 64
For n = 1030 and p = 10009, 1632 and 8377
For n = 1032 and p = 10009, No solution exits
For n = 44402 and p = 100049, 30468 and 69581
For n = 665820697 and p = 1000000009, 378633312 and 621366697
For n = 881398088036 and p = 1000000000039, 791399408049 and 208600591990
For n = 41660815127637347468140745042827704103445750172002 and p = 100000000000000000000000000000000000000000000000577,
32102985369940620849741983987300038903725266634508 and 67897014630059379150258016012699961096274733366069
</pre>
=={{header|PicoLisp}}==
| |||