Thank you. Regarding
> I have not experimented extensively,but performance may be
> increased by not evaluating the full expression
>
> (+./c=n-1) +. 1={:c=. a n&|@^ huo n-1
>
> since you can reject a basis element if any element of c is n-1.
This is a case where I went for clarity of exposition
rather than the last ounce of efficiency. Implementation
in a scalar language (such as C) would do something
different, including avoiding the calculation of all the powers,
and exploiting the fact that the exponents are d*2^i.s .
(First calculate a^d and then do repeated squaring.)
In J that would require the special code for +./@:f that
I mentioned several days ago.
I learned something in this thread: there is something
(a-SPRP) faster than trial division for small numbers (n<3e14).
In contrast, trial division on _1+2^31 requires about 4800 divisions.
----- Original Message -----
From: John Randall <[EMAIL PROTECTED]>
Date: Monday, November 3, 2008 16:18
Subject: Re: [Jprogramming] Miller-Rabin primality test
To: Programming forum <[email protected]>
> Roger Hui wrote:
> > I note that certain statements in
> > http://primes.utm.edu/prove/prove2_3.html
> > are incorrect.
>
> Roger:
>
> I agree with your analysis. Testing all numbers 73 < n
> < 9,080,191 gives
> the non-primes 946 596926 6376126, and as stated, the bullet
> point is
> false.
>
> To make it true, we have to do the following:
>
> - We only test odd numbers. This is mentioned near the top
> of the page,
> but then ignored.
>
> - We can only test numbers against basis elements smaller than
> the number.
> This point does not arise in most of Jaeschke's paper,
> since he is
> looking at consecutive small primes. The results quoted in
> the web page
> occur almost as an afterthought to main results of the paper.
>
> Despite the flaws in the exposition, I believe this approach can
> still be
> made into a useful primality test. I have not experimented
> extensively,but performance may be increased by not evaluating
> the full expression
>
> (+./c=n-1) +. 1={:c=. a n&|@^ huo n-1
>
> since you can reject a basis element if any element of c is n-1.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
