Fermat's primality test vs. Miller-Rabin

[Joseph Ashwood]

----- Original Message ----- 
From: "Anton Stiglic" <astiglic at okiok.com>
Subject: RE: Fermat's primality test vs. Miller-Rabin


> -----Original Message-----
> From: [Joseph Ashwood]
> Subject: Re: Fermat's primality test vs. Miller-Rabin
>>I think much of the problem is the way the number is being applied. Giving
>>a stream of random numbers that have passed a single round of MR you will
>>find that very close to 50% of them are not prime, this does not mean that
>>it passes 50% of the numbers (the 2^-80 probability given above is of this
>>type).
>
> Do you do an initial sieving to get rid of the more obvious primes?

No I did not, since this was specifically to test the effectiveness of MR I 
determined that it would be better to test purely based on MR, and not use 
any sieving. The actual algorithm was:


16384 times
{
    question = random 512-bit number
    //this is not the most efficient, but it should remove bias making this 
just MR
    while(question does not pass a single round of MR) question = random 
512-bit number
    127 times
    {
        perform an MR round
        log MR round result
    }
}

Then I performed analysis based on the log generated. I will gladly disclose 
the source code to anyone who asks (it's in Java).

> I'm
> guessing you don't since you seem to have a result contradictory to what 
> has
> been proven by Damgard, Landrock and Pomerance.  If you look at table 4.3 
> of
> HAC (which comes from Damgard & al. paper), it says that if your 
> candidates
> come from a uniform random distribution, then for 500 bit candidate, the
> probability that a candidate n is composite when one round of miller-Rabin
> said it was prime is <= (1/2)^56.  You are finding that the probability is
> about 1/2, that seems very wrong (unless you are not doing the sieving,
> which is very important).  Am I misunderstanding something?

No you're not. The seiving is important from a speed standpoint, in that the 
odds improve substantially based on it, however it is not, strictly 
speaking, necessary, MR will return a valid result either way.

>>In fact it appears that integers fall on a continuum of difficulty
>>for MR, where some numbers will always fail (easy composites), and other
>>numbers will always pass (primes). The problem comes when trying to denote
>>which type of probability you are discussing.
>
> Well I think I explained it pretty clearly.  I can try to re-iterate.  Let 
> X
> represent the event that a candidate n is composite, and let Y_n denote 
> the
> event that Miller-Rabin(n,t) declares n to be prime, where 
> Miller-Rabin(n,t)
> means you apply t iterations of Miller-Rabin on n.
> Now the basic theorem that we all know is that P(Y_t | X) <= (1/4)^t (this
> is problem in one of Koblitz basic textbooks on cryptography, for 
> example).
> But this is not the probability that we are interested in, we are (at 
> least
> I am) more interested in P(X | Y_t).  In other words, what is the
> probability that n is in fact composite when Miller-Rabin(n, t) declared n
> to be prime?  Do we agree that this is the probability that we are
> interested in?

If we are discussing that aspect, then yes we can agree to it. That is the 
probability I gave, at exactly a single round (i.e. no sieving involved), 
approaching 1/2 (my sample was too small to narrow it beyond about 2 
significant digits). I know this result is different from the standard 
number, but the experiment was performed, and the results are what I 
reported. This is where the additional question below becomes important 
(since it gives how quickly the odds of being incorrect will fall).


>>What are the odds that a
>>random 512-bit composite will be detected as composite by MR in one round?
>>I don't think anyone has dependably answered that question, but the answer
>>is very different from 1-(probability that MR-* says it's a prime)^-k. Any
>>discussion needs to be more accurately phrased.
>
> You are looking for P( Comp Y_t | X), where Comp Z is the complementary
> event of Z. In our case, Comp Y_t is the event that Miller-Rabin(n,t) 
> proves
> n to be composite. Is that what you are looking for?

Actually I'm not, the probability is a subtley different one and the key 
different is in Y. Instead it is given random composite RC what is P(MR(RC, 
k) | Comp X). This appears to me to be a complex probability based on the 
size of the composite. But this is the core probability that governs the 
probability of composites remaining in the set of numbers that pass MR-k. 
Fortunately, while it is a core probability, it is not necessary for MRs 
main usefulness. Performing log_2(N)/4 rounds of MR appears to be a solid 
upper bound on the requirements, and as this is the probability given by 
Koblitz, and the most common assumption on usage it is a functionable 
substitute.

>>For example, my phrasing is that in the tests that I performed 50% (+/-
>>experimental noise) of those numbers that passed a single round of MR also
>>passed 128 rounds, leading me to conclude that 50% of the numbers that
>>passed a single round of MR are in fact prime. Since each number that
>>passed a single round was subjected to 127 additional rounds, a number of
>>additional statistics can be drawn, in particular that of those that 
>>failed
>
>>at least one round none failed less than 40 rounds, and that few passed
>>less than 40 rounds. Due to the fact that this was only iterated 65536
>>times there is still substantial experimental error available. These 
>>pieces
>>of information combined indicate that for 512-bits it is necessary to have
>>80 rounds of MR to verify a prime.
>
> I don't understand what you are trying to point out.  If you chose your
> candidates uniformly at random, do the sieving before applying the
> Miller-Rabin tests, then for 512 bit number it is sufficient to apply 5
> rounds to get probability of error lower than (1/2)^80.

But that would be entirely insufficient to isolate MR, which is what I was 
discussing. Including sieving does speed up the process enormously, but it 
fails to discuss what the actual behaviors of MR alone are, a very critical 
difference.

> You should take a look at Damgard & al's paper, they did a very good
> analysis.

And I'm saying that if you have accurately represented their analysis, their 
analysis does not apply to MR itself, but on a combination of MR with other 
techniques. As such it is not a valid analysis of MR alone.
                Joe 



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com