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
- 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
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
- 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
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
- 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
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
* 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
- 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
-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
- 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
- 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
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
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
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
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
- 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
* 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
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
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
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
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
(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
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
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
25 matches
Mail list logo
