Как сгенерировать простой p (минимум 2048 бит) и q (минимум 224 бит), где q | p-1

Question

Я хочу проверить свой алгоритм, но мне нужна пара p и q, где q | p-1, минимальная длина p = 2048 бит и минимальная длина q = 224 бит.

Я могу найти p с Wolframalpha, используя NextPrime [2^2048] или SageMath, используя prime.next(pow(2,2048)), где prime = Primes().

Но найти q трудно для меня. Я попытался использовать метод эллиптической кривой (ecm.factor(p-1)) в SageMath и найти факторы, которые имеют минимальную длину 224, он проводит всю ночь (более 10 часов уже и все еще работает).

Кто-нибудь может мне помочь, что это лучший способ его найти? или любой может поделиться одной парой p (min 2048) и q (min 224) (я просто хочу проверить его)?

Answer 1

Выберет простой д и множитель к подходящей величины, а затем вычислить соответствующие р = к × д + 1. Если р является простым, вы сделали , В противном случае приращение k и повторите попытку.