Tag Info

In your question, you already pointed out, that the necessary condition is More generally largest prime minus one does not consists of smallest prime as a prime factor therefore, it is sufficient to just check if $p$ divides $q-1$ by computing division. You can just verify this condition during the key generation. I don't know of a more efficient ...