hw4p1a

hw4p1a.py

import math

N = 15241559823203705227878887673081037716739857612370054905916497747890512048310998045508373462474562762403971294892047440113259277270082256942002416995850675202397184299808987
e = 13

def mysqrt(x):
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    n = int(x)
    if n == 0:
        return 0
    a, b = divmod(n.bit_length(), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y

def getPQ(N,e):
    for xx in range(1,1000000):
        mynum = (xx*xx + 4*N)
        myRoot = mysqrt(mynum)
        P = (xx+myRoot)/2
        Q = P-xx
        if(P*Q == N):
            print "found factors"
            print P
            print Q
            return (P,Q)
        P = (xx-myRoot)/2
        Q = P-xx
        if(P*Q == N):
            print "found factors!"
            print P
            print Q
    return (P,Q)

def Phi(P,Q):
    return(P-1)*(Q-1)

def getD(phi, e):
    for kk in range(1, 100000):
        D = (kk * phi + 1)/e
        if(D * e == (kk * phi + 1)):
           print "GOT D!"
           return D
           

P,Q = getPQ(N, e)
phi = Phi(P,Q)
D = getD(phi, e)
print
print
print phi
print
print
print D