D.5 Computations for Chapter 9

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

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

Let’s factor the modulus



without using the `factor` command:

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

Of course, the fact that  and  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  and , up to order:

````p, q`
`(98765432100000000000000000000000000000000000000000000012617, `
`98765432100000000000000000000000000000000000000000000012773)`
```