Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

Генератор простых чисел - 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. Нужно ввести число до которого...

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

Не по теме:

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

0
ninja2
231 / 187 / 7
Регистрация: 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
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
06.08.2013, 06:26 #8
Цитата Сообщение от 0x10 Посмотреть сообщение
Логика сегодня подвергается жестокому испытанию...
Ой перепутал 512/8 байт
0
Croessmah
Ушел
Эксперт CЭксперт С++
13553 / 7704 / 872
Регистрация: 27.09.2012
Сообщений: 19,006
Записей в блоге: 3
Завершенные тесты: 1
06.08.2013, 06:32 #9
Цитата Сообщение от ninja2 Посмотреть сообщение
Ой перепутал 512/8 байт
Ну и что? Когда-нибудь слышали про длинную арифметику?

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

Не по теме:

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

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

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

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

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

Добавлено через 15 минут
Кажись вот эту штуку я брал за основу.
1
06.08.2013, 14:56
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.08.2013, 14:56
Привет! Вот еще темы с ответами:

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

Вычислить количество простых чисел среди положительных чисел массива - C++
Дан массив целых положительных и отрицательных чисел в количестве меньше или равно 64 . А требуется , Вычислить количество простых чисел...

Дан массив целых чисел. Верно ли, что он состоит только из простых чисел? - C++
Дан массив целых чисел. Верно ли, что он состоит только из простых чисел?

Вводится последовательность целых чисел. Определить среднее арифметическое простых чисел последовательности - C++
Использовать функции в программе Задание: Вводится последовательность целых чисел. Определить среднее арифметическое простых чисел...


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

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

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