from functools import reduce
def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod
 
def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a // b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1
 

# Chinese Remainder Theorem:
# In number theory, the Chinese remainder theorem states that if one knows the remainders 
# of the Euclidean division of an integer n by several integers, then one can determine
# uniquely the remainder of the division of n by the product of these integers, under the
# condition that the divisors are pairwise coprime.

# What follows from the theorem:
# If M, N are coprime and A is coprime to M and N,
# then A is a quadratic residue modulo (M * N) if and only if it is a quadratic residue modulo M and modulo N
# a ≡ x^2 mod mn  =>  a ≡ x^2 mod m and a ≡ x^2 mod n.
# H ≡ pkey^2 mod p   => H ≡ pkey^2 mod p0 and H ≡ pkey^2 mod p1 ...

# Note:
# If each factor has 2 solutions, then for H we have 2*2*2*2 = 16 solutions
# To use the theorem all factors pi should be coprime gcd(pi, pj) = 1 !

if __name__ == '__main__':
    p = 862718293348820473429344482784628181556388621521298319395315527974911
    H = 381704527450191606347421195235742637659723827441243208291869156144963 # odd integer coprime to p
 
    factors = [1504073, 20492753, 59833457464970183, 467795120187583723534280000348743236593] # factors are coprime

    r0 = [1104407, 13380905, 25592602581952126, 159525640227776948659231897831230505709]
    r1 = [1104407, 13380905, 25592602581952126, 308269479959806774875048102517512730884]
    r2 = [1104407, 13380905, 34240854883018057, 159525640227776948659231897831230505709]
    r3 = [1104407, 13380905, 34240854883018057, 308269479959806774875048102517512730884]
    r4 = [1104407, 7111848, 25592602581952126, 159525640227776948659231897831230505709]
    r5 = [1104407, 7111848, 25592602581952126, 308269479959806774875048102517512730884]
    r6 = [1104407, 7111848, 34240854883018057, 159525640227776948659231897831230505709]
    r7 = [1104407, 7111848, 34240854883018057, 308269479959806774875048102517512730884]
    r8 = [399666, 13380905, 25592602581952126, 159525640227776948659231897831230505709]
    r9 = [399666, 13380905, 25592602581952126, 308269479959806774875048102517512730884]
    r10 = [399666, 13380905, 34240854883018057, 159525640227776948659231897831230505709]
    r11 = [399666, 13380905, 34240854883018057, 308269479959806774875048102517512730884]
    r12 = [399666, 7111848, 25592602581952126, 159525640227776948659231897831230505709]
    r13 = [399666, 7111848, 25592602581952126, 308269479959806774875048102517512730884]
    r14 = [399666, 7111848, 34240854883018057, 159525640227776948659231897831230505709]
    r15 = [399666, 7111848, 34240854883018057, 308269479959806774875048102517512730884]

    rs = [r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15]
    for r in rs:
        print(chinese_remainder(factors, r))

# Results:
# 739258514585797449032297222084055811470702691611125687711372074996687
# 460372941321907147479217537764873459531020265638440613169538863817034
# 785232755191570522054580268914288666635203565395845945113513087262967
# 506347181927680220501500584595106314695521139423160870571679876083314
# 861011580078658110931573476857568388286745404020778288869777707662969
# 582126006814767809378493792538386036347062978048093214327944496483316
# 44267527335610710524512040903173061894857656284200226876603191954338
# 628100247420540882400776839368618891511563851832813471730085508749596
# 234618045928279591028567643416009290044824769688484847665230019225315
# 818450766013209762904832441881455119661530965237098092518712336020573
# 280592286534052664050850690246242145209325643473205105067371031491595
# 1706713270162362497771005927059793269643217500520030525537820311942
# 356371111421140252927843898189521866860867482098137448823635651891597
# 77485538157249951374764213870339514921185056125452374281802440711944
# 402345352026913325950126945019754722025368355882857706225776664157877
# 123459778763023024397047260700572370085685929910172631683943452978224