BW results
From: Cristiano (cristiano.pi_at_NSquipo.it)
Date: 12/17/04
- Next message: Mok-Kong Shen: "Re: [Lit.] Buffer overruns"
- Previous message: Andrew Swallow: "Re: C v. Ada (was Buffer Overruns)"
- Next in thread: Phil Carmody: "Re: BW results"
- Reply: Phil Carmody: "Re: BW results"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Fri, 17 Dec 2004 14:51:43 GMT
Using the Baillie-Wagstaff improved version of the strong Lucas pseudoprime
test, I tested all the odd composite numbers from 13 to 2^33 and from 2^34
to 2^35.
5027 of them were (erroneously) declared prime.
1) As already known, all the composite numbers declared prime by the BW test
were declared composite by MR test with base 2.
Afaik, that was known for the numbers up to 25e9. I seen that also for the
numbers up to 2^35 (about 34e9).
I also randomly tested 100 to 200-bit numbers and I seen the same.
I'd say that it's very likely that the conjecture holds for any odd number,
but unfortunately we don't have the proof.
2) Let N a composite declared prime by BW. I seen this:
N mod 6 Composites found
1 803 15.97%
3 21 0.42%
5 4203 83.61%
4203 composites (declared primes) were congruent to 5 modulo 6. We also see
a small amount of numbers congruent to 3 mod 6 (which will be discarded
using 3 in trial division).
Afaik, there is 50% of primes congruent to 1 mod 6 and 50% congruent to 5
mod 6, then I could think to test only the numbers congruent to 1 mod 6.
Could that lead to some kind of weakness in the crypto protocols?
Please, take a look to this graph (it's just a 24 kB gif image):
http://www.webalice.it/cristiano.pi/MR%20vs%20BW.gif
In the graph we can see that the probability of MR with 1 round it is better
than BW and it seems even better as the number gets bigger.
Moreover, my implementation of MR is about 6 times faster than BW, this
means that the BW test is equivalent to 6 rounds of MR, but the probability
to fail for MR with 6 rounds is much smaller.
The graph shows all these probability and it's clearly showed (the image is
scaled, but I hope it's clear enough) that the upper bound for MR with 6
rounds is much smaller than the BW with the numbers congruent to 1 mod 6
only.
The upper bound for MR with t rounds is showed on page 3, lemma 3:
http://www.ams.org/mcom/1996-65-213/S0025-5718-96-00695-3/S0025-5718-96-00695-3.pdf
Now there are several options, but I thought to this:
1) choose a random odd number N;
2) if N = 5 mod 6 go to 1;
3) trial division (this discards also N = 3 mod 6);
4) do a base 2 MR test;
4a) optionally do n MR tests with random bases from 3 to N-2;
5) if it declares "prime" do the BW test;
6) if it declares "prime" it is extremely unlike that N is composite.
[The steps 1 to 3 can be optimized, but here it is not important.]
The step 4a could be done using n = 3 or 4, this way, if the conjecture
"2-SPRP + BW" will be disproven (altought I don't think so), the probability
for a crypto sized number to be composite will be anyway astronomically
small.
Any comment?
Cristiano
- Next message: Mok-Kong Shen: "Re: [Lit.] Buffer overruns"
- Previous message: Andrew Swallow: "Re: C v. Ada (was Buffer Overruns)"
- Next in thread: Phil Carmody: "Re: BW results"
- Reply: Phil Carmody: "Re: BW results"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
