2

I'm looking at some prime generation code which first tests $p$ for primality, then has the option to check $(p-1)/2$ for primality. The code already tests $p$ directly (testing against some known primes and using Miller Rabin), but then has the option run those same tests on $(p-1)/2$. What is the purpose of this?

Nerrit
  • 402
ubiquibacon
  • 775
  • 1
    @QiaochuYuan, yes, it is being tested for primality. In fact, "safe" is the name of the argument in the code :) – ubiquibacon Jan 01 '23 at 23:58
  • In any case, it is not "an additional check to see if $p$ is actually prime." It's a separate check to see if $\frac{p-1}{2}$ is prime, which is apparently useful in some cryptographic applications. – Qiaochu Yuan Jan 02 '23 at 00:01
  • 1
    @MarianoSuárez-Álvarez, sorry, not a math wiz so sometimes hard to know what/how to ask the question, I'll gladly provide any info I can. Here is the bit of code I'm looking at if that helps. – ubiquibacon Jan 02 '23 at 00:02
  • 1
    @QiaochuYuan, ok, the application is RSA key generation so I guess I'll check on the Cryptography Exchange site. – ubiquibacon Jan 02 '23 at 00:04
  • 2
    Got my answer here: https://crypto.stackexchange.com/questions/47729/safe-primes-in-rsa – ubiquibacon Jan 02 '23 at 00:07
  • 1
    @MarianoSuárez-Álvarez, :/ Ok, I didn't realize you were not happy with the wording of the question. Thought it was clear that the "test" was for primality, and that the test vectors were $p$ and $(p-1)/2$. I have updated the wording for future viewers. Let me know if it is still not satisfactory and I'll try again. – ubiquibacon Jan 02 '23 at 00:12
  • 1
    Thanks for tracking down the answer, which I found interesting. – MJD Jan 02 '23 at 00:13
  • Huge safe primes are difficult to find , and also not needed for RSA. But if one does want to find one, this feature helps. – Peter Jan 22 '23 at 15:57

0 Answers0