Editing Blum Blum Shub (section)

==Security==
There is a proof reducing its security to the [[Computational complexity theory|computational difficulty]] of factoring.{{sfn|Blum|Blum|Shub|1986|pp=364–383}} When the primes are chosen appropriately, and [[big O notation|''O'']]([[logarithm|log]] log ''M'') lower-order bits of each ''x<sub>n</sub>'' are output, then in the limit as ''M'' grows large, distinguishing the output bits from random should be at least as difficult as solving the [[quadratic residuosity problem]] modulo ''M''.

The performance of the BBS random-number generator depends on the size of the modulus ''M'' and the number of bits per iteration ''j''. While lowering ''M'' or increasing ''j'' makes the algorithm faster, doing so also reduces the security. A 2005 paper gives concrete, as opposed to asymptotic, security proof of BBS, for a given ''M'' and ''j''. The result can also be used to guide choices of the two numbers by balancing expected security against computational cost.<ref>{{cite book |last1=Sidorenko |first1=Andrey |last2=Schoenmakers |first2=Berry |chapter=Concrete Security of the Blum-Blum-Shub Pseudorandom Generator |title=Cryptography and Coding |series=Lecture Notes in Computer Science |date=2005 |volume=3796 |pages=355–375 |doi=10.1007/11586821_24|isbn=978-3-540-30276-6 }}</ref>