Tonelli-Shanks algorithm: Difference between revisions
m
→{{header|Phix}}: bigatom -> mpfr
Thundergnat (talk | contribs) m (Convert to a task.) |
m (→{{header|Phix}}: bigatom -> mpfr) |
||
Line 1,726:
=={{header|Phix}}==
{{trans|C#}}
{{libheader|mpfr}}
<lang Phix>include
mpz_sub_ui(pm1,p,1) -- pm1 = p-1
mpz_fdiv_q_2exp(pm2,pm1,1) -- pm2 = pm1/2
mpz_powm(t,n,pm2,p) -- t = mod(n^pm2,p)
end while▼
▲function ts(object n, p)
pm1o2 = ba_div(pm1,2)▼
▲ if ba_mod_exp(n,pm1o2, p)!=BA_ONE then
end if
integer ss = 0
while
ss += 1
mpz_fdiv_q_2exp(q,q,1)
end while
if ss=1 then
mpz_powm(r,n,t,p) -- r = mod(n^((p+1)/4),p)
end if▼
mpz z = mpz_init(2)
mpz_powm(t,z,pm2,p) -- t = mod(z^pm2,p)
end while▼
if mpz_cmp(t,pm1)=0 then exit end if
t = ba_mod_exp(n,q,p)▼
integer m = ss▼
while true do▼
end if▼
integer i = 0▼
while zz!=BA_ONE and i<m-1 do▼
i += 1▼
end while
mpz_powm(r,n,t,p)
mpz_powm(t,n,q,p) -- t = mod(n^q,p)
▲ integer m = ss
while mpz_cmp_si(t,1) do -- t!=1
▲ integer i = 0
mpz_powm_ui(zz,zz,2,p) -- zz = mod(zz^2,p)
▲ i += 1
▲ end while
mpz_set(b,c)
integer e = m-i-1
mpz_powm_ui(b,b,2,p) -- b = mod(b^2,p)
e -= 1
▲ end while
mpz_mod(r,r,p) -- r = mod(r*b,p)
mpz_powm_ui(c,b,2,p) -- c = mod(b^2,p)
mpz_mod(t,t,p) -- t = mod(t*c,p)
end while
▲ end if
return mpz_get_str(r)&" and "&mpz_get_str(p)
▲ t = ba_mod(ba_mul(t,c),p)
▲ m = i
end function
constant tests = {{"10","13"},
{"56","101"},
{"1030","10009"},
{"1032","10009"},
{"44402","100049"},
{"665820697","1000000009"},
{"881398088036","1000000000039"},
{"41660815127637347468140745042827704103445750172002",
for i=1 to length(tests) do
▲ sol = "No solution exits"
end for</lang>
{{out}}
Line 1,816 ⟶ 1,810:
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
For n = 44402 and p = 100049, 30468 and 69581
For n = 665820697 and p = 1000000009, 378633312 and 621366697
| |||