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

From: "*** T. Winter" <***.Win...@xxxxxx>
The program I am using for primality tests initially does trial
division by primes upto 100,000; next it performs Fermat for a
single number; ...

I got to thinking about that, whether it's really cost effective to
do trial division up to such a high divisor.
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.
- 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.
- 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.
- 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.
- The whole purpose of this primality-test is to filter non-primes
out from randomly generated numbers. 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.
If any of those assumptions are seriously flawed, let me know and I
can backtrack. Assuming you agree with all the above:

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 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.

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. If the remaining factor of (p-1) is prime, the you can run
the Fermat-Maas test immediately. 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. 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.

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. Just say that number is probably prime but it'd be too hard
to prove it to be worth the expense, so just dismiss it and find
another prime easier to prove prime because p-1 and/or p+1 is
easier to mostly-factorize. It's like fishing to eat, when you
don't care about the big fish that's too hard to reel in, you just
let it go and catch a medium sized fish that comes next, and you
won't waste a week on that too-big fish and starve in the mean time.

We could run businesses: You generate only primes whose p-1 and p+1
are easy to partly factorize just enough for the super-duper
primality test to work. I directly synthesize p-1 as a product,
such that I generate only primes whose p-1 and p+1 are very very
difficult to factor, hardly any small factors at all. So you and I
never accidently give customers the same primes where they might
know each other's secret key.
.