Skip to content
Snippets Groups Projects
  • Simon Tatham's avatar
    da3bc3d9
    Refactor generation of candidate integers in primegen. · da3bc3d9
    Simon Tatham authored
    I've replaced the random number generation and small delta-finding
    loop in primegen() with a much more elaborate system in its own source
    file, with unit tests and everything.
    
    Immediate benefits:
    
     - fixes a theoretical possibility of overflowing the target number of
       bits, if the random number was so close to the top of the range
       that the addition of delta * factor pushed it over. However, this
       only happened with negligible probability.
    
     - fixes a directional bias in delta-finding. The previous code
       incremented the number repeatedly until it found a value coprime to
       all the right things, which meant that a prime preceded by a
       particularly long sequence of numbers with tiny factors was more
       likely to be chosen. Now we select candidate delta values at
       random, that bias should be eliminated.
    
     - changes the semantics of the outermost primegen() function to make
       them easier to use, because now the caller specifies the 'bits' and
       'firstbits' values for the actual returned prime, rather than
       having to account for the factor you're multiplying it by in DSA.
       DSA client code is correspondingly adjusted.
    
    Future benefits:
    
     - having the candidate generation in a separate function makes it
       easy to reuse in alternative prime generation strategies
    
     - the available constraints support applications such as Maurer's
       algorithm for generating provable primes, or strong primes for RSA
       in which both p-1 and p+1 have a large factor. So those become
       things we could experiment with in future.
    da3bc3d9
    History
    Refactor generation of candidate integers in primegen.
    Simon Tatham authored
    I've replaced the random number generation and small delta-finding
    loop in primegen() with a much more elaborate system in its own source
    file, with unit tests and everything.
    
    Immediate benefits:
    
     - fixes a theoretical possibility of overflowing the target number of
       bits, if the random number was so close to the top of the range
       that the addition of delta * factor pushed it over. However, this
       only happened with negligible probability.
    
     - fixes a directional bias in delta-finding. The previous code
       incremented the number repeatedly until it found a value coprime to
       all the right things, which meant that a prime preceded by a
       particularly long sequence of numbers with tiny factors was more
       likely to be chosen. Now we select candidate delta values at
       random, that bias should be eliminated.
    
     - changes the semantics of the outermost primegen() function to make
       them easier to use, because now the caller specifies the 'bits' and
       'firstbits' values for the actual returned prime, rather than
       having to account for the factor you're multiplying it by in DSA.
       DSA client code is correspondingly adjusted.
    
    Future benefits:
    
     - having the candidate generation in a separate function makes it
       easy to reuse in alternative prime generation strategies
    
     - the available constraints support applications such as Maurer's
       algorithm for generating provable primes, or strong primes for RSA
       in which both p-1 and p+1 have a large factor. So those become
       things we could experiment with in future.