Miller–Rabin primality test: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: added DO-end labels, removed superflous blank lines (before suboutines), changed section header comments, added whitespade in multi-line statements.. -- ~~~~) |
|||
Line 1,451: | Line 1,451: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
With a K of 1, there seems to be a not uncommon number of failures, but |
With a K of 1, there seems to be a not uncommon number of failures, but |
||
:with a K ≥ 2, the failures are rare, |
: with a K ≥ 2, the failures are rare, |
||
:with a K ≥ 3, rare as hen's teeth. |
: with a K ≥ 3, rare as hen's teeth. |
||
This would be in the same vein as: 3 is prime, 5 is prime, 7 is prime, all odd numbers are prime. |
This would be in the same vein as: 3 is prime, 5 is prime, 7 is prime, all odd numbers are prime. |
||
Line 1,489: | Line 1,489: | ||
exit |
exit |
||
/*─────────────────────────────────────Miller-Rabin primality test.─────*/ |
/*─────────────────────────────────────Miller-Rabin primality test.─────*/ |
||
/*─────────────────────────────────────Rabin-Miller (also known as)─────*/ |
/*─────────────────────────────────────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. */ |
||
if n<2 | n//2==0 then return 0 /*check for low, or even number. |
if n<2 | n//2==0 then return 0 /*check for low, or even number.*/ |
||
d=n-1 |
d=n-1 |
||
nL=n-1 /*saves a bit of time, down below*/ |
nL=n-1 /*saves a bit of time, down below*/ |
||
s=0 |
s=0 |
||
do while d//2==0; d=d%2; s=s+1; end |
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)// |
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 |
do r=1 for s-1 |
||
x=(x*x)//n |
x=(x*x) // n |
||
if x==1 then return 0 /*definately it's not prime. */ |
if x==1 then return 0 /*definately it's not prime. */ |
||
if x==nL then leave |
if x==nL then leave |
||
end |
end |
||
if x\==nL then return 0 |
if x\==nL then return 0 |
||
end |
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 |
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.*/ |