Class Notes (838,860)
Mathematics (2,859)
MAT246H1 (30)
Regina (8)
Lecture

MAT246 Lecture5.pdf

2 Pages
136 Views

Department
Mathematics
Course
MAT246H1
Professor
Regina
Semester
Fall

Description
MAT246 Lecture 5 (2012-10-10) RSA coding Relatively prime: two integers a & b are relatively prime if their only common factor is 1. Receiver: Chooses 2 distinct large prime p and q, and lets N=pq Note that: Chooses a relatively prime E to Announces the pair (N,E) Sender: Message must be natural number, M, that is less than N Note that: Sends the remainder R Theorem 6.1.1: let N=pq, where p and q are distinct prime numbers, and let . If k and a are any natural numbers, then . Proof: Known that and , then Since N=pq, this means that and Consider p first, same proof for q. Case 1: if , then Case 2: if p does not divide a then, by Fermat’s THM, , thus, => that is, => Same proof for q, thus Decoding: A natural number D (decoder) satisfies that for some natural number k => => that is By THM 6.1.1, , thus,  Ex1. p=11, q=7, N=77, =60, M=71, encode message. Step 1: find E E is relatively prime to Let E=13 Step 2: find R M=71 => => Since => Since => => => => => => => => . MAT246 Lecture 5 (2012-10-10) Since => , that is => R=15 Thus the encoded version o
More Less

Related notes for MAT246H1
Me

OR

Join OneClass

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

Join to view

OR

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.