, where n is the product of two large primes p and q that
p and q are kept secret.
Among the numerous applications of the elementary properties of quadratic congruences are identification schemes and secure pseudorandom number generators. Public-key identification schemes are the analogs of the Personal Identification Numbers (PIN) or passwords. Public-key identification schemes are designed to protect against security problems that arise when a secret key is compromised. Instead of revealing the secret key to verify a person's identity, these schemes provide a mechanism for a person to prove that he/she knows the secret key. A proof of identity is based on some computation involving this key, and the intermediate results of the computation are different for each identification session. Someone listening to the exchange will not be able to use the data to impersonate, because in a well-designed system, the computations will be different in the next session. The computations are simple enough that they can be performed by embedded electronic circuitry in ``smart cards'' or by client software in a computer network.
The schemes studied in the text are based on the difficulty of solving , where n is the product of two large primes p and q that
p and q are kept secret.
The Blum-Blum-Shub pseudorandom number generator is also based on the difficulty of solving this congruence when the prime factorization of n is not known. The properties of this pseudo-random number generator are discussed in the second section.