Re: primality

Ertugrul Soeylemez wrote:
Bryan Olson (07-04-01 18:20:19):

Trying whether RSA works is equivalent to Fermat's test. Doing
Fermat tests alone is discouraged. Yes, Carmichael numbers are
seldom, but consider this: Since a Miller-Rabin employs two modular
exponentiations, where Fermat employs only one, a Fermat interation
is twice as fast as a Miller-Rabin iteration.

I think there's a mistake in either your implementations or your
analysis of them. With a random base, the speed of the two tests
differs only trivially.

If implemented correctly, Miller-Rabin requires only a few more
squarings, yes. But that even supports my statement that M-R is more
useful in practice.

Sebastian Gottschalk explained how to use Fermat and Miller-Rabin.
I was unclear on why you were following that, but whatever the
reason the mistaken analysis seemed worth noting.

A quick Fermat test is one with a low base, usually 2. Miller-Rabin
requires a random base to support the proof that the chance of a
composite passing one round is less than 1/4.

A quick Fermat test has still some low but considerable probability of
giving a wrong answer. And the base of M-R does not need to be random
completely. Choosing a random single-word base will suffice, and is
fast.

With a random base, I know the theorem that for any composite the
chance of a k M-R iterations not finding the number to be composite
is less than (1/4)**k. Can you show or cite the proof that the
same still holds when we use single-word bases?

By the way, you don't regenerate your keys very frequently, so what's
better? Performance or security? I wouldn't trade security for a speed
improvement in the milliseconds range for something, which you don't do
often anyway.

That has nothing to do with the issue here. For any amount of work
we may choose expend in generating primes, doing the initial weed-out more efficiently leaves us more time to certify the final primes.

But on the other hand, each Miller-Rabin iteration with a negative
(i.e. not composite) result lowers the probability of the number
being composite by a factor of 4, where Fermat lowers it only by 2.
And as an extra, it does detect Carmichael numbers.

That's a sloppy statement about M-R, and, unless you know of some
relevant theorem unknown to me, a wrong claim about the Fermat test.

The maximum probability. Sorry for not being specific enough. Or which
statement are you referring to?

That a Fermat iteration with a not-found-composite result lowers the
probability of the number being composite by a factor of 2. Where's
the proof of that? Don't Carmichael numbers show that it is false?


--
--Bryan
.

Relevant Pages

  • Re: primality
    ... probability, and the contrary being proven when the RSA or whatever ... Rabin-Miller is for ensuring corner cases like Carmichael numbers, ... Trying whether RSA works is equivalent to Fermat's test. ... Doing Fermat ...
    (sci.crypt)
  • Re: Seeking efficient sequential-Carmichael-number generator
    ... Short: Search for Carmichael Numbers ... which cheat the Fermat Test. ... Prozedur zur Berechnug der Potenz einer Zahl modulo m. ... (define (carmichael-bis-iter zaehler obergrenze) ...
    (sci.math)
  • Re: Conjectures with very large lowest counterexamples
    ... quoteint obtained when F_5 is divided by 641, which IIRC is also prime). ... That Fermat numbers suddenly switch from prime to composite at n = 5 is ... being composite, so to speak). ... F_5 is the first Fermat number where so ...
    (sci.math)
  • Re: primality
    ... probability, and the contrary being proven when the RSA or whatever ... Trying whether RSA works is equivalent to Fermat's test. ... Doing Fermat ... the chance of a composite passing one round is less than 1/4. ...
    (sci.crypt)
Quantcast