Re: Primes algorithm

mm_at_nospam.net
Date: 04/21/05 

Date: Thu, 21 Apr 2005 13:38:29 +0200

Lasse wrote:

>>>But that's a testing method, not synthesis. How does the
>>>encryption program (RSA implementation, I assume) find
>>>80-bit primes? I can't believe it just generates a random
>>>sequence until a pair turns up.
>>>
>>That's pretty much the way to do it.
>>Up where the 80-bit numbers live, roughly one number
>>in every 55 is prime. So pick some large N and test
>>N, N + 1, N + 2, ..., and you'll be quite unlucky if
>>you have to test more than 100 numbers before you find
>>one that's prime. Each test is fast, doing 100 doesn't
>>really take all that much time. And of course you can
>>save time by throwing out all the even numbers, multiples
>>of 3, etc., before you begin.
>>
>>
>
> Actually, there is no reason to try N, N+1, N+2 etc.

The poster was answering to someone who seems to be a total
beginner. Taking this in account, the way he answered is a
good way of doing it.

 
> Just pick a large number at random, test whether it is prime. If it's
> not, take another random number, and so on.
>
> It is known (by the *prime number theorem*) that the number of primes
> smaller than n is about n/log n, and it follows by a simple calculation
> that the expected time to find a prime is
> O(log n), so it won't take you too long.
>
> By the way, the algorithm of Agrawal, Kayal and Saxena is not, at the
> moment, the most efficient way to test for primality. The classical
> method which is generally used, as far as I know, is the Miller-Rabin
> algorithm, which is a randomized algorithm. If this algorithm tells you
> that a given number is composite, then it is definitely composite; when
> it outputs 'prime', it is prime with very high probability.

Here, you are confusing the OP. Yes, Miller-Rabin is a 'randomized'
test (assuming you use randomly chosen bases) but, overall, it is
a probabilistic test. And to nitpick a little more, it is not a
primality test but a compositeness test ;-)

 
> If your number is prime with probability 1 - 10^{-10},

A number is prime with a probability equal to either 0 or to 1.
And the fact that we don't know its status doesn't change this
probability. (Yes, I know what you wanted to say ;-)

> this is usually
> good enough. If you want to be sure, you can always run the
> AKS-algorithm (or some of the randomized primality provers which were
> previously known)

Are you saying that, before AKS, there were no deterministic
primality tests?

> to make sure that this is correct --- i.e., use the
> more efficiennt Miller-Rabin test to throw away all the composites you
> come across, and then double-check using another algorithm to know
> you've definitely got a prime.

If you want to check crypto-primes with a probabilistic
compositeness test, use the BPSW (Baillie-Pomerance-Selfridge-
Wagstaff) test. It is faster than Miller-Rabin used with more than
three bases, and, overall, it is more reliable.

mm

Relevant Pages

  • Re: Primality tests and ERH
    ... Are you comparing the Solovay-Strassen test to the Miller test? ... if r!= s return composite. ... The Miller-Rabin test is based on the fact that if n is prime, ... Rabin presented Miller's algorithm in a form that resembles ...
    (sci.crypt)
  • Re: EFFICIENCY: PRIME TEST vs PRIME GENERATOR
    ... > Let's suppose we have an algorithm that will take a positive ... > For example, the USUAL test runs on odd numbers, checking for primality. ... > The time it takes to prove one such number is either composite or prime is ... > you DON'T use every partition, you might require very large exponents. ...
    (sci.math)
  • Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
    ... probability of mathematical failure just means that you are getting your ... contract for an algorithm, then it should do that, ... adverse effect is less than chance of all of you spontaneously ...
    (sci.crypt)
  • Re: Towards a Formula for Primes
    ... did the OP prove that this algorithm always makes primes? ... which are either composite, or not necessarily prime ... it certainly comports to Big Peak Oil's statistics -- ...
    (sci.math)
  • Re: Deterministic Algorithm for Random Number Generation Using Coin Flips
    ... -the algorithm can guarantee that there is 0 probability that the ... algorithm will run forever. ... generator that is guaranteed to terminate after finite throws? ... the rng be random? ...
    (sci.math)
Loading