2
$\begingroup$

$p$ is a 2048 bit prime number

$q$ is a 224 bit prime number

I know that $q$ is a prime divisor of $p-1$, thus $p=1 \bmod q$ but I couldn't write efficient code to calculate this.

  • I can calculate 2048 bit prime $p$, but how to find $q$ efficiently?

Currently what I am doing is generating 224-bit primes and checking whether they are dividing $p-1$ or not but it takes forever...

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

I can calculate 2048 bit prime $p$, but how to find $q$ efficiently?

You're doing things in the wrong order.

Instead, you pick a 224 bit $q$, and then such for a 2048 bit prime of the form $p = kq + 1$ (for some integer $k$).

This can be done with essentially the same amount of effort as finding a 2048 bit prime (without constraints), and directly answers the problem, as such a $p, q$ pair guarantees that $p \equiv kq + 1 \equiv 1 \pmod q$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the answer.Currently i am generating prime numbers with this : generate random number given n bits and test whether its prime or not with isPrime function.So how should i modify this to find p ? Am i going to multiply q some k s,(what should be k trials ??) then add 1 and check until it is prime ? I mean what should be the range of ks that i am going to test in a loop $\endgroup$
    – doggodonger
    Dec 10, 2018 at 19:37
  • $\begingroup$ I guess i couldnt understand since my code still takes forever $\endgroup$
    – doggodonger
    Dec 10, 2018 at 19:56
  • $\begingroup$ @doggodonger: are you adding one to $k$, or one to $p$? Adding one to $k$ (or equivalently, adding $q$ to $p$) is the correct thing. If you add 1 to $p$, then your initial $p$ will be of the form $kq+1$; the ones after the first won't be $\endgroup$
    – poncho
    Dec 10, 2018 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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