Re: Elementary group theory: Proof of Fermat-Maas primality-test (was: correcting *** ...)

In article <rem-2007jan22-004@xxxxxxxxx> rem642b@xxxxxxxxx (robert maas, see http://tinyurl.com/uh3t) writes:
From: "*** T. Winter" <***.Win...@xxxxxx>
....
Well, trial division does not take much time (0.051 seconds on this
slow Sun). Moreover, in that time also small divisors of p-1 and
p+1 are found, and they are used in a later Lucas-Lehmer test, which
also determines some of the flags used in APR-CL.

Let's make clear some assumptions:
- You don't know ahead of time whether the number is prime or
composite. It could be either. In fact in a majority of cases it
is in fact composite.

Right. Otherwise I would not test it.

- You are doing trial division by an algorithm that is linear in
the number of digits in the bignum dividend, and which returns
the remainder as a single-word integer, never buildig the
quotient at all in the process. For example, you break up the
bignum dividend into chunks of several bits each, perform a MOD
operation on the highest order piece, then shift that remainder
to left and add the next chunk of the dividend, etc., until at
the end the last remainder is the true bignum .mod. trialDivisor
value.

Right.

- So the way you do trial division to test both p-1 and p+1 at the
same time is first compute p-1 mod trialDivisor, then check
whether it's exactly 0 or 1 or 2. Checking all three values is
hardly any more time than checking just one. The real compute
cycles were consumed in computing the bignum remainder in the
first place.

And again right.

- The chance that p-1 has a factor of trialDivisor is expected to
be 1/trialDivisor. Likewise the chance that p has a factor of
trialDivisor is expected to be 1/trialDivisor. Likewise the
chance that p+1 has a factor of trialDivisor is expected to be
1/trialDivisor. So the value you can expect to get by a single
trial division is 3/trialDivisor, 1.5 times as much as if you
were only testing p having a factor and collecting factors of p-1.

Eh?

- The whole purpose of this primality-test is to filter non-primes
out from randomly generated numbers.

Wrong. It is also used to gather information about small divisors of
p-1 and p+1. Moreover, this is a generic primality proving algorithm.
Whether the number is randomly generated or not has no influence.

If a number is composite,
you want to eliminate it as soon as you possibly can so you can
get on with testing other numbers. You don't want to waste
unnecessary time doing worthless trial division on a non-prime
when a single Fermat test would have shown it non-prime faster.

But you do not know whether a single Fermat test would show that. And
as you have use of the small divisors of both p-1 and p+1 later, it
comes in pretty usefil.

Therefore for reasonably big numbers (one or two hundred digits)
being tested to see if they are suitable for use as p or q in a RSA
cryptosystem,

The program is not used to test whether the primes are suitable in some
system; it is used to prove whether a number is prime or not. It was
specifically designed to prove whether some (large) numbers in the
Cunningham tables for which it was not known whether they were composite
or not, to give a proof of either.

the threshold for stopping trial division and just
doing one Fermat test before proceeding with whatever else you want
to do, is only a factor of 1.5 greater than what I estimated.
There's no way it's efficient to do trial division all the way to
100,000 before doing the first Fermat test.

But it gets smallish factors of p-1 and p+1 that are useful later.

After you've done a single Fermat test with a random base in the
interval [2,n-2], and gotten it satisfied, you might as well
immediately proceed to the too-many-roots test and the
remaining-factor-of-(p-1)-primality test, in whichever order you
want.

And if the remaining-factor-of-(p-1)- is not prime?

If the remaining factor of (p-1) is prime, the you can run
the Fermat-Maas test immediately.

When doing my generation of a random prime of 120 digits, I scanned
over 294 candidates. In 256 cases the number did not survive trial
division, the largest divisor found was 55717. The time needed for
this one was 0.048 seconds. A pseudo-prime test uses about 0.046
seconds. The complete set of primes upto 100,000 takes about 0.080
seconds. One candidate did also survive the pseudo prime test.

In that case the remaining factor was:
28988632716339269019731982692336680940408646961327424290384644373248\
10095465363511659807695206555579326234594280889
I do know it is not prime, but I do not know factors at all. If we
look again at p-1, the remaining factor is
33243844858187235114371539784789771720652118074916770975211748134458\
83137001563660160329925695591260695223158579
again not prime. We continue and we go through the series of composites:
13056258290074320601041371370980194690382577203250636625250077815748\
5002631433652508064171145062888252895419

29174470244018149817938387800452992529357285287780206074589748695273\
6045258211932067253940299

40338452724160620945672877478592658134116616501100509764506278218329\
6801574809618427

27373762871988263972343266933098100494795071228801949773764393453563\
69246777

80482074786671742403922454443758320516759348658171461568092745453237

and finally the prime
1076366484602147092546975531532636822831532507598719595143807113

But try to prove it prime. The original number is:
1234567890123456789012345678901234567890123456789012345678901234567890\
12345678901234567890123456789012345678901234500733

I would even like to see how you prove that the last number in the series
is prime.

In any case, you probably have a
sizeable collection of small prime factors of (p-1) from trial
division, and testing for GCD involving powers of the base short by
each of the small primes will surely produce a nontrivial factor if
it's not prime.

Try it on the numbers above. The sizeable collection of small prime
factors is, indeed, sizeable. At most some 8 factors smaller than
100,000.

If no such nontrivial factor turns up, the you have
high confidence the number really is prime and doing a lot more
trial division to find ever more factors of p-1 and p+1 is almost
certain to be not a waste. But after a while it's probably better
to attack min((p-1)/allKnownSmallFactorsOf(p-1),
(p+1)/allKnownSmallFactorsOf(p+1))
with a quadradic sieve instead of more trial division.

The quadratic sieve is an extremely expensive way to prove a number
prime.

Or punt if both remaining unfactored but known composite quotients
are each so large they'd be too hard to factor even with quadradic
sieve.

But the above large number takes only about 9 seconds to prove prime on
this fairly slow Sun. So why should I punt?

So you and I
never accidently give customers the same primes where they might
know each other's secret key.

You should not give your customers two primes. You should give your
customer the product of two primes and two exponents, one of them
must be secret.
--
*** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~***/
.