Как находят большие простые числа?

[Bulinator]

Привет всем.

Пытаюсь найти очень большое(~200-300 десятичных символов) простое число для имплементациии протокола RSA.
Подскажите, пожалуйста, как это вообще делается. Может есть готовые библиотеки.

Заранее спасибо.

[AndreUT]

С помощью теоремы Диемитко как вариант. Есть ГОСТовские алгоритмы получения простых, которые построены на этой теореме. :)

[venco]

Для RSA обычно используют псевдо-простые числа, проверенные тестом Миллера-Рабина. Этот тест реализован во многих библиотеках для работы с большими числами, даже в java.math.BigInteger.probablePrime().

-- Вс июл 20, 2014 14:23:46 --

AndreUT в сообщении #889000 писал(а):

С помощью теоремы Диемитко

Первый раз слышу. Возможно, сказывается то, что это всё я изучал самостоятельно. Правда гугл находит только 341 страницу по запросу "теорема Диемитко", причём только упоминания. Формулировки теоремы я пока не нашёл.

[Bulinator]

Спасибо за ответы.

Мне реально нужно найти такие числа. Погуглив я нашел библиотеку C++ GMP. Там имеется функция mpz_probab_prime_p , которая по-ходу использует именно алгоритма Миилера-Рабина.

Собственно вопрос в следующем: уменя комп Intel Core i5 3.10GHz, RAM: 8Gb далее не важно.

Я беру с какое-нибудь 200-значное число и последовательно инкрементирую его, пока тест не выдаст true. Это серьезно? За какое время я найду парочку таких чисел?

[Xaositect]

Bulinator в сообщении #889006 писал(а):

Мне реально нужно найти такие числа. Погуглив я нашел библиотеку C++ GMP. Там имеется функция mpz_probab_prime_p , которая по-ходу использует именно алгоритма Миилера-Рабина.

Там есть еще mpz_nextprime.

[Bulinator]

Xaositect в сообщении #889011 писал(а):

Там есть еще mpz_nextprime.

Уххх... Спасибо.
Я немного боюсь начинать, ибо не представляю сколько нахождение одного такого числа может продлиться. Может есть оценки?


И еще, есть еще какие-то критерии, которым должны удовлетворять простые числа для RSA. Например, не иметь вид $2^p\pm 1$ и.т.д.
Где найти весь список этих условий. Может есть библиотека, которая это все проверяет?

[Xaositect]

Bulinator в сообщении #889012 писал(а):

Я немного боюсь начинать, ибо не представляю сколько нахождение одного такого числа может продлиться. Может есть оценки?

У меня полторы секунды прошло, я сделал случайное число от $2^{2048}$ до $2^{2049}$ и вызвал на нем mpz_nextprime. Процессор Intel i5-3570K, 3.4 GHz.

-- Вс июл 20, 2014 22:42:40 --

Вообще есть библиотеки криптографии, напр. openssl, libgcrypt, nettle.

Вот, например, код из nettle, с комментариями и ссылками на Handbook of Applied Cryptography: https://git.lysator.liu.se/nettle/nettl ... om-prime.c

[venco]

Bulinator в сообщении #889006 писал(а):

Я беру с какое-нибудь 200-значное число и последовательно инкрементирую его, пока тест не выдаст true. Это серьезно? За какое время я найду парочку таких чисел?

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

[Xaositect]

Bulinator в сообщении #888998 писал(а):

для имплементациии протокола RSA.

Да, стандартное предупреждение: не используйте это ваше RSA после того, как Вы его реализуете. Используйте проверенные библиотеки, читайте их код, если никому не доверяете.

[AndreUT]

venco в сообщении #889003 писал(а):

Для RSA обычно используют псевдо-простые числа, проверенные тестом Миллера-Рабина. Этот тест реализован во многих библиотеках для работы с большими числами, даже в java.math.BigInteger.probablePrime().

-- Вс июл 20, 2014 14:23:46 --

AndreUT в сообщении #889000 писал(а):

С помощью теоремы Диемитко

Первый раз слышу. Возможно, сказывается то, что это всё я изучал самостоятельно. Правда гугл находит только 341 страницу по запросу "теорема Диемитко", причём только упоминания. Формулировки теоремы я пока не нашёл.

http://apmi.bsu.by/assets/files/tasks/task18.pdf
Первая ссылка

[Bulinator]

Xaositect в сообщении #889018 писал(а):

не используйте это ваше RSA после того, как Вы его реализуете. Используйте проверенные библиотеки, читайте их код, если никому не доверяете.

Я не именно RSA имплементирую а, так называемый coin-flipping protocol
http://www.comp.nus.edu.sg/~hugh/presen ... ipping.pdf

Его проверенную библиотеку нигде не нашел. Можете прокомментировать?

-- Вс июл 20, 2014 21:06:23 --

Используется синтаксис C++

#include <cstdlib>
#include <math.h>
#include <iostream>
#include "gmp.h"
#include <string.h>

using namespace std;

/*
 * 
 */
int main(int argc, char** argv) {

    mpz_t a,b;
    mpz_init(a);
    mpz_init(b);
    
    mpz_set_str(a,"1234567890",10);
    //mpz_set_str(b,"0",10);
    //a=45;
    mpz_nextprime(b,a);
    char *x;
    cout<<mpz_get_str(x,10,b)<<endl;
    cout<<mpz_probab_prime_p(b,35)<<endl;
    return 0;
}

Ответ на ноутбуке Intel® Core™2 Duo CPU T5470 @ 1.60GHz × 2 , RAM 3.9 GiB:

1234567891
1

RUN FINISHED; exit value 0; real time: 0ms; user: 0ms; system: 0ms

Для числа "1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890"

1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234568879
1

RUN FINISHED; exit value 0; real time: 40ms; user: 0ms; system: 10ms

[maxal]

См. Случайное простое число в Википедии.

[Karan]

Сообщение пользователя Izigro отделено в Карантин