Rosetta Code

Cipolla's algorithm: Difference between revisions

Page Discussion

Cipolla's algorithm (view source)

Revision as of 19:30, 3 August 2019

1,972 bytes removed ,  4 years ago
→‎{{header|Phix}}: removed bigatom (now deprecated)
(→‎{{header|Phix}}: added gmp version)
(→‎{{header|Phix}}: removed bigatom (now deprecated))
Line 1,365:
=={{header|Phix}}==
{{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"},
{"34035243914635549601583369544560650254325084643201",▼
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>
Obviously were you to use that in anger, you would probably rip out a few ba_sprint() and return false rather than "false", etc.▼
{{out}}▼
<pre>▼
{10,13,{"6","7","true"}}▼
{56,101,{"37","64","true"}}▼
{8218,10007,{"9872","135","true"}}▼
{8219,10007,{"0","0","false"}}▼
{331575,1000003,{"855842","144161","true"}}▼
{665165880,1000000007,{"475131702","524868305","true"}}▼
{"881398088036","1000000000039",{"791399408049","208600591990","true"}}▼
{"34035243914635549601583369544560650254325084643201","100000000000000000000000000000000000000000000000151",
{"82563118828090362261378993957450213573687113690751","17436881171909637738621006042549786426312886309400","true"}}▼
</pre>▼
=== gmp ===
<lang Phix>include mpfr.e
 
Line 1,536 ⟶ 1,459:
?{n,p,cipolla(n,p)}
end for</lang>
▲Obviously were you to use that in anger, you would probably rip out a few ba_sprint() and return false rather than "false", etc.
same output
▲{{out}}
▲<pre>
▲{10,13,{"6","7","true"}}
▲{56,101,{"37","64","true"}}
▲{8218,10007,{"9872","135","true"}}
▲{8219,10007,{"0","0","false"}}
▲{331575,1000003,{"855842","144161","true"}}
▲{665165880,1000000007,{"475131702","524868305","true"}}
▲{"881398088036","1000000000039",{"791399408049","208600591990","true"}}
▲ {"34035243914635549601583369544560650254325084643201","100000000000000000000000000000000000000000000000151",
▲ {"82563118828090362261378993957450213573687113690751","17436881171909637738621006042549786426312886309400","true"}}
▲</pre>
 
=={{header|PicoLisp}}==
Petelomax
7,820

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/266424"