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

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

- 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

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

- 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

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

- 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

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

* 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

- 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

-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

- 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

- 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

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

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

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

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

- 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: FW: Fermat's primality test vs. Miller-Rabin

* Charlie Kaufman: The probability of a single run of Miller-Rabin or Fermat not detecting that a randomly chosen number is composite is almost vanishingly small. How do you chose a random integer, that this, based on which probability distribution? 8-) Anyway, one can show that for some

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

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

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

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

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

### FW: Fermat's primality test vs. Miller-Rabin

(resending after bounce) -Original Message- From: Charlie Kaufman Sent: Tuesday, November 08, 2005 3:11 PM To: 'Travis H.'; 'cryptography@metzdowd.com' Subject: RE: Fermat's primality test vs. Miller-Rabin Is that the distinction that makes Miller-Rabin a stronger primality test? Yes

### Fermat's primality test vs. Miller-Rabin

In Practical Cryptography, Schneier states that the you can prove that when n is not a prime, a certain property of a mod n holds for at most 25% of possible values 1 a n. He later states that Fermat's test can be fooled by Carmichael numbers, and finally he basically says that Miller-Rabin is

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

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