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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 5.00
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
#1

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

05.08.2013, 19:08. Просмотров 1912. Ответов 19
Метки нет (Все метки)

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

Генератор простых чисел - C++
задача: написать генератор простых чисел до заданного пользователем значения. Плз помогите.

Нужен генератор простых чисел на C++ - C++
Оч. нужен генератор БОЛЬШИХ простых чисел и, соответственно, класс под него. (размерность числа - 1024 в двоичном виде)

генератор простых чисел в С++, в основу положить формулу 2x2 + 29 при 0<=x<=28 - C++
Помогите составить программу – генератор простых чисел в С++, в основу положить формулу 2x2 + 29 при 0&lt;=x&lt;=28

Реализовать генератор простых чисел с использованием решета Эратосфена и перебора делителей - C++
В этой задаче мы реализуем генератор простых чисел. Простыми называются положительные целые, не имеющие делителей кроме 1 и самого числа....

Составить программу – генератор простых чисел, в основу положить формулу 2x2 + 29 при 0<=x<=28. - C++
Помогите решить задачу в С++ Составить программу – генератор простых чисел, в основу положить формулу 2x2 + 29 при 0&lt;=x&lt;=28.

Составить программу-генератор простых чисел, в основу положить формулу 2*(x)^2 + 29 при 0 ≥ х ≥ 28 - C++
Составить программу-генератор простых чисел, в основу положить формулу 2*(x)^2 + 29 при 0 ≥ х ≥ 28. Нужно ввести число до которого...

Генератор простых арифметических примеров - C++
Доброго времени суток. Нужно написать программу, которая генерирует примеры, которые нужно решить. Например: 5 + 6 * 2, или 5 + (10 -...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
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
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
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
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
06.08.2013, 06:26     Генератор простых чисел #8
Цитата Сообщение от 0x10 Посмотреть сообщение
Логика сегодня подвергается жестокому испытанию...
Ой перепутал 512/8 байт
Croessmah
Модератор
Эксперт CЭксперт С++
12980 / 7292 / 812
Регистрация: 27.09.2012
Сообщений: 18,007
Записей в блоге: 3
Завершенные тесты: 1
06.08.2013, 06:32     Генератор простых чисел #9
Цитата Сообщение от ninja2 Посмотреть сообщение
Ой перепутал 512/8 байт
Ну и что? Когда-нибудь слышали про длинную арифметику?

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

Не по теме:

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

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

Добавлено через 10 секунд
Цитата Сообщение от vlad_light Посмотреть сообщение
Миллера-Рабина, реализацию скину завтра в лс
не знал, что это генератор простых чисел, извините.
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
882 / 621 / 125
Регистрация: 28.07.2012
Сообщений: 1,661
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
882 / 621 / 125
Регистрация: 28.07.2012
Сообщений: 1,661
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
882 / 621 / 125
Регистрация: 28.07.2012
Сообщений: 1,661
06.08.2013, 15:59     Генератор простых чисел #17
vlad_light, тут много интересных алгоритмов с доказательствами. Оттуда я брал метод Баррета для быстрого деления.
Тута я подчерпнул идею для ускорения умножения в столбик с помощью векторных операций процессора.
Ну и Кормен и Кнут - это понятно.
Evg
Эксперт CАвтор FAQ
17469 / 5707 / 362
Регистрация: 30.03.2009
Сообщений: 15,669
Записей в блоге: 26
06.08.2013, 18:52     Генератор простых чисел #18
Цитата Сообщение от ninja2 Посмотреть сообщение
Таких чисел нету
Чисто для самообразования. Криптографические алгоритмы основаны на использовании простых чисел. Чтобы увеличить криптостойкость алгоритма, нужно увеличивать размер числа. Со временем быстродействие вычислительной техники растёт, а потому то, что 15 лет назад считалось криптостойким, на сегодняшний день является полной лажей, т.к. методом перебора на современных процессорах всё это дело взламывается за сравнительно небольшой срок. Поэтому со временем растёт и длина чисел, используемых в криптографии, чтобы на современных процессорах требовалось большое время для взлома

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



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

Последовательность чисел, определить среднее арифметическое простых чисел - C++
Вводится последовательность целых чисел, 0 – конец последовательности. Определить среднее арифметическое простых чисел ...

Генератор чисел - C++
Народ подскажыте пожалуста как создать свой генератор чисел.

Генератор чисел! - C++
Всем доброго времени суток. Нужна помощь, является задача сгенерировать матрицуNхM случайных чисел с нормальным законом распределения....

генератор чисел - C++
Прошу Вас помочь мне в написание лабораторной работы, мне нужна на языке С Написать генератор псевдослучайных чисел по алгоритму f(n)...

Генератор чисел - C++
числа до 100 помещаются в контейнер, перемешиваются и по нажатии &lt;1&gt;+Enter выводит на экран &quot;генерирование число&quot;, после чего программа...


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

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

Не по теме:

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

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

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