## Primes
Historically, most coding systems required the sender and receive to each have a "private key" which enabled them to encrypt and decrypt the information that was being sent and received. Revolutionary ideas worked on by Ralph Merkle, Whitfield Diffie, Martin Hellman, Leonard Adleman, Adi Shamir, and Ronald Rivest made it feasible to implement new public key systems. These systems make it possible for a person Y to put information in a public directory and have anyone X who wanted to send a secret message to Y use this "public key" so as to be able to send information in a secure manner. This system does not depend on the secrecy of the key but on the computational complexity of using "intercepted" encrypted text to obtain the "clear" (readable) text. Amazingly, the security of the system developed by Rivest, Shamir, and Adleman (known as RSA) is based on the fact that factoring products of two extremely large primes.is thought to be very difficult. The design of the system depends on being able to choose very large integers that are known to be prime. Thus, the issue of checking whether or not a particular very large number is prime becomes significant in this system. The new algorithm that verifies that testing for primality can be done in polynomial time is, unfortunately, not speedy enough to be used in cryptographical applications unless it can be modified in some way that speeds it up significantly. Furthermore, the fact that numbers can be tested in polynomial time to see if they are prime in no way affects the security of RSA to the best of current knowledge. RSA's security depends on the complexity not of checking if a number is prime but of factoring numbers into primes. |
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance |