hw4p1c

hw4p1c.py

import math

N = 257604469245070482680978550578686065374289166183513000923532857227284294429858993942954469559591983
e = 3
d = 85868156415023494226992850192895355124763055394504333641177619075761431476619664647651489853197328

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
        
def findPhi(e,d):
    for k in range(2, 10000):
        if(k == 0):
            continue
        if(k==1):
            continue
        phi = (e*d - 1)/k
        if((phi * k) == (e*d - 1)):
            return phi

def F(phi, N):
    return N-phi+1

def getFactors(phi, N):
    f = F(phi, N)
    p = f - mysqrt(f*f - 4 * N)
    p = p/2
    q = f - p
    return(p,q)

(p, q) = getFactors(findPhi(e,d), N)
print "P IS"
print p
print "Q IS"
print q
print
print "but does it work?"
print "yes" if(q*p == N) else "nope"