MAT246H1 Lecture Notes - Euclidean Algorithm, Coprime Integers, Natural Number
Document Summary
Chooses 2 distinct large prime p and q, and lets n=pq. Relatively prime: two integers a & b are relatively prime if their only common factor is 1. 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 . Case 2: if p does not divide a then, by fermat"s thm, , thus, A natural number d (decoder) satisfies that for some natural number k. Ex1. p=11, q=7, n=77, =60, m=71, encode message. Thus the encoded version of the message is 15. Ex2. p=11, q=7, n=77, =60, r=15, d=37, decode message. The greatest common divisor of the natural numbers m and n is denoted . Let d=gcm (a,b), find d as follows: (suppose b
