Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In the key generation step of paillier cryptosystem ,

In order to satisfy $\gcd(pq,(p-1)(q-1))=1$ , we can take equal length primes.

Instead of taking(length as parameter to generate $p,q$) equal length primes , is there any time efficient method to generate $p,q$ that assures $pq,(p-1)(q-1)$ are relatively prime ? Or is it mandatory to take equal length primes for efficient implementation .

Just out of curiosity I want to know whether there are any public-key cryptosystems in which primes of equal length are mandatory. If there is , please list names of few of them.

Some work :

Let $p,q$ be the primes such that $p<q$.

Then $p\not|(p-1)$ and $q\not|(q-1)$

Since $p<q$ , $q\not|(p-1)$

So , the only chance to violate the condition $\gcd(pq,(p-1)(q-1))=1$ is $p|(q-1)$

More generally largest prime number minus one does not consists of smallest prime number as a prime factor .

How to ensure this without taking equal length primes ?

share|improve this question

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 way, anyway, it should be efficient enough for key generation. The main drawback for efficiency would occur if you repeatedly generate unsuitalbe keys, but the probability of that would depend on the length difference you allow for the two primes.

However, in general I think that the security of the scheme depends on the size of the smallest prime, however, the efficiency depends on the size of the obtained modulus $N = pq$, therefore it is probably reasonable to just use equal size primes for the best security and efficiency. Hence, I would guess that the main reason for noting that this property can be ensured by taking equal length primes, is to make sure that no additional work is required to check this during key generation.

I can not point out any schemes that definitely require equal length primes.

share|improve this answer
After generating $p,q$ we can check that condition . But my point is that, we have to generate $p,q$ in such a way that $\gcd(pq,(p-1)(q-1))=1$ but $p,q$ are of any length . – hanugm Sep 11 '14 at 9:08
@hanu I don't know of any way to do this. I think there is an inherent problem that the primes have to be random and independent, but in general ensuring this property might enforce more dependencies between the primes than required by this condition. Any algorithm that does this generation would have to take care not to add any other dependencies between the generated primes. – DragonMouse Sep 11 '14 at 9:25
One could compute $q$ as 1 more than [something-coprime-to-$p$ times something-smaller-than-$p$]. $\hspace{.48 in}$ – Ricky Demer Sep 12 '14 at 4:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.