Problem 3

In RSA, we will consider what happens when Alice makes the mistake of choosing p,q

too close together. Her method is as follows. She chooses p

a random large prime, and then chooses q

to be the smallest prime greater than p

. You are Eve, and Alice's public key is (e,n)

where e=13

and n

is

4149515568880992958512407863691161151012446232242436899995657329690652811412991293413200434314186514261288537546721977134041420919065144782418033157091025480140853599374890776565691

(Make sure to copy all of n, which has 181

digits).

Find Alice's private key d

using python