Rosetta Code

Tonelli-Shanks algorithm: Difference between revisions

Page Discussion

Tonelli-Shanks algorithm (view source)

Revision as of 02:43, 11 June 2021

19,236 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (added wikipedia tag)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 2,909:
{{trans|C#}}
{{libheader|Phix/mpfr}}
<!--<lang Phix>include mpfr.e(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
function ts(string ns, ps)
mpz n = mpz_init(ns),
<span style="color: #008080;">function</span> <span style="color: #000000;">ts</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">ns</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ps</span><span style="color: #0000FF;">)</span>
p = mpz_init(ps),
<span style="color: #004080;">mpz</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ns</span><span style="color: #0000FF;">),</span>
t = mpz_init(),
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ps</span><span style="color: #0000FF;">),</span>
r = mpz_init(),
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
pm1 = mpz_init(),
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
pm2 = mpz_init()
<span style="color: #000000;">pm1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
mpz_sub_ui(pm1,p,1) -- pm1 = p-1
<span style="color: #000000;">pm2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
mpz_fdiv_q_2exp(pm2,pm1,1) -- pm2 = pm1/2
<span style="color: #7060A8;">mpz_sub_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pm1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- pm1 = p-1</span>
mpz_powm(t,n,pm2,p) -- t = mod(n^pm2,p)
<span style="color: #7060A8;">mpz_fdiv_q_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pm2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pm1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- pm2 = pm1/2</span>
if mpz_cmp_si(t,1)!=0 then
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pm2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t = mod(n^pm2,p)</span>
return "No solution exists"
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
end if
<span style="color: #008080;">return</span> <span style="color: #008000;">"No solution exists"</span>
mpz q = mpz_init_set(pm1)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
integer ss = 0
<span style="color: #004080;">mpz</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pm1</span><span style="color: #0000FF;">)</span>
while mpz_even(q) do
<span style="color: #004080;">integer</span> <span style="color: #000000;">ss</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
ss += 1
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
mpz_fdiv_q_2exp(q,q,1) -- q/=2
<span style="color: #000000;">ss</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end while
<span style="color: #7060A8;">mpz_fdiv_q_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- q/=2</span>
if ss=1 then
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
mpz_add_ui(t,p,1)
<span style="color: #008080;">if</span> <span style="color: #000000;">ss</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
mpz_fdiv_q_2exp(t,t,2)
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
mpz_powm(r,n,t,p) -- r = mod(n^((p+1)/4),p)
<span style="color: #7060A8;">mpz_fdiv_q_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
else
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- r = mod(n^((p+1)/4),p)</span>
mpz z = mpz_init(2)
<span style="color: #008080;">else</span>
while true do
<span style="color: #004080;">mpz</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
mpz_powm(t,z,pm2,p) -- t = mod(z^pm2,p)
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
if mpz_cmp(t,pm1)=0 then exit end if
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pm2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t = mod(z^pm2,p)</span>
mpz_add_ui(z,z,1) -- z+= 1
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pm1</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end while
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- z+= 1</span>
mpz {b,c,zz} = mpz_inits(3)
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
mpz_powm(c,z,q,p) -- c = mod(z^q,p)
<span style="color: #004080;">mpz</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zz</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
mpz_add_ui(t,q,1)
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- c = mod(z^q,p)</span>
mpz_fdiv_q_2exp(t,t,1)
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
mpz_powm(r,n,t,p) -- r = mod(n^((q+1)/2),p)
<span style="color: #7060A8;">mpz_fdiv_q_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
mpz_powm(t,n,q,p) -- t = mod(n^q,p)
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- r = mod(n^((q+1)/2),p)</span>
integer m = ss
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t = mod(n^q,p)</span>
while mpz_cmp_si(t,1) do -- t!=1
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ss</span>
integer i = 0
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- t!=1</span>
mpz_set(zz,t)
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
while mpz_cmp_si(zz,1)!=0 and i<m-1 do
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
mpz_powm_ui(zz,zz,2,p) -- zz = mod(zz^2,p)
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">m</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
i += 1
<span style="color: #7060A8;">mpz_powm_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- zz = mod(zz^2,p)</span>
end while
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
mpz_set(b,c)
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
integer e = m-i-1
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
while e>0 do
<span style="color: #004080;">integer</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
mpz_powm_ui(b,b,2,p) -- b = mod(b^2,p)
<span style="color: #008080;">while</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
e -= 1
<span style="color: #7060A8;">mpz_powm_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- b = mod(b^2,p)</span>
end while
<span style="color: #000000;">e</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
mpz_mul(r,r,b)
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
mpz_mod(r,r,p) -- r = mod(r*b,p)
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
mpz_powm_ui(c,b,2,p) -- c = mod(b^2,p)
<span style="color: #7060A8;">mpz_mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- r = mod(r*b,p)</span>
mpz_mul(t,t,c)
<span style="color: #7060A8;">mpz_powm_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- c = mod(b^2,p)</span>
mpz_mod(t,t,p) -- t = mod(t*c,p)
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
m = i
<span style="color: #7060A8;">mpz_mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t = mod(t*c,p)</span>
end while
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
mpz_sub(p,p,r)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return mpz_get_str(r)&" and "&mpz_get_str(p)
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #008080;">return</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">" and "</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
constant tests = {{"10","13"},
{"56","101"},
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #008000;">"10"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"13"</span><span style="color: #0000FF;">},</span>
{"1030","10009"},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"56"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"101"</span><span style="color: #0000FF;">},</span>
{"1032","10009"},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"1030"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"10009"</span><span style="color: #0000FF;">},</span>
{"44402","100049"},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"1032"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"10009"</span><span style="color: #0000FF;">},</span>
{"665820697","1000000009"},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"44402"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"100049"</span><span style="color: #0000FF;">},</span>
{"881398088036","1000000000039"},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"665820697"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1000000009"</span><span style="color: #0000FF;">},</span>
{"41660815127637347468140745042827704103445750172002",
<span style="color: #0000FF;">{</span><span style="color: #008000;">"881398088036"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1000000000039"</span><span style="color: #0000FF;">},</span>
sprintf("1%s577",repeat('0',47))}} -- 10^50+577
<span style="color: #0000FF;">{</span><span style="color: #008000;">"41660815127637347468140745042827704103445750172002"</span><span style="color: #0000FF;">,</span>
<span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1%s577"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">47</span><span style="color: #0000FF;">))}}</span> <span style="color: #000080;font-style:italic;">-- 10^50+577</span>
for i=1 to length(tests) do
string {p1,p2} = tests[i]
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
printf(1,"For n = %s and p = %s, %s\n",{p1,p2,ts(p1,p2)})
<span style="color: #004080;">string</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
end for</lang>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"For n = %s and p = %s, %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
<pre>
Petelomax
7,795

edits

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