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

$$\begin{array}{c}n=pq=9754610577899710410000000000000000000000000000000000002507\\ 654321019000000000000000000000000000000000000000000161156941\end{array}$$

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 ...