"""
n = 10240099
b1 = chr((n & 0xff000000) >> 24)
b2 = chr((n & 0xff0000) >> 16)
b3 = chr((n & 0xff00) >> 8)
b4 = chr(n & 0xff)
s = b1 + b2 + b3 + b4

print(b1.encode())
print(b2.encode())
print(b3.encode())
print(b4.encode())
print(s.encode())

import struct
print(struct.pack('>I', 10240099))
"""
import random
import libnum

d = 5
e = 88447120342035329077203801890175181441227843548712394915405983098804986074228491993716303861346713336901472423214577098721961679062412555594462454080858396158886857405021364693424253936899868042331165487633709535319154171592544118785565876198853503758641178366299573880796663815089204345025378660387680199869
n = 0x009d70ebf2737cb43a7e0ef17b6ce467ab9a116efedbecf1ead94c83e5a082811009100708d690c43c3297b787426b926568a109894f1c48257fc826321177058418e595d16aed5b358d61069150cea832cc7f2df884548f92801606dd3357c39a7ddc868ca8fa7d64d6b64a7395a3247c069112698a365a77761db6b97a2a03a5

k = e * d - 1

r = k
t = 0
while True:
    r = r // 2
    t += 1
    if r % 2 == 1:
        break

success = False

for i in range(1, 101):
    g = random.randint(0, n)
    y = pow(g, r, n)
    if y == 1 or y == n - 1:
        continue

    for j in range(1, t):
        x = pow(y, 2, n)
        if x == 1:
            success = True
            break
        elif x == n - 1:
            continue
        else:
            y = x

    if success:
        break
    else:
        continue

if success:
    p = libnum.gcd(y - 1, n)
    q = n / p
    print ('P: ' + '%s' % p)
    print ('Q: ' + '%s' % q)
else:
    print ('Cannot compute P and Q')