Miller–Rabin primality test: Difference between revisions

Content added Content deleted
(→‎{{header|Go}}: added deterministic test)
m (→‎{{header|REXX}}: changed the separator fence, indented DO loops more, added DO-END comment labels. -- ~~~~)
Line 1,536: Line 1,536:
call suspenders /*suspenders now, belt later... */
call suspenders /*suspenders now, belt later... */
primePi=# /*save the count of (real) primes*/
primePi=# /*save the count of (real) primes*/
say "They're" primePi 'primes <=' limit /*might as well crow a wee bit.*/
say "They're" primePi 'primes ≤' limit /*might as well crow a wee bit. */
say /*nothing wrong with whitespace. */
say /*nothing wrong with whitespace. */
do a=2 to accur /*(skipping 1) do range of K's.*/
say copies('─',79) /*show separator for the eyeballs*/
⚫
mrp=0 /*prime counter for this pass. */


do a=2 to accur /*(skipping 1) do range of K's.*/
do z=1 for limit /*now, let's get busy and crank. */
say copies('-',79) /*show separator for the eyeballs*/
p=Miller_Rabin(z,a) /*invoke and pray... */
mrp=0 /*prime counter for this pass. */
if p==0 then iterate /*Not prime? Then try another. */
mrp=mrp+1 /*well, found another one, by gum*/


do z=1 for limit /*now, let's get busy and crank. */
if tell then say z, /*maybe should do a show & tell ?*/
p=Miller_Rabin(z,a) /*invoke and pray... */
if p==0 then iterate /*Not prime? Then try another. */
⚫
mrp=mrp+1 /*well, found another one, by gum*/

if tell then say z, /*maybe should do a show & tell ?*/
'is prime according to Miller-Rabin primality test with K='a
'is prime according to Miller-Rabin primality test with K='a


if !.z\==0 then iterate
if !.z\==0 then iterate
say '[K='k"] " z "isn't prime !" /*oopsy-doopsy and whoopsy-daisy!*/
say '[K='a"] " z "isn't prime !" /*oopsy-doopsy & whoopsy-daisy!*/
end
end /*z*/


say 'for 1-->'limit", K="k', Miller-Rabin primality test found' mrp,
say 'for 1──►'limit", K="a', Miller-Rabin primality test found' mrp,
'primes {out of' primePi"}"
'primes {out of' primePi"}"
end
end /*a*/
exit /*stick a fork in it, we're done.*/

/*─────────────────────────────────────Miller─Rabin primality test.─────*/
exit
/*─────────────────────────────────────Rabin─Miller (also known as)─────*/
/*─────────────────────────────────────Miller-Rabin primality test.─────*/
/*─────────────────────────────────────Rabin-Miller (also known as)─────*/
Miller_Rabin: procedure; parse arg n,k
Miller_Rabin: procedure; parse arg n,k
if n==2 then return 1 /*special case of an even prime. */
if n==2 then return 1 /*special case of an even prime. */
Line 1,569: Line 1,567:
s=0
s=0


do while d//2==0; d=d%2; s=s+1; end /*while d//2==0 */
do while d//2==0; d=d%2; s=s+1; end /*while d//2==0 */


do k
do k
a=random(2,nL)
a=random(2,nL)
x=(a**d) // n /*this number can get big fast. */
x=(a**d) // n /*this number can get big fast. */
if x==1 | x==nL then iterate
if x==1 | x==nL then iterate

do r=1 for s-1
x=(x*x) // n
do r=1 for s-1
if x==1 then return 0 /*definately it's not prime. */
x=(x*x) // n
if x==nL then leave
if x==1 then return 0 /*it's definately not prime. */
end
if x==nL then leave
⚫
end /*r*/
if x\==nL then return 0

⚫
end /*k*/
if x\==nL then return 0 /*nope, it ain't prime nohows. */
end /*k*/
/*maybe it is, maybe it ain't ...*/
/*maybe it is, maybe it ain't ...*/
return 1 /*coulda/woulda/shoulda be prime.*/
return 1 /*coulda/woulda/shoulda be prime.*/
/*──────────────────────────────────SUSPENDERS subroutine───────────────*/
/*─────────────────────────────────────SUSPENDERS subroutine────────────*/
suspenders: @.=0; !.=0 /*crank up the ole prime factory.*/
suspenders: @.=0; !.=0 /*crank up the ole prime factory.*/
@.1=2; @.2=3; @.3=5; #=3 /*prime the pump with low primes.*/
@.1=2; @.2=3; @.3=5; #=3 /*prime the pump with low primes.*/
!.2=1; !.3=1; !.5=1 /*and don't forget the water jar.*/
!.2=1; !.3=1; !.5=1 /*and don't forget the water jar.*/

do j=@.#+2 by 2 to limit /*just process the odd integers. */
do k=2 while @.k**2<=j /*let's do the ole primality test*/
do j =@.#+2 by 2 to limit /*just process the odd integers. */
if j//@.k==0 then iterate j /*the Greek way, in days of yore.*/
do k=2 while @.k**2<=j /*let's do the ole primality test*/
end /*k*/ /*a useless comment, but hey!! */
if j//@.k==0 then iterate j /*the Greek way, in days of yore.*/
#=#+1 /*bump the prime counter. */
end /*k*/ /*a useless comment, but hey!! */
@.#=j /*keep priming the prime pump. */
#=#+1 /*bump the prime counter. */
!.j=1 /*and keep filling the water jar.*/
@.#=j /*keep priming the prime pump. */
end /*j*/ /*this comment not left blank. */
!.j=1 /*and keep filling the water jar.*/
end /*j*/ /*this comment not left blank. */
return /*whew! All done with the primes*/</lang>
return /*whew! All done with the primes*/</lang>
{{out|Output when using the input of <tt>10000 10</tt>}}
{{out|Output when using the input of: <tt>10000 10</tt>}}
<pre style="height:30ex;overflow:scroll">
<pre style="height:30ex;overflow:scroll">
They're 1229 primes <= 10000
They're 1229 primes ≤ 10000


───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
[K=2] 2701 isn't prime !
[K=2] 2701 isn't prime !
for 1-->10000, K=2, Miller-Rabin primality test found 1230 primes {out of 1229}
for 1──►10000, K=2, Miller─Rabin primality test found 1230 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->10000, K=2, Miller-Rabin primality test found 1229 primes {out of 1229}
for 1──►10000, K=2, Miller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->10000, K=3, Miller-Rabin primality test found 1229 primes {out of 1229}
for 1──►10000, K=3, Miller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->10000, K=4, Miller-Rabin primality test found 1229 primes {out of 1229}
for 1──►10000, K=4, Miller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->10000, K=5, Miller-Rabin primality test found 1229 primes {out of 1229}
for 1──►10000, K=5, Miller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->10000, K=6, Miller-Rabin primality test found 1229 primes {out of 1229}
for 1──►10000, K=6, Miller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->10000, K=7, Miller-Rabin primality test found 1229 primes {out of 1229}
for 1──►10000, K=7, Miller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->10000, K=8, Miller-Rabin primality test found 1229 primes {out of 1229}
for 1──►10000, K=8, Miller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->10000, K=9, Miller-Rabin primality test found 1229 primes {out of 1229}
for 1──►10000, K=9, Miller─Rabin primality test found 1229 primes {out of 1229}
───────────────────────────────────────────────────────────────────────────────
-------------------------------------------------------------------------------
for 1-->10000, K=10, Miller-Rabin primality test found 1229 primes {out of 1229}
for 1──►10000, K=10, Miller─Rabin primality test found 1229 primes {out of 1229}
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Miller–Rabin_primality_test"