Suppose the primes p and q used in the RSA algorithm are consecutive primes (meaning they differ by 2). How would you factor n = pq?
The ciphertext 10787770728 was encrypted using n = 10993522499 and e = 113. The factors p and q of n were chosen so that p - q = 2. Use your method in part (a) to decrypt the message
Asked
Active
Viewed 1,206 times
0
Steph
- 11
-
Taking the square root of $n$ will get you most of the way there for the first part – David Simmons Oct 05 '14 at 16:57
-
$n = pq = (2+q)q = 2q + q^2 \implies q^2 + 2q - n = 0$. Thus, we have $$ q= \frac{-2 + \sqrt{4 + 4n}}{2} $$ which gives $$ q = {-1 + \sqrt{1 + n}} $$ – David Simmons Oct 05 '14 at 17:05
1 Answers
1
Set $n^2-1=10993522499$.
Isolate $n^2$.
$n$ is its positive square root.
Your two factors are $n-1$ and $n+1$.
Senex Ægypti Parvi
- 2,419