Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.73/15: Рейтинг темы: голосов - 15, средняя оценка - 4.73
vlad_light
4 / 4 / 1
Регистрация: 24.09.2012
Сообщений: 178
#1

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

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

Подскажите, пожалуйста, хороший алгоритм (желательно с реализацией) генерации простых чисел (от 512 бит). Текущий алгоритм работает примерно в 4 раза медленнее, чем аналогичный в openssl. Разобраться в openssl не получилось, буду рад любой помощи. Спасибо!

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.08.2013, 19:08
Ответы с готовыми решениями:

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

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

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

Реализовать генератор простых чисел с использованием решета Эратосфена и перебора делителей
В этой задаче мы реализуем генератор простых чисел. Простыми называются...

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

19
salam
175 / 156 / 29
Регистрация: 10.07.2012
Сообщений: 766
05.08.2013, 20:14 #2
Цитата Сообщение от vlad_light Посмотреть сообщение
Текущий алгоритм работает примерно в 4 раза медленнее, чем аналогичный в openssl.
"текущий алгоритм" можно увидеть?
0
vlad_light
4 / 4 / 1
Регистрация: 24.09.2012
Сообщений: 178
06.08.2013, 03:26  [ТС] #3
Миллера-Рабина, реализацию скину завтра в лс
0
ninja2
969 / 188 / 32
Регистрация: 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;
}
0
0x10
06.08.2013, 06:13
  #5

Не по теме:

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

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

Не по теме:

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

1
ninja2
969 / 188 / 32
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
06.08.2013, 06:26 #8
Цитата Сообщение от 0x10 Посмотреть сообщение
Логика сегодня подвергается жестокому испытанию...
Ой перепутал 512/8 байт
0
Croessmah
++Ͻ
14367 / 8149 / 1534
Регистрация: 27.09.2012
Сообщений: 20,086
Записей в блоге: 3
Завершенные тесты: 1
06.08.2013, 06:32 #9
Цитата Сообщение от ninja2 Посмотреть сообщение
Ой перепутал 512/8 байт
Ну и что? Когда-нибудь слышали про длинную арифметику?

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

Не по теме:

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

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

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

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

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

Добавлено через 15 минут
Кажись вот эту штуку я брал за основу.
1
vlad_light
4 / 4 / 1
Регистрация: 24.09.2012
Сообщений: 178
06.08.2013, 15:47  [ТС] #16
при генерации рандомных чисел у каждого устанавливать первый бит в единицу
Да, так и делается. Там по определению в алгоритме нужно выбирать нечетное число.
только иерархия классов
У меня проект на си, надеюсь много переделывать не придётся
А длинная арифметика у меня тоже вся реализована. Кстати, работает гораздо быстрее, чем bigint.
Любую литературу (кроме Кнута/Кормена, их уже выучил) буду рад взглянуть.
0
nonedark2008
1025 / 765 / 211
Регистрация: 28.07.2012
Сообщений: 2,124
06.08.2013, 15:59 #17
vlad_light, тут много интересных алгоритмов с доказательствами. Оттуда я брал метод Баррета для быстрого деления.
Тута я подчерпнул идею для ускорения умножения в столбик с помощью векторных операций процессора.
Ну и Кормен и Кнут - это понятно.
1
Evg
Эксперт CАвтор FAQ
19127 / 6967 / 522
Регистрация: 30.03.2009
Сообщений: 19,612
Записей в блоге: 30
06.08.2013, 18:52 #18
Цитата Сообщение от ninja2 Посмотреть сообщение
Таких чисел нету
Чисто для самообразования. Криптографические алгоритмы основаны на использовании простых чисел. Чтобы увеличить криптостойкость алгоритма, нужно увеличивать размер числа. Со временем быстродействие вычислительной техники растёт, а потому то, что 15 лет назад считалось криптостойким, на сегодняшний день является полной лажей, т.к. методом перебора на современных процессорах всё это дело взламывается за сравнительно небольшой срок. Поэтому со временем растёт и длина чисел, используемых в криптографии, чтобы на современных процессорах требовалось большое время для взлома

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



Твой алгоритм годится разве что для школьных задач, поскольку является квадратичным. Твоим алгоритмом найти простое число для нужд современной криптографии потребуется несколько лет. Постановка вопроса в данной теме выходит далеко за пределы школьного курса информатики
Школьный курс информатики тоже, знаете ли, ни пальцемъ деланый...)
0
silent_1991
10.08.2013, 17:11     Генератор простых чисел
  #20

Не по теме:

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

0
10.08.2013, 17:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.08.2013, 17:11
Привет! Вот еще темы с ответами:

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

Генератор простых арифметических примеров
Доброго времени суток. Нужно написать программу, которая генерирует примеры,...

Найти количество почти простых чисел в заданном интервале натуральных чисел.
Натуральное число называется почти простым, если оно не простое и имеет только...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

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