How to generate prime p (minimum 2048 bits) and q (minimum 224 bits) where q | p-1

Question

i want to test my algorithm, but I need a pair of p and q where q|p-1, minimum length of p = 2048 bits, and minimum length of q = 224 bits.

I can find p with Wolframalpha by using NextPrime[2^2048] or SageMath by using prime.next(pow(2,2048)) where prime = Primes().

But, finding q is hard to me. I tried with elliptic curve method (ecm.factor(p-1)) in SageMath and find the factors which have minimum length 224, it spends all night (over 10 hours already and still running).

Anyone can help me, what is the best way to find it? or anyone can share one pair of p (min 2048) and q (min 224) (I just want to test it)?

Answer 1

Choose a prime q and a multiplier k of a suitable magnitude, then calculate the corresponding p = k × q + 1. If p is prime, you're done. Otherwise, increment k and try again.