01204211/activity7 number theory 2

This is part of 01204211-58.

In-class activities

Due date: 14 Dec 2015

These activities require programming. You can use any languages that you like. Please keep the codes for these activities for the other sets of activities as well.

A.1 Implement the Extended-GCD algorithm and use it to find, for each following pair of $a$ and $b$, the g.c.d. of $a$ and $b$ and a pair of integers $(x,y)$ such that $ax+by=gcd(a,b)$.

(a) $a=5,$ $b=7$

(b) $a=500,$ $b=7123$

(c) $a=55515,$ $b=71234$

(d) $a=5551532,$ $b=7123456$

(e) $a=$your student id, $b=$ the student id of another student sitting next to you. (Don't forget to write down the values of $a$ and $b$ as well.

Notes: The pseudo code for the Extended-GCD is as follows. (Don't forget to watch the video clips.)

FUNCTION ExtendedGCD(a,b)
1.   IF a mod b == 0 THEN
2.      return (b,0,1)
3.   ELSE
4.      (g,x,y) = ExtendedGCD(b, a mod b)
5.      return (g,y, x - y * floor(a/b))
6.   ENDIF

A.2 Use the Extended-GCD algorithm to find the modular multiplicative inverse for the divisor in each of the following question and find the result of the modular division. If the inverse does not exist, you can just state the fact and state that the division cannot be found.

(E.g., if the question is to find 4/3 (mod 11), you have to find $3^{-1}$ and then find $0\leq c<11$ such that $c\cdot 3\equiv 4$ (mod 11).)

(a) $5/6$ (mod $7$)

(b) $5/6$ (mod $1451$)

(c) $5/6$ (mod $7829$)

(d) $6543/3456$ (mod $98899$)

(e) $1234/4567$ (mod $104537$)

A.3 RSA. In this activity, we will try to run the RSA algorithm.

PART I: Preparation

(a) Pick two primes from this list of primes. Call them $p$ and $q$.

(b) Let $N=pq$.

(c) Pick some integer $e$ (where $3\leq e<N$) such that $gcd(e,(p-1)(q-1))=1$.

(d) Find integer $d$ which is $e^{-1}$ (mod $(p-1)(q-1)$).

(e) Write out the public key $(e,N)$ and the private key $(d,N)$.

PART II: Encryption. In this part, you should work with another student. Let's call another student A.

(a) Give A you public key.

(b) Let A pick one number $M$ as a message (make sure that $1\leq M<N$). A should not tell you the message $M$.

(c) Now, let A encrypt the message with your public key, and give you the encrypted message $M'$.

(d) Decrypt $M'$ and compare the message with A's original message $M$.

A.4 Solve for $x$ in this equation $10x+3\equiv 0$ (mod 71143).

A.5 In this problem, we will perform all calculation modulo 11. Let $x,y$ denote the last 2 digits of your student id. (E.g., if you ID is 1234567890, then x=9, y=0.) Find the values $a,b$ that satisfy these equations.

$10a+5b\equiv x$ (mod 11)

$7a+2b\equiv y$ (mod 11)

(Try to solve this without the Gaussian elimination algorithm in the next activity.)

A.6 Gaussian Elimination. In this activity we will implement the Gaussian Elimination algorithm for solving systems of linear equations.

Do you remember the Gaussian Elimination algorithm? If you don't, please read this wikipedia entry on the Gaussian elimination algorithm first.

The nice thing about modular arithmetic when the modulus is a prime is that we can perform division with integers. This enables us to use methods (designed for a system of real numbers) to solve a system of linear equations.

Let's take your student id and make it our constraints. Let $b_{1},b_{2},b_{3},\ldots ,b_{10}$ be the digits from your student id. (E.g., if your id is 1234567890, $b_{1}=1,b_{5}=5,b_{10}=0$.)

Let's perform all calculations modulo 17.

(a) Solve for $a_{0},a_{1},\ldots ,a_{9}$ in this system of linear congruences. (Don't forget that we are doing modular arithmetic modulo 17 here.)

$\left({\begin{array}{cccccccccc}1&1&1&1&1&1&1&1&1&1\\2&1&9&13&15&16&8&4&2&1\\14&16&11&15&5&13&10&9&3&1\\4&1&13&16&4&1&13&16&4&1\\12&16&10&2&14&13&6&8&5&1\\11&16&14&8&7&4&12&2&6&1\\10&16&12&9&11&4&3&15&7&1\\8&1&15&4&9&16&2&13&8&1\\9&1&2&4&8&16&15&13&9&1\\7&16&5&9&6&4&14&15&10&1\end{array}}\right)\left({\begin{array}{c}a_{9}\\a_{8}\\a_{7}\\a_{6}\\a_{5}\\a_{4}\\a_{3}\\a_{2}\\a_{1}\\a_{0}\end{array}}\right)\equiv \left({\begin{array}{c}b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\\b_{6}\\b_{7}\\b_{8}\\b_{9}\\b_{10}\end{array}}\right)$

If you need the coefficient matrix, you can copy from the following text:

 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
 2, 1, 9, 13, 15, 16, 8, 4, 2, 1
 14, 16, 11, 15, 5, 13, 10, 9, 3, 1
 4, 1, 13, 16, 4, 1, 13, 16, 4, 1
 12, 16, 10, 2, 14, 13, 6, 8, 5, 1
 11, 16, 14, 8, 7, 4, 12, 2, 6, 1
 10, 16, 12, 9, 11, 4, 3, 15, 7, 1
 8, 1, 15, 4, 9, 16, 2, 13, 8, 1
 9, 1, 2, 4, 8, 16, 15, 13, 9, 1
 7, 16, 5, 9, 6, 4, 14, 15, 10, 1

(b) The coefficient matrix in this question is a special one to find coefficients of a polynomial $F(x)=a_{9}x^{9}+a_{8}x^{8}+\cdots a_{1}x+a_{0}$. Find $F(1),F(2),\ldots ,F(10)$. What do you see? (Don't forget to perform every calculation modulo 17.)