2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Как находят большие простые числа?
Сообщение20.07.2014, 21:02 
Заслуженный участник
Аватара пользователя


30/10/10
1481
Ереван(3-й участок)
Привет всем.

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

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

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение20.07.2014, 21:12 


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

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение20.07.2014, 21:16 
Заслуженный участник


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

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

AndreUT в сообщении #889000 писал(а):
С помощью теоремы Диемитко
Первый раз слышу. Возможно, сказывается то, что это всё я изучал самостоятельно. Правда гугл находит только 341 страницу по запросу "теорема Диемитко", причём только упоминания. Формулировки теоремы я пока не нашёл.

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение20.07.2014, 21:28 
Заслуженный участник
Аватара пользователя


30/10/10
1481
Ереван(3-й участок)
Спасибо за ответы.

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

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

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

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение20.07.2014, 21:33 
Заслуженный участник
Аватара пользователя


06/10/08
6119
Bulinator в сообщении #889006 писал(а):
Мне реально нужно найти такие числа. Погуглив я нашел библиотеку C++ GMP. Там имеется функция mpz_probab_prime_p , которая по-ходу использует именно алгоритма Миилера-Рабина.
Там есть еще mpz_nextprime.

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение20.07.2014, 21:37 
Заслуженный участник
Аватара пользователя


30/10/10
1481
Ереван(3-й участок)
Xaositect в сообщении #889011 писал(а):
Там есть еще mpz_nextprime.

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


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

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение20.07.2014, 21:41 
Заслуженный участник
Аватара пользователя


06/10/08
6119
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

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение20.07.2014, 21:42 
Заслуженный участник


04/05/09
4462
Bulinator в сообщении #889006 писал(а):
Я беру с какое-нибудь 200-значное число и последовательно инкрементирую его, пока тест не выдаст true. Это серьезно? За какое время я найду парочку таких чисел?
Мне кажется, это плохой способ, недостаточно случайный. Вроде-бы надо генерить случайное число нужного размера, потом проверять его простоту.

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение20.07.2014, 21:49 
Заслуженный участник
Аватара пользователя


06/10/08
6119
Bulinator в сообщении #888998 писал(а):
для имплементациии протокола RSA.
Да, стандартное предупреждение: не используйте это ваше RSA после того, как Вы его реализуете. Используйте проверенные библиотеки, читайте их код, если никому не доверяете.

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение20.07.2014, 21:52 


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

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

AndreUT в сообщении #889000 писал(а):
С помощью теоремы Диемитко
Первый раз слышу. Возможно, сказывается то, что это всё я изучал самостоятельно. Правда гугл находит только 341 страницу по запросу "теорема Диемитко", причём только упоминания. Формулировки теоремы я пока не нашёл.


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

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение20.07.2014, 21:58 
Заслуженный участник
Аватара пользователя


30/10/10
1481
Ереван(3-й участок)
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

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение26.07.2014, 14:58 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Как находят большие простые числа?
Сообщение18.11.2016, 12:37 
Модератор


19/10/15
1197
 !  Сообщение пользователя Izigro отделено в Карантин

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group