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)