Re: Fermat's primality test vs. Miller-Rabin

2005-12-06 Thread Sidney Markowitz
Joseph Ashwood wrote: Apparently, they are, I'm ran a sample, but even with the added second sanity check, every one of them that passes a single round comes up prime. I then proceeded to move it to 2048-bit numbers. It takes longer and the gaps between primes is averaging around 700 right

Re: Fermat's primality test vs. Miller-Rabin

2005-12-06 Thread Joseph Ashwood
- Original Message - From: Anton Stiglic [EMAIL PROTECTED] Subject: RE: Fermat's primality test vs. Miller-Rabin Ok after making that change, and a few others. Selecting only odd numbers (which acts as a small seive) I'm not getting much useful information. It appears

Re: Fermat's primality test vs. Miller-Rabin

2005-12-05 Thread Sidney Markowitz
Joseph Ashwood wrote: Granted this is only a test of the generation of 128 numbers, but I got 128 primes (based on 128 MR rounds). That doesn't make sense, unless I'm misinterpreting what you are saying. Primes aren't that common, are they? I don't have time right now to look for a bug in

Re: Fermat's primality test vs. Miller-Rabin

2005-12-05 Thread Joseph Ashwood
- Original Message - From: Sidney Markowitz [EMAIL PROTECTED] Subject: Re: Fermat's primality test vs. Miller-Rabin Joseph Ashwood wrote: Granted this is only a test of the generation of 128 numbers, but I got 128 primes (based on 128 MR rounds). That doesn't make sense, unless I'm

RE: Fermat's primality test vs. Miller-Rabin

2005-12-05 Thread Anton Stiglic
Ok after making that change, and a few others. Selecting only odd numbers (which acts as a small seive) I'm not getting much useful information. It appears to be such that at 512 bits if it passes once it passes 128 times, and it appears to fail on average about 120-130 times, so the sieve

Re: Fermat's primality test vs. Miller-Rabin

2005-12-04 Thread Joseph Ashwood
- Original Message - From: Sidney Markowitz [EMAIL PROTECTED] Subject: Re: Fermat's primality test vs. Miller-Rabin Joseph Ashwood wrote: byte [] rawBytes = new byte[lenNum/8]; rand.nextBytes(rawBytes); curNum = new BigInteger(rawBytes); curNum = BigInteger.ONE.or(new

Re: Fermat's primality test vs. Miller-Rabin

2005-12-03 Thread Sidney Markowitz
Joseph Ashwood wrote: byte [] rawBytes = new byte[lenNum/8]; rand.nextBytes(rawBytes); curNum = new BigInteger(rawBytes); I haven't thought through why it would produce non-primes, but it doesn't seem to do what you want. That produces a 512 bit twos-complement number, which gives you a

Re: Fermat's primality test vs. Miller-Rabin

2005-12-02 Thread Nicolas Rachinsky
* Joseph Ashwood [EMAIL PROTECTED] [2005-11-22 02:50 -0800]: - Original Message - From: Anton Stiglic [EMAIL PROTECTED] Subject: RE: Fermat's primality test vs. Miller-Rabin -Original Message- From: [Joseph Ashwood] Subject: Re: Fermat's primality test vs. Miller-Rabin

Re: Fermat's primality test vs. Miller-Rabin

2005-12-02 Thread Joseph Ashwood
- Original Message - From: Nicolas Rachinsky [EMAIL PROTECTED] Subject: Re: Fermat's primality test vs. Miller-Rabin * Joseph Ashwood [EMAIL PROTECTED] [2005-11-22 02:50 -0800]: 16384 times .. If I remember the proof of MR correctly it assumes an odd number. Were

RE: Fermat's primality test vs. Miller-Rabin

2005-11-30 Thread Anton Stiglic
-Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Joseph Ashwood Sent: November 18, 2005 3:18 AM To: cryptography@metzdowd.com Subject: Re: Fermat's primality test vs. Miller-Rabin Look at table 4.3 of the Handbook of applied cryptography: for t = 1

Re: Fermat's primality test vs. Miller-Rabin

2005-11-30 Thread Joseph Ashwood
- Original Message - From: Anton Stiglic [EMAIL PROTECTED] 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

Re: Fermat's primality test vs. Miller-Rabin

2005-11-18 Thread Joseph Ashwood
- Original Message - From: Anton Stiglic [EMAIL PROTECTED] Subject: RE: Fermat's primality test vs. Miller-Rabin The general consensus is that for 500-bit numbers one needs only 6 MR tests for 2^{-80} error probability [1]: My own tests disagreed with this, 512-bits seemed to have

RE: Fermat's primality test vs. Miller-Rabin

2005-11-16 Thread Anton Stiglic
The general consensus is that for 500-bit numbers one needs only 6 MR tests for 2^{-80} error probability [1]: ... and thus a single test gives ~2^{-13}. If you just took the exponent 80 and divided it by 6 to get ~13, I don't think that is the right reasoning. Look at table 4.3 of the

Re: Fermat's primality test vs. Miller-Rabin

2005-11-15 Thread Hal Finney
Ron Rivest reported on some theoretical and practical experimental work in Crypto 90, Finding Four Million Large Random Primes, http://theory.lcs.mit.edu/~rivest/Rivest-FindingFourMillionLargeRandomPrimes.ps A number n is a (base two) pseudoprime if it is composite and satisfies the identity

Re: Fermat's primality test vs. Miller-Rabin

2005-11-14 Thread Travis H.
Although the Carmichael numbers fool the Fermat test (that is, $a^{n-1} = 1 (n)$) for *all* a, I thought it would work properly if a shares a factor with n. Yes I guess the difference is that with MR you are trying to find a number that is *likely* a prime, whereas with Fermat you are

Re: Fermat's primality test vs. Miller-Rabin

2005-11-14 Thread Alexander Klimov
On Fri, 11 Nov 2005, Joseph Ashwood wrote: From: Charlie Kaufman [EMAIL PROTECTED] I've heard but not confirmed a figure of one failure in 20 million. I've never heard an estimate of the probability that two runs would fail to detect the composite. It couldn't be better than one failure is 20

Re: Fermat's primality test vs. Miller-Rabin

2005-11-13 Thread Joseph Ashwood
- Original Message - From: Charlie Kaufman [EMAIL PROTECTED] Subject: FW: Fermat's primality test vs. Miller-Rabin In practice, the probability of randomly choosing a Carmichael number of size 250 bits is vanishingly small. I would say that finding any Carmichael number without

Re: Fermat's primality test vs. Miller-Rabin

2005-11-10 Thread Jeremiah Rogers
I guess the small increase in efficiency would not be worth additional program code. That depends on the size of the numbers you're working with... Considering the research that goes into fast implementations of PowerMod I don't think the required computation is trivial. Although the

Re: Fermat's primality test vs. Miller-Rabin

2005-11-10 Thread Alexander Klimov
On Wed, 9 Nov 2005, Jeremiah Rogers wrote: I guess the small increase in efficiency would not be worth additional program code. That depends on the size of the numbers you're working with... Considering the research that goes into fast implementations of PowerMod I don't think the

Re: Fermat's primality test vs. Miller-Rabin

2005-11-10 Thread Anton Stiglic
I guess the small increase in efficiency would not be worth additional program code. That depends on the size of the numbers you're working with... Considering the research that goes into fast implementations of PowerMod I don't think the required computation is trivial. Although the

Re: Fermat's primality test vs. Miller-Rabin

2005-11-10 Thread Anton Stiglic
Although the Carmichael numbers fool the Fermat test (that is, $a^{n-1} = 1 (n)$) for *all* a, there are no such things for the Miller-Rabin test: for any odd composite n at least 3/4 of a's fail the test, that is if you made m MR tests with random a's then you are mistaken with probability

Re: Fermat's primality test vs. Miller-Rabin

2005-11-08 Thread Jeremiah Rogers
It appears that Fermat's test can be fooled by Carmichael numbers, whereas Miller-Rabin is immune, but I'm not sure why. Where does it say Miller-Rabin is immune to Carmichael numbers? It seems confusingly worded and says that Fermat's Test is not immune to Carmichaels, but this does not imply