The Essay
http://www.jsoftware.com/jwiki/Essays/Primality_Tests
contains an implementation of the probabilistic Miller-Rabin test on an
integer n. This depends on testing potential witnesses for the
compositeness of n. If any witness is found, n is composite; if you test
a lot and don't find one, n is probably prime.
The potential witnesses for all numbers in a range can be reduced to a
small number. This allows for a deterministic version of the test, which
may be somewhat faster.
time=:6!:2
huo=: <[EMAIL PROTECTED]:^:(0=2&|)^:a: NB. halve until odd
MillerRabin=: 100&$: : (4 : 0) " 0
d=. {:s=. huo y-1
e=. 2x^#s
for_a. 1+x [EMAIL PROTECTED] y-1 do.
if. 1~:(a y&|@^ d) y&|@^ e do. 0 return. end.
end.
1
)
NB. Deterministic Miller-Rabin
DMR=: 3 : 0"0
if. (73>:y)+.(y>:3e14) do. MillerRabin y return. end.
d=. {:s=. huo y-1
e=. 2x^#s
for_a. 2 3 5 7 11 13 17 31 61 73 do.
if. 1~:(a y&|@^ d) y&|@^ e do. 0 return. end.
end.
1
)
N=:1000 [EMAIL PROTECTED] 2e10
time'a=:MillerRabin N'
1.28576
time'b=:DMR N'
0.326521
a-:b
1
The basis set can be much smaller if the range of y is restricted further.
For example, if y<9e6, you only have to test for_a. 31 73 .
Best wishes,
John
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
