🚀 go-pugleaf

In article <1465@ttrdc.UUCP>, levy@ttrdc.UUCP (Daniel R. Levy) writes:
> 
> Wai-wai-wait... an earlier posting in this group showing a method that
> purported to be based on Lenstra's theorem simply produced a big number which
> is PROBABLY prime, to a degree of probability asymptotically approaching 100%
> depending on the number of iterations successfully passed in the test.  How
> is this different from the statement below "And if you don't mind the pos-
> sibility of error (which you can make very small)..."?
> 

I didn't see the earlier posting you refer to, but any test based on Lenstra's
theorem is not ramdom, so any number of iterations above 1 is meaningless (and
surely doesn't increase the "accuracy" of the test).

The other interesting thing about Lenstra's theorem is that it *guarantee's*
the result.  i.e., if it says a number is prime, then the number *is* prime --
no possibility of error.  If interested I'll post what the theorem says... It's
kinda cute, but if you want a good discussion of it, see Cohen and Lenstra's
paper.  Actually a better presentation is given by Dixon in his survey on
primality testing.  Don't remember exactly where this came out, but if anybody
is interested, send me a letter and I'll look it up.

-- 
Steve Tate			UUCP: ..!{ihnp4,decvax}!duke!srt
				CSNET: srt@duke
				ARPA:  srt%duke@csnet-relay