Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(Refactored the code in a way that is more idiomatic to Forth.) |
|||
Line 1,510: | Line 1,510: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
Forth only supports native ints (e.g. 64 bits on most modern machines), so this version uses a set of known deterministic bases that is known to be correct for 64 bit integers (and possibly greater). Prior to the Miller Rabin check, the "prime?" word checks for divisibility by some small primes. |
Forth only supports native ints (e.g. 64 bits on most modern machines), so this version uses a set of known deterministic bases that is known to be correct for 64 bit integers (and possibly greater). Prior to the Miller Rabin check, the "prime?" word checks for divisibility by some small primes. |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
\ modular multiplication and exponentiation |
\ modular multiplication and exponentiation |
||
\ |
\ |
||
Line 1,544: | Line 1,530: | ||
then |
then |
||
repeat nip rdrop ; |
repeat nip rdrop ; |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
\ actual Miller-Rabin test |
\ actual Miller-Rabin test |
||
Line 1,554: | Line 1,555: | ||
4.759.123.141 drop constant mr-det-3 \ Deterministic threshold; 3 bases |
4.759.123.141 drop constant mr-det-3 \ Deterministic threshold; 3 bases |
||
: fermat-square-test ( n m s -- ? ) \ perform n = n^2 (mod m), s-1 times |
|||
1- 0 ?do |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
: strong-fermat-pseudoprime? ( n a -- ? ) |
|||
over >r \ keep the modulus on the return stack |
|||
⚫ | |||
swap r@ mod^ \ s d a -- s, a^d (mod n) |
|||
dup 1 = \ a^d == 1 (mod n) => Fermat pseudoprime |
|||
if 2drop rdrop true |
|||
else r> rot fermat-square-test |
|||
then ; |
|||
create small-prime-bases 2 , 7 , 61 , \ deterministic up to mr-det-3 |
create small-prime-bases 2 , 7 , 61 , \ deterministic up to mr-det-3 |
||
Line 1,565: | Line 1,583: | ||
: miller-rabin-primality-test ( n -- f ) |
: miller-rabin-primality-test ( n -- f ) |
||
dup miler-rabin-bases |
dup miler-rabin-bases cells bounds do |
||
dup i @ strong-fermat-pseudoprime? invert |
|||
⚫ | |||
if drop false unloop exit then |
|||
cell +loop drop true ; |
|||
i @ d n mod^ dup to x 1 <> |
|||
⚫ | |||
begin 1+ dup s < x n 1- <> and while |
|||
⚫ | |||
repeat drop |
|||
x n 1- <> |
|||
if false unloop exit |
|||
⚫ | |||
then |
|||
⚫ | |||
⚫ | |||
: prime? ( n -- f ) |
: prime? ( n -- f ) |