Saturday 18 June 2011


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.