huo=: <[EMAIL PROTECTED]:^:(0=2&|)^:a: NB. halve until odd
NB. magic numbers from http://primes.utm.edu/prove/prove2_3.html
witnesses=: 4 : 0
r=. 9080191 4759123141 2152302898747 3474749600383 341550071728321x
if. y>:{:r do.
1+x [EMAIL PROTECTED] y-1
else.
((r-1) I. y){:: 31 73 ; 2 7 61 ; 2 3 5 7 11 ; 2 3 5 7 11 13 ; 2 3 5 7 11 13
17
end.
)
NB. Miller-Rabin primality test
NB. deterministic for y< {:r (3.4e14) in witnesses; probabilistic for y>:{:r (0
answer is always correct;
NB. 1 answer is wrong with error probability at most 0.25^x)
MillerRabin=: 100&$: : (4 : 0) " 0
if. 0=2|y do. 2=y return. end.
if. 74>y do. y e. i.&.(p:^:_1) 74 return. end.
e=. huo y-1
for_a. x witnesses y do. if. (+./c=y-1) +: 1={:c=. a y&|@^ e do. 0 return.
end. end.
1
)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
