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

MAT246 Lecture5.pdf

2 Pages
136 Views
Unlock Document

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

Log In


OR

Join OneClass

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

Sign up

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.

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.


Submit