Форум программистов, компьютерный форум CyberForum.ru

Генератор простых чисел - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 5.00
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
05.08.2013, 19:08     Генератор простых чисел #1
Подскажите, пожалуйста, хороший алгоритм (желательно с реализацией) генерации простых чисел (от 512 бит). Текущий алгоритм работает примерно в 4 раза медленнее, чем аналогичный в openssl. Разобраться в openssl не получилось, буду рад любой помощи. Спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.08.2013, 19:08     Генератор простых чисел
Посмотрите здесь:

Нужен генератор простых чисел на C++ C++
Массив целых чисел состоит из n элементов, найти сумму простых чисел, входящих в него C++
C++ Дана последовательность целых чисел а1, а2, …, an. Выяснить, является ли она симметричной последовательностью простых чисел
C++ Составить программу – генератор простых чисел, в основу положить формулу 2x2 + 29 при 0<=x<=28.
генератор простых чисел в С++, в основу положить формулу 2x2 + 29 при 0<=x<=28 C++
C++ Дан массив целых чисел. Верно ли, что он состоит только из простых чисел?
C++ как вычислить количество простых чисел среди положительных чисел массива
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
05.08.2013, 20:14     Генератор простых чисел #2
Цитата Сообщение от vlad_light Посмотреть сообщение
Текущий алгоритм работает примерно в 4 раза медленнее, чем аналогичный в openssl.
"текущий алгоритм" можно увидеть?
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
06.08.2013, 03:26  [ТС]     Генератор простых чисел #3
Миллера-Рабина, реализацию скину завтра в лс
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
06.08.2013, 06:04     Генератор простых чисел #4
Цитата Сообщение от vlad_light Посмотреть сообщение
от 512 бит
Таких чисел нету
От мой маленький алгоритм для не больших чисел
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using std::cout;
using std::endl;
#include <vector>
using std::vector;
#include <cstdlib>
using std::exit;
#include <algorithm>
using std::remove;
 
int main()
{
    int mass[1000];
    for(int i=0;i<=999;i++)
        mass[i]=i;
 
    for(int i=2;i<=999;i++)
    {
        if(mass[i]==0) continue;
        //cout <<i<<endl;
        for(int n=i+i;n<999;n=n+i)
        {
            mass[n]=0;
        }
    }
 
    //exit(1);
    int* end=remove(mass,mass+sizeof(mass)/sizeof(int),0);
 
    //вывод массива простых чисел
    for(int* i=mass;i!=end;i++)
        cout <<*i<<endl;
 
 
    return 0;
}
0x10
06.08.2013, 06:13
  #5

Не по теме:

Цитата Сообщение от ninja2 Посмотреть сообщение
Таких чисел нету
С чего вдруг?

ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
06.08.2013, 06:21     Генератор простых чисел #6
Цитата Сообщение от 0x10 Посмотреть сообщение
С чего вдруг?
Ну и какое число будет, если int 4 байта, а там от 512 бит это 512*8 байт ???
0x10
06.08.2013, 06:24
  #7

Не по теме:

Цитата Сообщение от ninja2 Посмотреть сообщение
512 бит это 512*8 байт ???
Логика сегодня подвергается жестокому испытанию...

ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
06.08.2013, 06:26     Генератор простых чисел #8
Цитата Сообщение от 0x10 Посмотреть сообщение
Логика сегодня подвергается жестокому испытанию...
Ой перепутал 512/8 байт
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
12080 / 6941 / 782
Регистрация: 27.09.2012
Сообщений: 17,227
Записей в блоге: 2
Завершенные тесты: 1
06.08.2013, 06:32     Генератор простых чисел #9
Цитата Сообщение от ninja2 Посмотреть сообщение
Ой перепутал 512/8 байт
Ну и что? Когда-нибудь слышали про длинную арифметику?

Добавлено через 34 секунды

Не по теме:

Цитата Сообщение от ninja2 Посмотреть сообщение
Таких чисел нету
я же говорил, бесконечности не существует - это миф

salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
06.08.2013, 09:46     Генератор простых чисел #10
Цитата Сообщение от vlad_light Посмотреть сообщение
Миллера-Рабина, реализацию скину завтра в лс
не знал, что это генератор простых чисел, извините.

Добавлено через 10 секунд
Цитата Сообщение от vlad_light Посмотреть сообщение
Миллера-Рабина, реализацию скину завтра в лс
не знал, что это генератор простых чисел, извините.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
06.08.2013, 13:03     Генератор простых чисел #11
Цитата Сообщение от Croessmah Посмотреть сообщение
Ну и что? Когда-нибудь слышали про длинную арифметику?
Ага, свой класс делал для больших целых и 1000 факториал считал с помощью него, тоже громадное число.
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
06.08.2013, 13:26  [ТС]     Генератор простых чисел #12
Таких чисел нету
От мой маленький алгоритм для не больших чисел
Спасибо, очень хороший алгоритм. Пожалуй, послушаю других участников форума...
не знал, что это генератор простых чисел, извините.
Надеюсь, это был не сарказм и Вы поняли, что я имел ввиду.
Кстати, забыл уточнить. Простое число также должно быть случайным с распределением близким к равномерному.
nonedark2008
759 / 517 / 95
Регистрация: 28.07.2012
Сообщений: 1,381
06.08.2013, 14:05     Генератор простых чисел #13
vlad_light, хороший псевдокод по тесту Рабина-Милеера есть в википедии. Но тут самое сложное не сам тест, а именно длинная арифметика.(Конечно, если ее реализовывать эффективно)
Для генерации случайных чисел для теста Р-М можно использовать функцию CryptGenRandom.
Я бы кинул свою фигню, которую реализовывал для RSA, но там нет комментов, куча ассемлера и алгоритмов.
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
06.08.2013, 14:28  [ТС]     Генератор простых чисел #14
хороший псевдокод по тесту Рабина-Милеера есть в википедии
Там не описана, например, оптимизация, которая проверяет: делится ли число на некий набор простых чисел (напр. от 3 до 1024), что отсеивает около 80% составных чисел (пруфлинка пока нет, но могу поискать). У тебя есть на примете ещё какие-то оптимизации? Заранее очень благодарен!
можно использовать функцию CryptGenRandom
Я использую самостоятельно написанный её аналог (по скорости идентичны).
Я бы кинул свою фигню, которую реализовывал для RSA, но там нет комментов, куча ассемлера и алгоритмов.
Кинь в лс, пожалуйста, попробую разобраться. В асм тоже уже немного разбираюсь
nonedark2008
759 / 517 / 95
Регистрация: 28.07.2012
Сообщений: 1,381
06.08.2013, 14:56     Генератор простых чисел #15
Кину тут ссыль. Через денек другой файл по ссылке удалю.
Цитата Сообщение от vlad_light Посмотреть сообщение
оптимизация, которая проверяет: делится ли число на некий набор простых чисел
Там это тоже есть.
Для длинной арифметики за основу взял один из проектов, но потом все переделал. От прежнего осталась считай только иерархия классов. У меня даже вроде осталась литература с алгоритмами, которую я юзал. Если надо - скину.

Добавлено через 2 минуты
Цитата Сообщение от vlad_light Посмотреть сообщение
что отсеивает около 80% составных чисел
А можно вообще при генерации рандомных чисел у каждого устанавливать первый бит в единицу - сразу откинется половина неподходящих вариантов.

Добавлено через 43 секунды
Кстати, для норм работы проекта нужна поддержка SSE4.

Добавлено через 15 минут
Кажись вот эту штуку я брал за основу.
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
06.08.2013, 15:47  [ТС]     Генератор простых чисел #16
при генерации рандомных чисел у каждого устанавливать первый бит в единицу
Да, так и делается. Там по определению в алгоритме нужно выбирать нечетное число.
только иерархия классов
У меня проект на си, надеюсь много переделывать не придётся
А длинная арифметика у меня тоже вся реализована. Кстати, работает гораздо быстрее, чем bigint.
Любую литературу (кроме Кнута/Кормена, их уже выучил) буду рад взглянуть.
nonedark2008
759 / 517 / 95
Регистрация: 28.07.2012
Сообщений: 1,381
06.08.2013, 15:59     Генератор простых чисел #17
vlad_light, тут много интересных алгоритмов с доказательствами. Оттуда я брал метод Баррета для быстрого деления.
Тута я подчерпнул идею для ускорения умножения в столбик с помощью векторных операций процессора.
Ну и Кормен и Кнут - это понятно.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16934 / 5339 / 328
Регистрация: 30.03.2009
Сообщений: 14,343
Записей в блоге: 26
06.08.2013, 18:52     Генератор простых чисел #18
Цитата Сообщение от ninja2 Посмотреть сообщение
Таких чисел нету
Чисто для самообразования. Криптографические алгоритмы основаны на использовании простых чисел. Чтобы увеличить криптостойкость алгоритма, нужно увеличивать размер числа. Со временем быстродействие вычислительной техники растёт, а потому то, что 15 лет назад считалось криптостойким, на сегодняшний день является полной лажей, т.к. методом перебора на современных процессорах всё это дело взламывается за сравнительно небольшой срок. Поэтому со временем растёт и длина чисел, используемых в криптографии, чтобы на современных процессорах требовалось большое время для взлома

Цитата Сообщение от ninja2 Посмотреть сообщение
От мой маленький алгоритм для не больших чисел
Твой алгоритм годится разве что для школьных задач, поскольку является квадратичным. Твоим алгоритмом найти простое число для нужд современной криптографии потребуется несколько лет. Постановка вопроса в данной теме выходит далеко за пределы школьного курса информатики
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
06.08.2013, 19:18     Генератор простых чисел #19
Цитата Сообщение от Evg Посмотреть сообщение
Чисто для самообразования. Криптографические алгоритмы основаны на использовании простых чисел. Чтобы увеличить криптостойкость алгоритма, нужно увеличивать размер числа. Со временем быстродействие вычислительной техники растёт, а потому то, что 15 лет назад считалось криптостойким, на сегодняшний день является полной лажей, т.к. методом перебора на современных процессорах всё это дело взламывается за сравнительно небольшой срок. Поэтому со временем растёт и длина чисел, используемых в криптографии, чтобы на современных процессорах требовалось большое время для взлома



Твой алгоритм годится разве что для школьных задач, поскольку является квадратичным. Твоим алгоритмом найти простое число для нужд современной криптографии потребуется несколько лет. Постановка вопроса в данной теме выходит далеко за пределы школьного курса информатики
Школьный курс информатики тоже, знаете ли, ни пальцемъ деланый...)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.08.2013, 17:11     Генератор простых чисел
Еще ссылки по теме:

C++ Составить программу-генератор простых чисел, в основу положить формулу 2*(x)^2 + 29 при 0 ≥ х ≥ 28
Генератор простых чисел C++
Генератор простых арифметических примеров C++
Реализовать генератор простых чисел с использованием решета Эратосфена и перебора делителей C++
C++ Вычислить количество простых чисел среди положительных чисел массива

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
silent_1991
10.08.2013, 17:11     Генератор простых чисел
  #20

Не по теме:

Evg, не спорьте с гуру. Гуру сказал, что таких больших чисел нет - значит их нет!

Yandex
Объявления
10.08.2013, 17:11     Генератор простых чисел
Ответ Создать тему
Опции темы

Текущее время: 07:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru