Assignment #3: CRT, Totient Function, Inverses, and Applications (back to full lecture notes)

For this assignment, you will submit a single Python source file a3.py.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts.

    1. Define a Python function egcd() that takes two integer inputs x and y and returns a tuple of two integers (s,t) that satisfies the following property:
      • s * x + t * y == gcd(x,y)
    2. Define a Python function inverse() that takes two integer inputs x and m and returns the multiplicative inverse of x in Z/mZ if it exists, or returns None if it does not.
    1. Define a Python function CRT2() that takes two inputs, each of which is a pair of integers. Each of the two pairs of integers, call them (a,m) and (b,n), represents one of the equations in the system of equations below:
      x
      a (mod m)
      x
      b (mod n)
      You should assume m and n are coprime. The function should return a single integer x Z/(mn)Z that is the solution to the two equations above.
    2. Define a Python function CRTN() that takes one input, which is a list of pairs, each of which is of the form (a,m). Each of the pairs in the list represents a distinct equation in the system of equations below:
      x1
      a1 (mod m1)
      xk
      ak (mod mk)
      You should assume that for every i, j {1,...,k} where ij, mi and mj are coprime. The function should return a single integer x Z/(m1 ⋅ ... ⋅ mk)Z that is the solution to the system of equations above.
    1. Define a very efficient Python function pow2ModPrime() that takes four integer inputs x, y, z, and p. This function always assumes that p is prime (it need not return a correct output if p is not prime, and it should not check whether p is prime). The function should return the result of the computation:
      xyz mod p
      Your implementation may employ the built-in Python function pow(), which takes three inputs a, b, and m and returns ab mod m. However, your function must be able to handle very large inputs. For example:
         pow2ModPrime(3,3,1000000000000000000000,84199) # Should return 42526 quickly.
         pow(3,pow(3,1000000000000000000000),84199)     # Should be much slower than the above.
      
      Hint: consider the way Euler's theorem and the totient function φ are used in the RSA cryptographic protocol.
    2. Define a very efficient Python function diffPows() that takes three inputs: two integer inputs x and y and a list of distinct primes ps. Let P be the product of the primes in ps. The function should return an output equivalent to:
      (33x - 22y) mod P
      Your function must be able to handle very large inputs. For example:
         primes =[\
               15481619,15481633,15481657,15481663,15481727,15481733,15481769,15481787 
              ,15481793,15481801,15481819,15481859,15481871,15481897,15481901,15481933 
              ,15481981,15481993,15481997,15482011,15482023,15482029,15482119,15482123 
              ,15482149,15482153,15482161,15482167,15482177,15482219,15482231,15482263 
              ,15482309,15482323,15482329,15482333,15482347,15482371,15482377,15482387 
              ,15482419,15482431,15482437,15482447,15482449,15482459,15482477,15482479 
              ,15482531,15482567,15482569,15482573,15482581,15482627,15482633,15482639 
              ,15482669,15482681,15482683,15482711,15482729,15482743,15482771,15482773 
              ,15482783,15482807,15482809,15482827,15482851,15482861,15482893,15482911 
              ,15482917,15482923,15482941,15482947,15482977,15482993,15483023,15483029 
              ,15483067,15483077,15483079,15483089,15483101,15483103,15483121,15483151 
              ,15483161,15483211,15483253,15483317,15483331,15483337,15483343,15483359 
              ,15483383,15483409,15483449,15483491,15483493,15483511,15483521,15483553 
              ,15483557,15483571,15483581,15483619,15483631,15483641,15483653,15483659 
              ,15483683,15483697,15483701,15483703,15483707,15483731,15483737,15483749 
              ,15483799,15483817,15483829,15483833,15483857,15483869,15483907,15483971 
              ,15483977,15483983,15483989,15483997,15484033,15484039,15484061,15484087 
              ,15484099,15484123,15484141,15484153,15484187,15484199,15484201,15484211 
              ,15484219,15484223,15484243,15484247,15484279,15484333,15484363,15484387 
              ,15484393,15484409,15484421,15484453,15484457,15484459,15484471,15484489 
              ,15484517,15484519,15484549,15484559,15484591,15484627,15484631,15484643 
              ,15484661,15484697,15484709,15484723,15484769,15484771,15484783,15484817 
              ,15484823,15484873,15484877,15484879,15484901,15484919,15484939,15484951 
              ,15484961,15484999,15485039,15485053,15485059,15485077,15485083,15485143 
              ,15485161,15485179,15485191,15485221,15485243,15485251,15485257,15485273 
              ,15485287,15485291,15485293,15485299,15485311,15485321,15485339,15485341 
              ,15485357,15485363,15485383,15485389,15485401,15485411,15485429,15485441 
              ,15485447,15485471,15485473,15485497,15485537,15485539,15485543,15485549 
              ,15485557,15485567,15485581,15485609,15485611,15485621,15485651,15485653 
              ,15485669,15485677,15485689,15485711,15485737,15485747,15485761,15485773 
              ,15485783,15485801,15485807,15485837,15485843,15485849,15485857,15485863]
              
         # The code below should take at most a second or two to evaluate.
         diffPows(100000000000000000000, 100000000000000000000, primes)
         
         # The output of the above should be:
         1014583418021155147669596086281029838529720782206361091583595823689719157476532284
         8987189887167799660866466205679182087923947730758196605113875528351517618438642265
         3581039473366623112437577201358820794341439719440271391920116932817847656116153368
         7265432104820323843042836554017993078689112459259244886127618081567160190817432495
         2143410149340178452973885327762236756547669499168330784109081344938468727993713195
         3169678339499877031537565519050932012817516387739533522394516718093516017690196562
         7101427207866265547550708480269630690614590278546972352636005909708527043821426318
         4521095281729009794902244831649627645067744531132354275086194660115820734317391275
         9128112857042672881445685539242864388276070829222553398880738035689262514826688173
         6913562704802954300877406726543052076808476120620371564427614984332631535660033277
         8189204900085569366429138226629079794533371458002969316578012640171885098224952913
         3491159071950682951158132515447103910101337602328824428482135061810959708064341298
         2041798901080878626343050467586243536238154444445605344046612862002597217912264786
         0824335665138449552625836001208039714421654922433127769977323976312559879889522757
         1709222772581924582016690799105293131715244224202006451140406716336817962814141853
         2115825675072522109019428377974687020928180075572057614974579410052738475293483072
         3761795114940096414122259399758778638409278794055719938284333607939097874832982043
         1353079076167862532446907487602733400201159484031421148157283172670287937374484685
         4508879443653756784061411297770071775372502147954692284657158826404250380999506744
         2785210787255712896681508731293497639546329245604994768139819393571953247354217371
         7900740573848181518094539324832238278064519569345203659830437641031472046598369915
         89585651957609932891856423136539428409811645597728586100980931
      
  1. In this problem you will implement the three component algorithms of the RSA cryptographic protocol described in lecture.
    1. Define a Python function generate() that takes a single integer input k and returns a tuple (n,e,d) corresponding to the public values n and e and private key d in the RSA cryptographic protocol. The output n must be the product of two distinct, randomly chosen k-digit primes.
      • You may import and use the Python random number generator (from random import random or from random import randint).
      • Your algorithm does not need to be efficient, but it should always be correct.
    2. Define a Python function encrypt() that takes two inputs: an integer m and a tuple (n,e). It should return a single integer: the ciphertext c.
    3. Define a Python function decrypt() that takes two inputs: an integer c representing the ciphertext and a pair of integers (n,d) representing the private key. It should decrypt c and return the original message m.