The solution to the problem of finding the primes $p$ and $q$ that have the following form:

$$ c_1 = (a_1 p + b_1 q)^{e_1} \mod{N} \\ c_2 = (a_2 p + b_2 q)^{e_2} \mod{N} $$

Given the values of $c_i$, $a_i$, $b_i$, $e_i$ and $N$ where $N = pq$.

Can be found in this writeup online. I follow the solution right up to the very last line where the author concludes that from the expression.

$$ a_2^{-e_1e_2}c_2^{e_1}-a_1^{-e_1e_2}c_1^{e_2}=a_2^{-e_1e_2}(b_2q)^{e_1e_2}+a_1^{-e_1e_2}(b_1q)^{e_1e_2} \mod{N} $$

We can find $q$ as:

$$ q = \gcd\left( a_2^{-e_1e_2}c_2^{e_1} - a_1^{-e_1e_2}c_1^{e_2} \mod{N}, N \right) $$

Perhaps because the expression has gotten so unweildy I've missed something simple but this seems like such a massive leap and there is no additional explanation.

  • 1
    $\begingroup$ $$a_2^{-e_1e_2}c_2^{e_1}-a_1^{-e_1e_2}c_1^{e_2}=a_2^{-e_1e_2}(b_2q)^{e_1e_2}+a_1^{-e_1e_2}(b_1q)^{e_1e_2} \mod{N}$$ $$a_2^{-e_1e_2}c_2^{e_1}-a_1^{-e_1e_2}c_1^{e_2}= q^{e_1e_2}\left( a_2^{-e_1e_2}(b_2)^{e_1e_2}+a_1^{-e_1e_2}(b_1)^{e_1e_2}\right) \mod{N}$$ $$a= q b \mod{N}$$ $$ab^{-1}= q \mod{N}$$ $\endgroup$
    – kelalaka
    Oct 15, 2023 at 19:12
  • $\begingroup$ @kelalaka Apologies for the topic necromancy, but I'm having a little bit of trouble seeing the relationship between your second line and your third. I see the format of $\textrm{expr} = \left(q^\textrm{exp}\right) \cdot \left(\textrm{expr}\right) \pmod{N}$, but I don't understand why the exponent on the $q$ can be dropped (or, honestly, how that results in a solution of $q$ being equal to a gcd). $\endgroup$
    – apnorton
    Apr 6 at 5:30
  • $\begingroup$ @apnorton It is just renaming. Once you know $c_1, c_2, a_1, a_2, e_1, e_2, N$ then you have the $q$ $\endgroup$
    – kelalaka
    Apr 6 at 19:20


Your Answer

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

Browse other questions tagged or ask your own question.