Quadratic sieve is used to factorize number. I want to know if QS work better with M = p * q numbers, p and q primes, both congruent to 3 (mod 4). M is used in BBS.
Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blumand Michael Shub.[1]
Blum Blum Shub takes the form:
x_{n+1} = x_n^2 \bmod M
where M=pq is the product of two large primes p and q. At each step of the algorithm, some output is derived fromxn+1; the output is commonly either the bit parity of xn+1 or one or more of the least significant bits of xn+1.
The seed x0 should be an integer that is co-prime to M (i.e. p and q are not factors of x0) and not 1 or 0.
The two primes, p and q, should both be congruent to 3 (mod 4) (this guarantees that each quadratic residue has one square root which is also a quadratic residue) and gcd(φ(p-1), φ(q-1)) should be small (this makes the cycle length large).
An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any xi value directly (viaEuler's Theorem):
x_i = \left( x_0^{2^i \bmod \lambda(M)} \right) \bmod M
where \lambda is the Carmichael function. (Here we have \lambda(M) = \lambda(p\cdot q) = \operatorname{lcm}(p-1, q-1)).
nteger factorization problem is one of the most important parts in the world of cryptography. The security of the widely-used public-key cryptographic algorithm, RSA [1], and the Blum Blum Shub cryptographic pseudorandom number generator [2] heavily depend on the presumed difficulty of factoring a number to its prime constituents. As the size of the number to be factored gets larger, the difficulty of the problem increases enormously. This fact has led to the development of many different algorithms to attack bigger number within polynomial time.