Cryptography
Public Key Cryptography is a special form of cryptography that allows a user to receive and decrypt messages that have been encrypted with a publicly known algorithm. Essentially, any person can encrypt a message with the public key, but only the receiver of the message can decrypt it with their private key. The encryption key is the product of two extremely large prime numbers p and q known only to the person receiving the information. Because there is no known formula for factoring extremely large numbers, p and q remain unknown to the public. The decryption key is computed from the two primes using a public algorithm.
Randomized algorithms are essential to public key cryptography because they are a means of generating large prime numbers, a feat that would be terribly slow, inefficient and impractical if done deterministically. An algorithm that generates large prime numbers is relatively simple. All it needs to do is repeatedly pick a large number and then test it for primality until a prime is found. But how does one determine if a number is prime? See the next section...