NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/programm/3098

Internet Message Format | 1992-11-10 | 1.6 KB

Path: sparky!uunet!pipex!unipalm!uknet!root44!hrc63!mrcu!uk.co.gec-mrc!paj
From: [e-mail]-mrc (Paul Johnson)
Newsgroups: comp.programming
Subject: Probabilistic Prime Numbers
Message-ID: <2185@snap>
Date: 10 Nov 92 17:07:33 GMT
Sender: [e-mail]-mrc
Reply-To: [e-mail]-mrc (Paul Johnson)
Organization: GEC-Marconi Research Centre, Great Baddow, Essex
Lines: 27

I am trying to write a small prime number generator using Algorithm P
in Knuth.

Note for those without a copy of Knuth: this algorithm uses a randomly
generated number to perform a primality test.  It can return one of
two results: "Not prime" or "Probably prime".  If the latter, then the
chance of error is < 0.25.  Repeated tests with different random
numbers can reduce this probability very quickly.

I cannot understand the discussion of this test in Knuth, nor can I
understand what his variables are.  Is `n' the number under test, or
is it `q'?  If the former, why the statement "Let n = 1 + (2^k)q" just
before the statement of Algorithm P.

What I would really like is some C or Pascal code which implements
Algorithm P.  Failing that, a restatement with a more careful
declaration of variables would be gratefully received.  Sedgwick and
Numerical Recipies do not deal with primes.  Can anyone help?

Thanks in advance,

Paul.

Paul Johnson ([e-mail]).        | Tel: [phone] ext 3245
--------------------------------------------+----------------------------------
These ideas and others like them can be had | GEC-Marconi Research is not
for $0.02 each from any reputable idealist. | responsible for my opinions