RosettaCodeData/Task/Miller-Rabin-primality-test/Phix/miller-rabin-primality-test-1.phix

(phixonline)-->
 <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
 <span style="color: #008080;">function</span> <span style="color: #000000;">powermod</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
 <span style="color: #000080;font-style:italic;">-- calculate a^n%mod</span>
     <span style="color: #004080;">atom</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
     <span style="color: #008080;">while</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
         <span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
             <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
         <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</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;">m</span><span style="color: #0000FF;">)</span>
         <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

 <span style="color: #008080;">function</span> <span style="color: #000000;">witness</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
 <span style="color: #000080;font-style:italic;">-- n-1 = 2^s * d with d odd by factoring powers of 2 from n-1</span>
     <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;">a</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
         <span style="color: #004080;">atom</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">powermod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">=</span><span style="color: #000000;">s</span>
         <span style="color: #008080;">while</span> <span style="color: #000000;">w</span> <span style="color: #008080;">do</span>
             <span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">*</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
             <span style="color: #008080;">if</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
                 <span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
             <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
             <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span>
             <span style="color: #000000;">w</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
         <span style="color: #008080;">if</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
             <span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">return</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">;</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

 <span style="color: #008080;">function</span> <span style="color: #000000;">is_prime_mr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
         <span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
     <span style="color: #008080;">elsif</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">3</span> <span style="color: #008080;">then</span>
         <span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #004080;">atom</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">atom</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span>
     <span style="color: #008080;">while</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</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;">do</span>
         <span style="color: #000000;">d</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">2</span>
         <span style="color: #000000;">s</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>

     <span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span>
     <span style="color: #008080;">if</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">1373653</span> <span style="color: #008080;">then</span>
         <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">}</span>
     <span style="color: #008080;">elsif</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">9080191</span> <span style="color: #008080;">then</span>
         <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">31</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">73</span><span style="color: #0000FF;">}</span>
     <span style="color: #008080;">elsif</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">32</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">94910107</span><span style="color: #0000FF;">)</span>
        <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">64</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">4295041217</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
         <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">61</span><span style="color: #0000FF;">}</span>
     <span style="color: #008080;">else</span>
         <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"limits exceeded\n"</span><span style="color: #0000FF;">)</span>
         <span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">witness</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

 <span style="color: #004080;">sequence</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">999983</span><span style="color: #0000FF;">,</span><span style="color: #000000;">999809</span><span style="color: #0000FF;">,</span><span style="color: #000000;">999727</span><span style="color: #0000FF;">,</span><span style="color: #000000;">52633</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60787</span><span style="color: #0000FF;">,</span><span style="color: #000000;">999999</span><span style="color: #0000FF;">,</span><span style="color: #000000;">999995</span><span style="color: #0000FF;">,</span><span style="color: #000000;">999991</span><span style="color: #0000FF;">}</span>
 <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>
     <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;">"%d is %s\n"</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><span style="color: #008000;">"composite"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"prime"</span><span style="color: #0000FF;">}[</span><span style="color: #000000;">is_prime_mr</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><span style="color: #000000;">1</span><span style="color: #0000FF;">]})</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--