D.5 Computations for Chapter 9 – Introduction to Cryptography with Coding Theory, 3rd Edition

D.5 Computations for Chapter 9

Suppose someone unwisely chooses RSA primes p and q to be consecutive primes:

p=nextprime(987654321*10^50+12345); q=nextprime(p+1) 
n=p*q

Let’s factor the modulus

n=pq=9754610577899710410000000000000000000000000000000000002507654321019000000000000000000000000000000000000000000161156941

without using the factor command:

s=N(sqrt(n), digits=70) 
p1=next_prime(s) 
p1, q1 
(98765432100000000000000000000000000000000000000000000012773, 
98765432100000000000000000000000000000000000000000000012617)

Of course, the fact that p and q are consecutive primes is important for this calculation to work. Note that we needed to specify 70-digit accuracy so that round-off error would not give us the wrong starting point for looking for the next prime. These factors we obtained match the original p and q, up to order:

p, q 
(98765432100000000000000000000000000000000000000000000012617, 
98765432100000000000000000000000000000000000000000000012773)