from Crypto.Util.number import *

def xgcd(a, b):
    """Extended Euclidean Algorithm (Iterative)

    Args:
        a: int
        b: int

    NOTES
    =====
    We can represent gcd(a,b) = a.x + b.y
    This function returns gcd(a, b), x, y

    REFERENCES
    ==========
    https://a...content-available-to-author-only...c.edu/331/notes/xgcd.pdf

    EXAMPLES
    ========
    >>> xgcd(15, 35)
    (5, -2, 1)
    >>> xgcd(30, 20)
    (10, 1, -1)
    """
    assert a > 0 and b > 0

    xprev, x = 0, 1
    yprev, y = 1, 0

    while a:
        q = b // a
        x, xprev = xprev - q * x, x
        y, yprev = yprev - q * y, y
        a, b = b % a, a

    return b, xprev, yprev

#openssl rsa -noout -text -inform PEM -in publickey.pem -pubin
n = 6582416093028010331296659373009031197381159505574809084789080445968620671489531251341839807257414016347908553593373690756636759290807031891701228091164709
# sq,b = gmpy2.iroot(n,2)
# while n%sq != 0:
#     sq += 1
# p = sq
# q = n / sq

# with open("ciphertext.txt") as f:
#     ct = f.read()
# ct = ct.decode('hex')
# ct = bytes_to_long(ct)
ct = 6406127376909895751144371473602121008927740899743590913049046328952056446854240587499914154405355759628588334083763124425035272951938386104796254276926677

q = int(110973448182064790315250114993940850027832200825996529312042086382625413926861)
p = int(59315234417414827144869122702302197873013464220599601795902064496612053373369)

mp = pow(ct, int((p+1)/4), p)
mq = pow(ct, int((q+1)/4), q)


# from rsasim.gcd_utils import xgcd
g, yp, yq = xgcd(p, q)

r = (yp*p*mq + yq*q*mp) % n
mr = n - r
s = (yp*p*mq - yq*q*mp) % n
ms = n - s

for num in [r,mr,s,ms]:
    print(long_to_bytes(num))

ZnJvbSBDcnlwdG8uVXRpbC5udW1iZXIgaW1wb3J0ICoKCmRlZiB4Z2NkKGEsIGIpOgogICAgIiIiRXh0ZW5kZWQgRXVjbGlkZWFuIEFsZ29yaXRobSAoSXRlcmF0aXZlKQoKICAgIEFyZ3M6CiAgICAgICAgYTogaW50CiAgICAgICAgYjogaW50CgogICAgTk9URVMKICAgID09PT09CiAgICBXZSBjYW4gcmVwcmVzZW50IGdjZChhLGIpID0gYS54ICsgYi55CiAgICBUaGlzIGZ1bmN0aW9uIHJldHVybnMgZ2NkKGEsIGIpLCB4LCB5CgogICAgUkVGRVJFTkNFUwogICAgPT09PT09PT09PQogICAgaHR0cHM6Ly9hLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5jLmVkdS8zMzEvbm90ZXMveGdjZC5wZGYKCiAgICBFWEFNUExFUwogICAgPT09PT09PT0KICAgID4+PiB4Z2NkKDE1LCAzNSkKICAgICg1LCAtMiwgMSkKICAgID4+PiB4Z2NkKDMwLCAyMCkKICAgICgxMCwgMSwgLTEpCiAgICAiIiIKICAgIGFzc2VydCBhID4gMCBhbmQgYiA+IDAKCiAgICB4cHJldiwgeCA9IDAsIDEKICAgIHlwcmV2LCB5ID0gMSwgMAoKICAgIHdoaWxlIGE6CiAgICAgICAgcSA9IGIgLy8gYQogICAgICAgIHgsIHhwcmV2ID0geHByZXYgLSBxICogeCwgeAogICAgICAgIHksIHlwcmV2ID0geXByZXYgLSBxICogeSwgeQogICAgICAgIGEsIGIgPSBiICUgYSwgYQoKICAgIHJldHVybiBiLCB4cHJldiwgeXByZXYKCiNvcGVuc3NsIHJzYSAtbm9vdXQgLXRleHQgLWluZm9ybSBQRU0gLWluIHB1YmxpY2tleS5wZW0gLXB1YmluCm4gPSA2NTgyNDE2MDkzMDI4MDEwMzMxMjk2NjU5MzczMDA5MDMxMTk3MzgxMTU5NTA1NTc0ODA5MDg0Nzg5MDgwNDQ1OTY4NjIwNjcxNDg5NTMxMjUxMzQxODM5ODA3MjU3NDE0MDE2MzQ3OTA4NTUzNTkzMzczNjkwNzU2NjM2NzU5MjkwODA3MDMxODkxNzAxMjI4MDkxMTY0NzA5CiMgc3EsYiA9IGdtcHkyLmlyb290KG4sMikKIyB3aGlsZSBuJXNxICE9IDA6CiMgICAgIHNxICs9IDEKIyBwID0gc3EKIyBxID0gbiAvIHNxCgojIHdpdGggb3BlbigiY2lwaGVydGV4dC50eHQiKSBhcyBmOgojICAgICBjdCA9IGYucmVhZCgpCiMgY3QgPSBjdC5kZWNvZGUoJ2hleCcpCiMgY3QgPSBieXRlc190b19sb25nKGN0KQpjdCA9IDY0MDYxMjczNzY5MDk4OTU3NTExNDQzNzE0NzM2MDIxMjEwMDg5Mjc3NDA4OTk3NDM1OTA5MTMwNDkwNDYzMjg5NTIwNTY0NDY4NTQyNDA1ODc0OTk5MTQxNTQ0MDUzNTU3NTk2Mjg1ODgzMzQwODM3NjMxMjQ0MjUwMzUyNzI5NTE5MzgzODYxMDQ3OTYyNTQyNzY5MjY2NzcKCnEgPSBpbnQoMTEwOTczNDQ4MTgyMDY0NzkwMzE1MjUwMTE0OTkzOTQwODUwMDI3ODMyMjAwODI1OTk2NTI5MzEyMDQyMDg2MzgyNjI1NDEzOTI2ODYxKQpwID0gaW50KDU5MzE1MjM0NDE3NDE0ODI3MTQ0ODY5MTIyNzAyMzAyMTk3ODczMDEzNDY0MjIwNTk5NjAxNzk1OTAyMDY0NDk2NjEyMDUzMzczMzY5KQoKbXAgPSBwb3coY3QsIGludCgocCsxKS80KSwgcCkKbXEgPSBwb3coY3QsIGludCgocSsxKS80KSwgcSkKCgojIGZyb20gcnNhc2ltLmdjZF91dGlscyBpbXBvcnQgeGdjZApnLCB5cCwgeXEgPSB4Z2NkKHAsIHEpCgpyID0gKHlwKnAqbXEgKyB5cSpxKm1wKSAlIG4KbXIgPSBuIC0gcgpzID0gKHlwKnAqbXEgLSB5cSpxKm1wKSAlIG4KbXMgPSBuIC0gcwoKZm9yIG51bSBpbiBbcixtcixzLG1zXToKICAgIHByaW50KGxvbmdfdG9fYnl0ZXMobnVtKSkK