We are given the following constant:

e = 17

We generate a random 64 bit prime p and then calculate q so that:

q = modinv(e,p)

This process is repeated until q is prime as well. Now I ran this and generate the following pair:

p = 17409780921729337789
q = 10241047601017257523

Now I calculate n = p*q:

n = 178294395142712253230038799435668436647

My question is, can I try to derive both p and q from n? Because essentially I have:

n = p * modinv(e,p)

which looks to be a simple equation with 1 unknown. Am I missing something?


1 Answer 1


I ended up finding the solution: because of the way we construct q, we obtain the following equality:

$$(qe) - 1 = p j$$

where j is an integer. We can now express p as a quantity of q:

$$p = \frac{(qe)-1}j$$

Using the fact that n = q*p:

$$n =q(\frac{(qe)-1}j) $$

And we basically get a quadratic equation:

$$eq^2 -q -nj = 0 $$

Which we can now try to solve for various values of j.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .