Class Notes (806,741)
Canada (492,424)
Mathematics (2,710)
MAT246H1 (19)
Regina (8)

MAT246 Lecture6.pdf

6 Pages
Unlock Document

University of Toronto St. George

MAT246 Lecture 6 (2012-10-24) RSA encoding – find R N=pq, where p and q are big distinct primes . E: encoder is relatively prime to M: the message you want to send . RSA decoding – find M Step 1: find decoder D use Euclidean algorithm Step 2: find M .  Ex1. N=15, E=3, you get R=6, find M Step 0: => Step 1: find D => => => That is, , thus Step 2: find M => Thus the original message is 6.  Ex2. N=21, E=5, R=17, find M Step 0: => Step 1: find D => => => => That is, Thus, and Step 2: find M => Since => => Since => => Thus, => Thus the original message is 5  Ex3. N=35, E=11, M=7 Step 0: => Step 1: find D MAT246 Lecture 6 (2012-10-24) => => => => That is, Thus, and Step 2: find M => => Thus the encoded version of the message is 15. The Euclidean algorithm Definition 7.2.3: a linear Diophantine equation is an equation of form for which we seek solutions where x and y are integers.  Ex4. A store sells two different kinds of boxes of candies. One kind sells for $9 a box, another kind for $16 a box. At the end of the day, the store has received $143. How many boxes did the store sell at each price? Known that Find s and t satisfying => Step 1: => => => => That is, Thus, and Step 2: Step 3: => => => => Thus, and Thus, the store sold 7 of the cheaper boxes and 5 of the more expensive boxes of candy. Theorem 7.2.5: the Diophantine equation , with a, b and c integers, has integral solutions if and only if divides c. Proof: Let and there is a pair of integers satisfying . Part 1: suppose there is an integer solution to the above equation. divides => and divides => Then, , where is integer. That is divides c. Part 2: suppose divides c => By Euclidean algorithm, there is s and t satisfying Let and , then MAT246 Lecture 6 (2012-10-24) => Lemma 7.2.6: if s divides tu and s is relatively prime to u, then s divides t. Proof: by the unique prime factorization theorem. Theorem 7.2.7: let . The Diophantine equation has a solution if and only if d divides c. if d does divides c had is a solution, then the integral solutions of the equation consist of all the pairs where m assumes all integral values. Proof: the first part was proven in Theorem 7.2.5. Claim 1: each pair of is a solution, since Claim 2: there is no other solution. Let a pair be another solution to this equation ① Known that is a solution, then ② ① - ② => => => and are relatively primes By Lemma 7.2.6, divides and divides , thus => => Since => , that is Since => => => Then rewrite the solution using common value m => => This proves the theorem. Definition 7.2.9: for any natural number m, the Eulerfuntion is defined to the number of numbers in
More Less

Related notes for MAT246H1

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.