Есть ли метод генерации большого простого числа с факторизацией p — 1?

Question

[Ян]

Здравствуйте!
Есть задача - построить большое простое число(порядка 2-3к бит) с заранее известной факторизацией p - 1.
Это необходимо, чтобы найти первообразные корни(пытаюсь реализовать протокол Диффи-Хеллмана)

Comments

[Рональд Макдональд]

Держите в курсе.

[Wataru]

Что значит, с заранее известной факторизацией? Так-то если она дана, то p-1 известно, а значит и p фиксировано. Или надо, чтобы p-1 делилось на заданные простые числа?

[Ян]

wataru, есть подозрения, что существует метод такой, что в процессе построения простого числа можно сразу определять факторизацию p-1, именно это и значит вопрос.

[Wataru]

Ян, Т.е, вам надо получить большое простое число и вместе с ним факторизацию p-1?

Answer 1

[cicatrix]

Для изобретения велосипеда и обучения тому, как всё это работает, генерить большие числа не требуется.
Если уж очень хочется - то вот, ознакомьтесь. Ну и либо Решето Аткина, ну или того же Эратосфена.
Это первое.
Второе: никогда, никогда, никогда, никогда, никогда не пытайтесь реализовать криптографические алгоритмы для любых целей, кроме образовательных. Никогда не используйте собственную реализацию для защиты хоть чего-либо важного. Я вас, конечно, не знаю, но докторской степени по математике и нескольких лет опыта в криптографии и криптоанализе у вас, скорее всего, нет.

Comments

[Ян]

Спасибо за внимание к теме, но хотелось бы услышать ответ на мой вопрос. Если Вы так за меня волнуетесь, то скажу Вам, что я студент и этот вопрос я задал сугубо из академического интереса. И уж точно я бы не собирался использовать собственную реализацию в криптографии для защиты чего-либо без хотя бы кандидатской степени и нескольких лет опыта в этой сфере.

[cicatrix]

Ян, Я вам дал 3 ссылки. Собственно, это всё. Генерация простых чисел - дело не простое (в плане вычислительной сложности). Сами алгоритмы довольно просты.
https://en.wikipedia.org/wiki/Generation_of_primes...

Впрочем, можно и сжульничать, взять данные с существующих генераторов онлайн.
Вот отсюда, например.
https://www.numberempire.com/primenumbers.php

[Ян]

cicatrix, мне не нужно генерировать много простых чисел, к тому же больших. Конечно, если искать все простые числа это довольно долго, однако существуют довольно легкие алгоритмы построения одного большого и простого числа, даже есть алгоритм построения числа с получением числа, который будет являтся делителем p - 1. Это я все прекрасно знаю и спасибо ещё раз за советы, но обычная генерация простого и большого числа не является для меня проблемой, пусть даже 3-4к бит. Мне нужно построить число с заранее известной факторизацией p-1, поэтому я и опубликовал свой вопрос здесь, в надежде что мне кто-то подскажет в какую сторону копать.

[cicatrix]

Ян, Мне подобные алгоритмы неизвестны, действительно интересно, существуют ли таковые в природе. Что-то мне подсказывает, что нет, иначе бы вычислительная сложность, на которой основываются современные криптосистемы была бы недостаточной.
В любом случае, если ВДРУГ обнаружите подобный алгоритм, не сочтите за труд, дайте ссылочку на него при ответе, действительно интересно.

[cicatrix]

Ян, Если не пользоваться вероятностными алгоритмами ( wataru упомянул алгоритм Миллера-Рабина), который может протестировать с определённой долей вероятности, что число простое, то никаких чудес нет.
Генерация происходит теми же школьными алгоритмами, либо генерируются случайные числа и тестируются на то, что они простые.

Проверка числа n заключается в проверке его нечётности и проверке, делится ли оно без остатка на каждое целое нечётное число d. 1 < d < sqrt(n).

Answer 2

[Wataru]

Можно такой подход: Сгенерируйте два случайных простых числа длиной n/2 бит (Генерируйте случайное число, пока не получили простое). Потом перемножте их, прибавьте 1 и проверьте, что тоже результат простой.

Для этого надо уметь относительно быстро проверять что число простое. Можно использовать метод Миллера-Рабина. Он вероятностный, но увеличивая число итераций можно достичь произвольно маленькой вероятности ошибки.