MAT246 Lecture 5 (2012-10-10)
Relatively prime: two integers a & b are relatively prime if their only common factor is 1.
Chooses 2 distinct large prime p and q, and lets N=pq
Chooses a relatively prime E to
Announces the pair (N,E)
Message must be natural number, M, that is less than N
Sends the remainder R
let N=pq, where p and q are distinct prime numbers, and let . If k
and a are any natural numbers, then .
Known that and , then
Since N=pq, this means that
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
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
Step 2: find R
M=71 => =>
Since => =>
=> => =>
=> => =>
. MAT246 Lecture 5 (2012-10-10)
Since => , that is
Thus the encoded version o