#python3
from math import gcd
import binascii
# use https://www.alpertron.com.ar/ECM.HTM to factor n

# Cipher text and private key values
c = 14233215171999431620670742801992653887466654474564774567565482115708994971815998692805257101560625714845217078751863031453530789139353946667912836198369580283828831512520753040759574661583289733067194603349961285220341733595404870252973575776007626137207539918299185290666626201682475925787500697075273517928342450904756899125972158778923306466

n = 17190751765871320929594511788715040293755178677970494040999935752481499432324081420804535569049828358872534054083287610758506232432273611461779363808286315449034509728493030687881521253447668499524454596411931335376554928809260061677941571447357490867956927337940685369932675855590823386769800936470170609619423644569934236531433566627693968207

e = 65537


# Modular multiplicative inverse
def mod_inv(a, n):
    t, r = 0, n
    new_t, new_r = 1, a
    while new_r != 0:
        quotient = r // new_r
        t, new_t = new_t, t - quotient * new_t
        r, new_r = new_r, r - quotient * new_r
    if r > 1:
        raise Exception("a is not invertible")
    if t < 0:
        t = t + n
    return t


# Euler's totient
def calc_phi_n(ps):
    phi = ps[0] - 1
    for i in ps[1:]:
        j = i - 1
        phi *= j
    return phi


# Carmichael's totient
def calc_lambda_n(ps):
    lcm = ps[0] - 1
    for i in ps[1:]:
        j = i - 1
        lcm = lcm*j//gcd(lcm, j)
    return lcm


# Test factorization
def test_factor(ps, n):
    q = 1
    for i in ps:
        q *= i
    if q == n:
        b = True
    elif q != n:
        b = False
    return b


p1 = 8694307819
p2 = 8775407717
p3 = 9026241761
p4 = 9057149533
p5 = 9585778841
p6 = 9733417549
p7 = 9855694997
p8 = 9903110561
p9 = 9960439201
p10 = 10016164247
p11 = 10213913951
p12 = 10375133233
p13 = 10888745003
p14 = 10928267249
p15 = 11093110097
p16 = 11969573459
p17 = 12351917503
p18 = 12471968101
p19 = 13871073973
p20 = 14396917097
p21 = 14539225093
p22 = 14717833373
p23 = 14837579117
p24 = 15209272151
p25 = 15280005421
p26 = 15484737221
p27 = 15554133887
p28 = 16042139507
p29 = 16278648473
p30 = 16335802403
p31 = 16382994611
p32 = 16728205063
p33 = 16809927443
p34 = 16861924201

ps = [p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19, p20, p21, p22, p23, p24, p25, p26, p27, p28, p29, p30, p31, p32, p33, p34]

assert(test_factor(ps, n))   # verify p1*p2*...p34 = n

phi_n = calc_phi_n(ps)       # Euler's Totiens of n
lambda_n = (calc_lambda_n(ps)) # Carmichaels's Totient of n

d = mod_inv(e, phi_n)        # Calculate d value, trying with both phi_n and lambda_n
#print(d)

m2 = pow(c, d, phi_n)        # decrypt cipher text
print(bytes.fromhex(hex(m2)[2:]).decode('utf-8'))

#print(binascii.unhexlify(hexadecimals[2:]))