New answers tagged


If $p_0$ and $q_0$ are known then so are $p_i$ and $q_i$ by iterating. To factor $N$, do the following: $(p,q) \gets (p_0,q_0)$ while ($p \nmid N$) do $(p,q) \gets (next\_prime(p^2+q^2), next\_prime(2pq))$ Return $(p,q)$


Instead of using probabilistic methods to generate large primes, as indicated in the other answers, one can (IMHO better) employ Maurer's algorithm of generating provable primes. I have a Python code implementing that algorithm, available at


What you could do, is use a Mill's constant for generation. Then, a test for primarity would be good anyways...(in case that not exact enough constant is chosen, so you could end up with non prime) Mill's constant is such a number, that if powered to 3, and then powered to any N, where N is an usigned integer, we get value V wich, rounded down, is a prime. ...


There is some confusion here. The definition of prime numbers states that cannot be factored (see Definition of prime numbers) You seem to be talking about RSA modulus which is the product of two prime numbers (see RSA cryptosystem). As far as keylength is concerned 768 bits is not considered safe today. Note that the keylength choice is a compromise ...


Unlike the primes used in RSA the prime used in DH does not need to be a secret, so using a well-known prime is not a problem from that point of view. On the other hand much of the work in breaking dh is per-prime not per dh session. That doesn't change the cost of breaking the first session but it does change the average cost of breaking a session. It is ...


The statement "To factorize a number $n$ with the quadratic sieve, we are looking for a product of numbers $x^2−n$ giving a perfect square" is incorrect is only a subset of a possible more general definition: looking for a product of numbers $x^2-k\cdot n$ giving a perfect square (by restricting the numbers to be suitably smooth, factoring them, and using ...

Top 50 recent answers are included