Skip to content
Snippets Groups Projects
  • Simon Tatham's avatar
    11568652
    PrimeCandidateSource: add one-shot mode. · 11568652
    Simon Tatham authored
    If you want to generate a Sophie Germain / safe prime pair with this
    code, then after you've made p, you need to test the primality of
    2p+1.
    
    The easiest way to do that is to make a PrimeCandidateSource that is
    so constrained as to only be able to deliver 2p+1 as a candidate, and
    then run the ordinary prime generation system. The problem is that the
    prime generation loops forever, so if 2p+1 _isn't_ prime, it will just
    keep testing the same number over and over again and failing the test.
    
    To solve this, I add a 'one-shot mode' to the PrimeCandidateSource
    itself, which will cause it to return NULL if asked to generate a
    second candidate. Then the prime-generation loops all detect that and
    return NULL in turn. However, for clients that _don't_ set a pcs into
    one-shot mode, the API remains unchanged: pcs_generate will not return
    until it's found a prime (by its own criteria).
    
    This feels like a bit of a bodge, API-wise. But the other two obvious
    approaches turn out more awkward.
    
    One option is to extract the Pockle from the PrimeGenerationContext
    and use that to directly test primality of 2p+1 based on p - but that
    way you don't get to _probabilistically_ generate safe primes, because
    that kind of PGC has no Pockle in the first place. (And you can't make
    one separately, because you can't convince it that an only
    probabilistically generated p is prime!)
    
    Another option is to add a test() method to PrimeGenerationPolicy,
    that sits alongside generate(). Then, having generated p, you just
    _test_ 2p+1. But then in the provable case you have to explain to it
    that it should use p as part of the proof, so that API would get
    awkward in its own way.
    
    So this is actually the least disruptive way to do it!
    11568652
    History
    PrimeCandidateSource: add one-shot mode.
    Simon Tatham authored
    If you want to generate a Sophie Germain / safe prime pair with this
    code, then after you've made p, you need to test the primality of
    2p+1.
    
    The easiest way to do that is to make a PrimeCandidateSource that is
    so constrained as to only be able to deliver 2p+1 as a candidate, and
    then run the ordinary prime generation system. The problem is that the
    prime generation loops forever, so if 2p+1 _isn't_ prime, it will just
    keep testing the same number over and over again and failing the test.
    
    To solve this, I add a 'one-shot mode' to the PrimeCandidateSource
    itself, which will cause it to return NULL if asked to generate a
    second candidate. Then the prime-generation loops all detect that and
    return NULL in turn. However, for clients that _don't_ set a pcs into
    one-shot mode, the API remains unchanged: pcs_generate will not return
    until it's found a prime (by its own criteria).
    
    This feels like a bit of a bodge, API-wise. But the other two obvious
    approaches turn out more awkward.
    
    One option is to extract the Pockle from the PrimeGenerationContext
    and use that to directly test primality of 2p+1 based on p - but that
    way you don't get to _probabilistically_ generate safe primes, because
    that kind of PGC has no Pockle in the first place. (And you can't make
    one separately, because you can't convince it that an only
    probabilistically generated p is prime!)
    
    Another option is to add a test() method to PrimeGenerationPolicy,
    that sits alongside generate(). Then, having generated p, you just
    _test_ 2p+1. But then in the provable case you have to explain to it
    that it should use p as part of the proof, so that API would get
    awkward in its own way.
    
    So this is actually the least disruptive way to do it!