Homework 1.sagews

# Do your scratchwork at the bottom and put your finished code here.
# To receive full credit, these answers at the top must be easy to read.

%md
Who else is in your group? Xiao Hu <br>
Whose worksheet would you like me to grade? Tony Sanchez

Who else is in your group? Xiao Hu
Whose worksheet would you like me to grade? Tony Sanchez

# Question 3a
def fn1(N):
    phiN = fn2(N)
    a = N - phiN + 1
    b = N
    p = (a/2) + (sqrt(a^2-4*b)/2)
    q = (a/2) - (sqrt(a^2-4*b)/2)


    
    return (p,q)

# Question 3b
def fn1(N,e):
    d = fn3(N,e)
    m = valuation(e*d-1,2)
    k = Integer((e*d-1)/2^m)
    g = 2
    x = 2
    while gcd(x-1,N) <= 1:
        x = max([pow(g,(2^i)*k,N) for i in range (0,m)])
        g = g + 1

    p = gcd(x-1,N)

    return p

# Question 3c
def fn1(N):
    # Your code here, no # sign
    # ...
    y = fn4(N,e,x)
    # ...
    return p

# Question 3d
def fn4(N,e,x):
    p = fn1(N)
    q = N/p
    phiN = (p-1)*(q-1)
    d = pow(e,-1,phiN)
    y = pow(x,d,N)
    return y

# Here are some results that might help you test your code.
# If N = 24129905660902534322073032909325823181576568178561 and e = 3, then
# fn3(N,e) would return 16086603773935022881187289823823688622102843503275
# If N = 8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194449 and e = 5, then
# fn3(N,e) would return 7054815823175117051854536900021351766447062185289316942737602081438685044777870872884007347601045405924147549

pow(15,25,18)

9

fn4(187,3,166)

89

fn1(77)

(11, 7)

x = [pow(i,49,105) for i in range (105)]

[(0, 105)]

randint(1,100)

56

N = 8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194449
d = 7054815823175117051854536900021351766447062185289316942737602081438685044777870872884007347601045405924147549
e = 5
m = valuation(e*d-1,2)
k = Integer((e*d-1)/2^m)
g = 2
x = 2
while gcd(x-1,N) <= 1:
    y = [pow(g,(2^i)*k,N) for i in range (0,m)]
    x = max(y)
    print (x,y,gcd(x-1,N))
    g = g + 1

print gcd(x-1,N)

(8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, [8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, 1, 1, 1], 1) (1, [1, 1, 1, 1], 0) (1, [1, 1, 1, 1], 0) (8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, [8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, 1, 1, 1], 1) (8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, [8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, 1, 1, 1], 1) (1, [1, 1, 1, 1], 0) (8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, [8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, 1, 1, 1], 1) (1, [1, 1, 1, 1], 0) (1, [1, 1, 1, 1], 0) (1, [1, 1, 1, 1], 0) (1, [1, 1, 1, 1], 0) (1, [1, 1, 1, 1], 0) (8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, [8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, 1, 1, 1], 1) (8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, [8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, 1, 1, 1], 1) (1, [1, 1, 1, 1], 0) (8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, [8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, 1, 1, 1], 1) (8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, [8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, 1, 1, 1], 1) (8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, [8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, 1, 1, 1], 1) (8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, [8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, 1, 1, 1], 1) (1, [1, 1, 1, 1], 0) (8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, [8818519778968896314818171125026689708058827731612465846902868954883935484366081292667098376108977818563194448, 1, 1, 1], 1) (6057082589287677496862867634185624903817475392986756583163788458825665087823616019809985662639842965466235598, [6057082589287677496862867634185624903817475392986756583163788458825665087823616019809985662639842965466235598, 1, 1, 1], 10758642042407025293120480768408156100809153187347) 10758642042407025293120480768408156100809153187347

N = 24129905660902534322073032909325823181576568178561
d = 16086603773935022881187289823823688622102843503275
e = 3
m = valuation(e*d-1,2)
k = Integer((e*d-1)/2^m)
y = e*d-1
g = 2
x = 2
while gcd(x-1,N) <= 1:
    x = max([pow(g,(y/2**i),N) for i in range (0,m)])
    g = g + 1

p = gcd(x-1,N)
print p

82608889234523014817

valuation(48,3)

1

N = 24129905660902534322073032909325823181576568178561
d = 16086603773935022881187289823823688622102843503275
e = 3
m = valuation(e*d-1,2)
k = Integer((e*d-1)/2^m)
g = 2
while gcd(g-1,N) <= 1:
    g = pow(g,2*k,N)

for g in range (0,100):
    x = [pow(g,(2^i)*k,N) for i in range (0,20)]
    [gcd(x[i]-1,N) for i in range (0,20)]