Thanks. I'll incorporate the ideas into the essay. Do you have a proof that potential witnesses are limited for y in a smaller range?
----- Original Message ----- From: John Randall <[EMAIL PROTECTED]> Date: Thursday, October 30, 2008 7:02 Subject: [Jprogramming] Miller-Rabin primality test To: [email protected] > 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 . ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
