Cipolla's algorithm: Difference between revisions
Content added Content deleted
(→{{header|Phix}}: added gmp version) |
(→{{header|Phix}}: removed bigatom (now deprecated)) |
||
Line 1,365: | Line 1,365: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
{{libheader|mpfr}} |
|||
<lang Phix>include bigatom.e |
|||
function legendre(bigatom a, p) |
|||
-- Legendre symbol, returns 1, 0 or p - 1 |
|||
return ba_mod_exp(a,ba_idiv(ba_sub(p,1),2),p) |
|||
end function |
|||
function mul_point(sequence a, b, bigatom omega2, p) |
|||
object {xa,ya} = a, {xb,yb} = b |
|||
return {ba_mod(ba_add(ba_mul(xa,xb),ba_mul(ba_mul(ya,yb),omega2)),p), |
|||
ba_mod(ba_add(ba_mul(xa,yb),ba_mul(xb,ya)),p)} |
|||
end function |
|||
function cipolla(object no, po) |
|||
bigatom n = ba_new(no), |
|||
p = ba_new(po) |
|||
-- Step 0, validate arguments |
|||
if legendre(n,p)!=BA_ONE then return {"0","0","false"} end if |
|||
-- Step 1, find a, omega2 |
|||
integer a = 0 |
|||
bigatom omega2 |
|||
while true do |
|||
omega2 = ba_mod(ba_add(a*a,ba_sub(p,n)),p) |
|||
if ba_compare(legendre(omega2,p),ba_sub(p,BA_ONE))=0 then exit end if |
|||
a += 1 |
|||
end while |
|||
-- Step 2, compute power |
|||
sequence r = {1,0}, |
|||
s = {a,1} |
|||
bigatom nn = ba_mod(ba_idiv(ba_add(p,1),2),p) |
|||
while ba_compare(nn,BA_ZERO)>0 do |
|||
if ba_mod(nn,2)=BA_ONE then |
|||
r = mul_point(r,s,omega2,p) |
|||
end if |
|||
s = mul_point(s,s,omega2,p) |
|||
nn = ba_idiv(nn,2) |
|||
end while |
|||
-- Step 3, check x in Fp |
|||
if ba_compare(r[2],BA_ZERO)!=0 then return {"0","0","false"} end if |
|||
-- Step 5, check x * x = n |
|||
if ba_compare(ba_mod_exp(r[1],2,p),n)!=0 then return {"0","0","false"} end if |
|||
-- Step 4, solutions |
|||
return {ba_sprint(r[1]), ba_sprint(ba_sub(p,r[1])), "true"} |
|||
end function |
|||
constant tests = {{10,13}, |
|||
{56,101}, |
|||
{8218,10007}, |
|||
{8219,10007}, |
|||
{331575,1000003}, |
|||
{665165880,1000000007}, |
|||
{"881398088036","1000000000039"}, |
|||
⚫ | |||
ba_sprint(ba_add(ba_power(10,50),151))}} |
|||
for i=1 to length(tests) do |
|||
object {n,p} = tests[i] |
|||
?{n,p,cipolla(n,p)} |
|||
end for</lang> |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
{"34035243914635549601583369544560650254325084643201","100000000000000000000000000000000000000000000000151", |
|||
⚫ | |||
⚫ | |||
=== gmp === |
|||
<lang Phix>include mpfr.e |
<lang Phix>include mpfr.e |
||
Line 1,536: | Line 1,459: | ||
?{n,p,cipolla(n,p)} |
?{n,p,cipolla(n,p)} |
||
end for</lang> |
end for</lang> |
||
⚫ | |||
same output |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |