Re: Primes algorithm

From: Tim Smith (reply_in_group_at_mouse-potato.com)
Date: 04/23/05 

Date: Sat, 23 Apr 2005 21:47:54 GMT

In article <1114078111.016810.121960@g14g2000cwa.googlegroups.com>, Lasse
wrote:
> Actually, there is no reason to try N, N+1, N+2 etc.

In fact, testing N, N+1, etc (well, N, N+2, N+4, etc, since there is no need
to consider even numbers!) is not a good idea, as that skews your
distribution. The gaps between primes are not uniform, and testing
sequentially from a random starting point weights each prime by the size of
the gap it ends.

E.g., suppose you have the following for three consecutive primes:

    P1, gap of 49 composites, P2, gap of 1 composite, P3

Then "scan from random position" will pick P2 25 times as often as it picks
P3. 

-- 
--Tim Smith

Relevant Pages

  • Re: Problems With Public Key Cryptosystems
    ... >> the advice today is just to generate a pair of primes uniformly at ... > Two questions who says the condtions are shrinking. ... > distribution of primes is not random just look at distribution of ... since the span 0..65535 is uniform the sub-span 1-40000 must also be ...
    (sci.math)
  • Re: Problems With Public Key Cryptosystems
    ... >> the advice today is just to generate a pair of primes uniformly at ... > Two questions who says the condtions are shrinking. ... > distribution of primes is not random just look at distribution of ... since the span 0..65535 is uniform the sub-span 1-40000 must also be ...
    (sci.crypt)
  • Re: JSH: Math fakes and blind belief
    ... But even readers who don't know a lot about primes can understand how ... gaps don't act randomly, but you fail to take the utterly obvious next ... then your sequence can't possibly act randomly either ... It's not "shifting the issue" to talk about prime gaps here, ...
    (sci.skeptic)
  • Re: New advance on twin primes conjecture
    ... >> Within the space of 8 pages they show that the smallest gaps ... >> Even if the order of magnitude of the minimum gap between primes will ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.math)
  • Re: JSH: Math journals do not just die
    ... The sequence isn't random because it's ... preferences, especially for "small" primes. ... directly related to gaps between successive primes. ... They indicate preferences. ...
    (sci.skeptic)
Loading