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) 

Let’s factor the modulus


without using the factor command:

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

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