Re: Prime picking

Robert Harley (Robert.Harley@inria.fr)
Wed, 20 Aug 1997 21:23:59 +0200 (MET DST)


Ainsi parla Mark Baker <markb@mrburns.iosphere.net>:
>> While away, I ran a program to prove 2^5000+2157 prime.
>Terribly cool.
>
>But I've gotta know this - how the hell does one even *think* to try that
>number for primeness. Psychic Friends Network? Rumpelstiltskin?

Using probabilistic compositeness tests based on Fermat's Little Theorem.

The latter says that if p is prime and 0 < x < p then x^(p-1) mod p = 1.

Given p, one chooses some x and tests the condition. If it fails p is
definitely composite.

Otherwise p might be prime but is not necessarily so since the
converse of the theorem does not hold. However if p was a randomly
chosen integer (using some non-weird distribution) and x was likewise
chosen, then p is quite likely to be prime (hence the misnomer
"probabilistic primality tests" used by many).

I checked p = 2^5000+n for n = 0,1,2... until a "probable prime"
popped up at n = 2157. That was the easy part. Then I ran the
primality prover on p. It uses some partial converses to generalised
versions of the theorem to turn "quite likely" into "definitely".

The previous record was a partition number 2^(4997 point something)
which is why I started at 2^5000.

I haven't tried Psychic Friends yet, though.

-- Rob.

PS: you DID ask!

.-. Robert.Harley@inria.fr .-.
/ \ .-. .-. / \
/ \ / \ .-. _ .-. / \ / \
/ \ / \ / \ / \ / \ / \ / \
/ \ / \ / `-' `-' \ / \ / \
\ / `-' `-' \ /
`-' Linux - 500MHz Alpha - 256MB SDRAM `-'