- 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 informat
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 r
>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:
Granted this is only a test of the
generation of 128 numbers, but I got 128 primes (based on 128 MR rounds).
That doesn
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 y
- 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 =
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
- 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 correct
* 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: [J
- 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 t
-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 crypto
- 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 thi
>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 H
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 2^
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 fa
> > 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
- 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 de
>> 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 pr
>> 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
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 Carmic
On Tue, 8 Nov 2005, Jeremiah Rogers wrote:
> > 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?
> [...]
> To me it looks like M-R just eliminates some need
> 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
23 matches
Mail list logo
