MATH135 Study Guide - Quiz Guide: Delaware Route 1, Coprime Integers, Joule
17 Jun 2015
School
Department
Course
Professor
40
MATH135 Full Course Notes
Verified Note
40 documents
Document Summary
Much of this note can be treated as optional reading. While the square-and-multiply algorithm will not be examined, knowing it can be helpful when computing powers in modular arithmetic by hand. Both encryption and decryption require computing huge powers am (mod n) (assuming of course a 0 (mod n)). If n is a prime, we can speed up somewhat using fermat"s. Little theorem, according to which an1 1 (mod n). But even then, when n is large and m = q(n 1) + r where the remainder r is large, we cannot avoid computing am ar (mod n). Fortunately, there is a simple technique which handles this extremely well, regardless of whether n is prime. We demonstrate the square-and-multiply algorithm by a concrete example. Example 1. (this is the rsa example we tried in class. ) Choose primes p = 23 and q = 47, and let n = pq = 1081.
