-
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!
Simon Tatham authoredIf 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!