writeups/icecrax/asis2019/chinese_remainder_theorem.py

   1 from functools import reduce
   2 def chinese_remainder(n, a):
   3     sum = 0
   4     prod = reduce(lambda a, b: a*b, n)
   5     for n_i, a_i in zip(n, a):
   6         p = prod // n_i
   7         sum += a_i * mul_inv(p, n_i) * p
   8     return sum % prod
   9
  10 def mul_inv(a, b):
  11     b0 = b
  12     x0, x1 = 0, 1
  13     if b == 1: return 1
  14     while a > 1:
  15         q = a // b
  16         a, b = b, a%b
  17         x0, x1 = x1 - q * x0, x0
  18     if x1 < 0: x1 += b0
  19     return x1
  20
  21
  22 # Chinese Remainder Theorem:
  23 # In number theory, the Chinese remainder theorem states that if one knows the remainders
  24 # of the Euclidean division of an integer n by several integers, then one can determine
  25 # uniquely the remainder of the division of n by the product of these integers, under the
  26 # condition that the divisors are pairwise coprime.
  27
  28 # What follows from the theorem:
  29 # If M, N are coprime and A is coprime to M and N,
  30 # then A is a quadratic residue modulo (M * N) if and only if it is a quadratic residue modulo M and modulo N
  31 # a ≡ x^2 mod mn  =>  a ≡ x^2 mod m and a ≡ x^2 mod n.
  32 # H ≡ pkey^2 mod p   => H ≡ pkey^2 mod p0 and H ≡ pkey^2 mod p1 ...
  33
  34 # Note:
  35 # If each factor has 2 solutions, then for H we have 2*2*2*2 = 16 solutions
  36 # To use the theorem all factors pi should be coprime gcd(pi, pj) = 1 !
  37
  38 if __name__ == '__main__':
  39     p = 862718293348820473429344482784628181556388621521298319395315527974911
  40     H = 381704527450191606347421195235742637659723827441243208291869156144963 # odd integer coprime to p
  41
  42     factors = [1504073, 20492753, 59833457464970183, 467795120187583723534280000348743236593] # factors are coprime
  43
  44     r0 = [1104407, 13380905, 25592602581952126, 159525640227776948659231897831230505709]
  45     r1 = [1104407, 13380905, 25592602581952126, 308269479959806774875048102517512730884]
  46     r2 = [1104407, 13380905, 34240854883018057, 159525640227776948659231897831230505709]
  47     r3 = [1104407, 13380905, 34240854883018057, 308269479959806774875048102517512730884]
  48     r4 = [1104407, 7111848, 25592602581952126, 159525640227776948659231897831230505709]
  49     r5 = [1104407, 7111848, 25592602581952126, 308269479959806774875048102517512730884]
  50     r6 = [1104407, 7111848, 34240854883018057, 159525640227776948659231897831230505709]
  51     r7 = [1104407, 7111848, 34240854883018057, 308269479959806774875048102517512730884]
  52     r8 = [399666, 13380905, 25592602581952126, 159525640227776948659231897831230505709]
  53     r9 = [399666, 13380905, 25592602581952126, 308269479959806774875048102517512730884]
  54     r10 = [399666, 13380905, 34240854883018057, 159525640227776948659231897831230505709]
  55     r11 = [399666, 13380905, 34240854883018057, 308269479959806774875048102517512730884]
  56     r12 = [399666, 7111848, 25592602581952126, 159525640227776948659231897831230505709]
  57     r13 = [399666, 7111848, 25592602581952126, 308269479959806774875048102517512730884]
  58     r14 = [399666, 7111848, 34240854883018057, 159525640227776948659231897831230505709]
  59     r15 = [399666, 7111848, 34240854883018057, 308269479959806774875048102517512730884]
  60
  61     rs = [r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15]
  62     for r in rs:
  63         print(chinese_remainder(factors, r))
  64
  65 # Results:
  66 # 739258514585797449032297222084055811470702691611125687711372074996687
  67 # 460372941321907147479217537764873459531020265638440613169538863817034
  68 # 785232755191570522054580268914288666635203565395845945113513087262967
  69 # 506347181927680220501500584595106314695521139423160870571679876083314
  70 # 861011580078658110931573476857568388286745404020778288869777707662969
  71 # 582126006814767809378493792538386036347062978048093214327944496483316
  72 # 44267527335610710524512040903173061894857656284200226876603191954338
  73 # 628100247420540882400776839368618891511563851832813471730085508749596
  74 # 234618045928279591028567643416009290044824769688484847665230019225315
  75 # 818450766013209762904832441881455119661530965237098092518712336020573
  76 # 280592286534052664050850690246242145209325643473205105067371031491595
  77 # 1706713270162362497771005927059793269643217500520030525537820311942
  78 # 356371111421140252927843898189521866860867482098137448823635651891597
  79 # 77485538157249951374764213870339514921185056125452374281802440711944
  80 # 402345352026913325950126945019754722025368355882857706225776664157877
  81 # 123459778763023024397047260700572370085685929910172631683943452978224