MACM 101 Lecture 28: Lecture 28 Part 3_ Chinese Remainder Theorem
Document Summary
Fermat"s little theorem was improved by euler. For any integers m and a such that they are relatively prime a (m) 1(mod m) where (m) denotes the euler totient function, the number of numbers 0 < k < m relatively prime with m. To encrypt and decrypt messages using this cipher one needs to know the key. Caesar cipher uses the same key for encryption and decryption; it is secret, and if one knows the key he knows everything. Public key cryptosystems use a different approach. Such a system uses different keys for encryption and decryption: every person has a key for encryption, and can write an encrypted message. But this does not help to decrypt the message. Rsa stands for the names of the inventors: rivest, shamir, adleman. In the rsa method, messages are translated into an integer (a short message) or a sequence of integers. Let m be the plaintext (the original message).