Я пытаюсь реализовать простое поколение RSA для P и Q на основе спецификации FIP186-4.Спецификация описывает две различные реализации: Раздел 3.2. Обеспечиваемая основная конструкция против Раздела 3.3. Возможная основная конструкция.Первоначально я пытался реализовать подход вероятного простого числа, потому что его легче понять и реализовать, но я обнаружил, что он очень медленный из-за количества итераций, необходимых для нахождения простых чисел P и Q (в худшем случае это занимает 15 минут).Затем я решил попробовать доказуемый простой подход, но обнаружил, что алгоритм намного сложнее и может быть медленным.Ниже приведены мои два вопроса:
В Разделе C.10, Шаг 12, как исключить sqrt (2) для выражения x = floor (sqrt (2)) (2 ^(L − 1))) + (x mod (2 ^ L - floor ((sqrt (2) (2 ^ (L − 1))))), чтобы я мог представить его как целые числа, используя представление BigNum?
В разделе C.10, шаг 14, существует ли быстрый способ вычисления y в интервале [1, p2], такой что 0 = (y p0 p1–1) mod p2?Спецификация не определяет метод для реализации этого. Первоначально я хотел выполнить линейный поиск, начиная с целого числа 1 и выше, но это может быть очень медленно, потому что p2 может быть очень большим числом.
Я попытался найти в Интернете справку по этой проблеме, но обнаружил, что многие примеры даже не соответствуют FIPS186-4. Я предполагаю, что это потому, что эти два метода слишком медленные.