Class Notes
(806,741)

Canada
(492,424)

University of Toronto St. George
(42,762)

Mathematics
(2,710)

MAT246H1
(19)

Regina
(8)

Lecture

# MAT246 Lecture6.pdf

by
OneClass798

Unlock Document

University of Toronto St. George

Mathematics

MAT246H1

Regina

Fall

Description

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