Homework 5

Due Date: Friday, March 4

1. 1. Write a program that converts a positive integer \(a\) of arbitrary length to a string of binary digits.
   2. Use your program from part (a) to convert the number \(1884877076187\) to binary.
2. 1. Write a program that takes three positive integers \(a\), \(b\), \(n\) as input and computes \(a^b\;\mathrm{mod}\;n\) using repeated squares.
   2. Use your program from part (a) to compute \(a^b\;\mathrm{mod}\;n\), where \(a = 3848249404459590\), \(b=5149539332748573\), and \(n=8515443894701123\).
3. 1. Write a program that, given two relatively prime positive integers \(a\) and \(n\), computes the multiplicative inverse of \(a\) modulo \(n\). (Feel free to reuse your Euclidean algorithm code from Homework 3.)
   2. Use your program from part (a) to find the multiplicative inverse of \(1210435168831986\) modulo \(2934527328308269\).
   3. Use your answer to part (b) to solve the equation \[ 1210435168831986\,x \,\equiv\, 592169821564685\pmod{2934527328308269} \]
4. 1. Write a program that computes \(\phi(a)\) for a given positive integer \(a\), where \(\phi\) is the Euler \(\phi\)-function. (Feel free to reuse your prime factorization code from Homework 2.)
   2. Use your program from part (a) to compute \(\phi(8123774489011863)\).
5. 1. Write a program that takes three positive integers \(e\), \(c\), and \(n\) as input (where \(e\) and \(\phi(n)\) are relatively prime) and outputs the solution to the equation \[ x^{\large e} \,\equiv\, c\pmod{n}. \]
   2. Use your program from part (a) to solve the given equation in the case where \(e = 1903344204141091\), \(c = 5199406592532091\), and \(n=7811595468232416\).