Application of quantum computation to various categories of problems
- Grover's algorithm. Provides quadratic speedup for many search problems.
- Shor's algorithm. Provides exponential speedup for factorizing a number.
- Deutsch-Jozsa. Criterion of balance for Boolean function.
(Pseudo) Random number generators
- Blum Blum Shub. Based on a formula on prime numbers.
- Mersenne twister. By Matsumoto Nishimura, fast and with high period.
- Lagged Fibonacci generator. Improvement of Linear congruential generator, uses the Fibonacci sequence.
- Linear congruential generator. One of oldest, not the best, use three numbers to generate a sequence.
- Yarrow algorithm. By Bruce Schneier, John Kelsey, and Niels Ferguson. Cryptographically secure pseudorandom numbers generator, can also be used as a real random number generator, accepting random inputs from analog random sources.
- Fortuna. Allegedly an improvement on Yarrow algorithm.
- Linear feedback shift register. A shift register whose input bit is a linear function of its previous state. The first state is the seed.