RSA vs RNG (rsa-vs-rng)

cryptohack

Task: RSA where primes P,Q are produced by an LCG mod 2^512 (known A,B); get_prime skips composites so Q = A^k·P + C_k (mod 2^512) for a small unknown gap k. Solution: substitute into N=P·Q to get a quadratic A^k·P^2 + C_k·P - N ≡ 0 (mod 2^512); solve it by bit-by-bit Hensel lifting for each k=1,2,3,..., test P|N over the integers (found at k=180), then standard RSA decrypt.