Как найти простое число p, для которого (p - 1) / 2 также будет простым (алгоритм Диффи-Хелмана)

Друзья! Нужно реализовать алгоритм Диффи-Хелмана. И использовать, то есть числа должны быть не маленькими демонстрационными, но достаточно большими.

А где их брать?

Число p я решил взять здесь
Там, правда, ограничение в 128 цифр, но лучше ничего не нашёл.



Инструмент для работы с большими числами есть, класс Verylong на плюсах.

++++++++++++++++++++++++++

Дело в том, что не каждое найденное число p подойдёт, а нужно также проверять (p - 1) / 2 на простоту; назовём его p_0

И в этом-то вся загвоздка. Например, на указанном выше сайте я взял случайное простое число p.

4564765766786237648768678267813467832652 36523682634685634890963

Нашёл p_0

2282382883393118824384339133906733916326 18261841317342817445481

И как же мне проверить его на простоту? На сайте, который я указал, проверка делается и для моей задачи она бы подошла. Но дело в том, что если p_0 не окажется простым, то мне нужно вновь будет генерить p, находить p_0 и вновь проверять его на этом сайте на простоту. И всё вручную. И сколько таких попыток нужно будет сделать- неизвестно, может 10, а может 1000000. Вручную. Не подходит такой вариант мне.

++++++++++++++++++++++++++

Спас бы такой инструментарий:

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

и

2) Генератор простых чисел. Можно, конечно, реализовать решето Эратосфена. Но этот алгоритм, как я понял, работает в промежутке от 1 до n, то есть ОЧЕНЬ ДОЛГО, опять миллионы лет. А мне нужно искать сразу большие числа то есть рассматривать, промежуток, к примеру от 10000000000 до 10000000000000000. Такие дела.

Где такой инструментарий знать, я не знаю. Может, кто что подскажет, может онлайн генераторы какие путёвые есть? Спасибо, кто откликнется.

0

Нужно просто найти пару подходящих чисел в интернете.

0

Сообщение от Shamil1 Нужно просто найти пару подходящих чисел в интернете.

понятное дело, что в интернете. А где именно в интернете? На локальный комп я скачал какую-то программу, так она работает долго. А для шифрования используются числа порядка 10 в сотой.

0

Взять, например, это инструмент
http://www.softpedia.com/get/O... ator.shtml

За час-другой сгенерил мне 500 простых чисел, начиная от 100000000. Среди них удовлетворяющих условию (если p простое число, то (p - 1) / 2 тоже простое число), вот они:

100000127 100000463 100000799 100001843 100002899 100004159 100004519 100005107 100005623 100005923 100006799 100007099 100007807 100007879 100008023 100008323 100008479 100008803

Это на 500! А работать нужно, подчёркиваю в полевых условиях, то есть работать с числами порядка 10 в сотой.

То есть искать солидный ресурс в инете. Такой, чтобы генерил такие числа, только шуба бы заворачивалась. Есть такой в природе или комп для этого нужно мастырить?

0

у меня где-то были простые числа в 1024 бита и в 2048 бит.
Надо?

Добавлено через 2 минуты
В своё время я занимался такой проблемой как генерация простых чисел.
И я чуть не поседел).
Короче нет в нете генераторов таких чисел и вообще не понятно откуда они беруться.
Но в любом случае можете взять простое число из ГОСТ 34.10
и из американских стандартов для алгоритам какого-то. не помню уже. Для AES что ли...

Добавлено через 25 секунд
НО! они бубут в 16 ричной Системе Счисления.

0

Сообщение от dan24 Но в любом случае можете взять простое число из ГОСТ 34.10

А где их там брать-то?

0

Вот хороший сайт, где можно скачать стандарты:
http://meganorm.ru/list/8-0.htm
Вот гост:
http://meganorm.ru/Index/6/6784.htm
Смотрите там примеры. p- это простое число. Там 2 примера, вам наверное хватит. Также я в нете нашёл какого-то чувака из университета США, так он свои простые числа сгенерировал.
Воте ещё кривые:
http://www.secg.org/SEC2-Ver-1.0.pdf
Гуглится этот стандарт по запросу:
parameters for elliptical curve NIST
Вы дальше википедии ничего не видите что-ли?

Добавлено через 1 минуту

Сообщение от dan24 Но в любом случае можете взять простое число из ГОСТ 34.10

Из ГОСТа, а не из википедии.

Добавлено через 5 минут
Сейчас я чисто случайно открыл ГОСТ за 94 год. Я слышал, что он очень жёсткий, поэтому даже не открывать не стал в своё время.
В общем ознакомтесь с ним. В разделе 7 есть алгоритм генерирования простых чисел порядка 512 бит!
Конечно сейчас 512 - малова-то. Но наверное можно как-то переделать этот алгоритм так, чтобы он выдавал числа длинной и 1024 бита.

А вообще я так и не нашёл нормальных алгоритмов вычисления параметров для элептической кривой.

Например амеры предлагают брать параметр a=1. Мне кажется, что это как-то не правильно.

Добавлено через 15 секунд
http://meganorm.ru/Index/46/46926.htm - ссылку забыл)

Добавлено через 9 минут
Кстати на C# есть проекта позволяющие генерировать простые числа. НО! Эти поекты работают для чисел порядка 100000.
У меня комп i-7, 4 ядра физически, 8 процессов. Чтобы сгенерировать такое число я потратил по моему около часа.
Когда я генерировал число порядка 10^6. Я и за 2 часа не смог его создать. Т.е. сгенерировать простое число- ну никак нельзя дома имея опенсоурсные решения. Нужно заранее знать, что число простое. В принципе алгоритм из госта 94 года хороший для этого. По крайней мере он есть.

Для ознакомления можете посмотреть признаки простого числа. Есть статьи на хабрахабре. КОрчое я их читал, читал. И понял, что простые числа слишком сложны для меня))). Особенно в плане генерации).

0

Сообщение от dan24 Когда я генерировал число порядка 10^6. Я и за 2 часа не смог его создать.

Как это?
Я за 10 сек простой программой (в одном потоке) сгенерировал 10⁶ простых чисел. Последнее - 15,485,867.

0

значит у меня плохая программа была.
Я на c# прогаю. Он для таких дел не очень).

Что скажите по поводу алгоритма из -94 ГОСта?

Добавлено через 1 минуту
Но всё равно это не тот порядок, который нужен.
Не помню я порядок который нужен, но это выходит за пределы 10^9 точно.

0