1 | ||||||||||||||||
Быстрая проверка натурального числа на простоту29.09.2012, 21:35. Показов 139287. Ответов 121
Метки нет (Все метки)
Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь рассматриваются только детерминированные алгоритмы, дающие 100% ответ на вопрос о простоте.
Хорошо известно такое утверждение: если натуральное число n>1 не делится ни на одно простое число, не превосходящее , то оно простое. В связи с этим получается самый простой способ проверки на простоту алгоритм
33
|
29.09.2012, 21:35 | |
Ответы с готовыми решениями:
121
Проверка на простоту числа Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту |
05.10.2012, 14:41 [ТС] | 21 | |||||
Хотел применить теорию, которая помогла написать более быстрый алгоритм для проверки на простоту, к построению решета Эратосфена. Но ни тут то было, самая быстрая реализация имеет такой вид
0
|
07.10.2012, 11:14 [ТС] | 22 | ||||||||||
Решето Эратосфена в таком варианте
Добавлено через 1 час 56 минут С подачи от valeriikozlov более быстрый алгоритм:
1
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
28.10.2012, 22:47 | 23 |
не знаю на сколько актуально, но этот оптимизированный алгоритм можно загнать на GPU =) с лишь откидыванием четных чисел я получил скорость в проверки 10млрд делителей/ секунду. Число порядка 10^19 в худшем случае проверяет около 100-120ms.
Добавлено через 11 минут Thinker, а ты еще что нить придумал ? вот конкретный тест: digit 2305843009213693951 is simp 0 time 150.121 ms
0
|
29.10.2012, 09:07 [ТС] | 24 |
Не по теме: судя по всему, мои алгоритмы очень медленны для очень больших чисел. Вот в этой теме
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
29.10.2012, 23:25 | 25 |
Thinker, я так понял алгоритм никто не написал на с++? Просто тот же перебор можно оптимизировать для видеокарты и он будет работать с бешеной скоростью ю, пока достиг проверки 15млрд делителей/сек
Добавлено через 12 часов 1 минуту Thinker, я придумал как ускорить этот алгоритм, произведя заранее подготовку, то есть имея какие то данные в виде таблицы в файле например, которые можно просчитать 1 раз и сохранить. В общем как ты писал, если исключить из проверки все четные числа и каждое 3е, то получим, что надо проверить всего 33% делителей. Я решил проверить на сколько уменьшится этот процент, если к примеру мы исключим по больше числе. В итоге получил такой расчет: при исключении всех простых чисел до 10 000 (а их 1228) получаем, что на больших числах нам надо проверить около 6,6% оставшихся, то есть можно ускорить в 5 раз! (теоритически). А период повторения этих чисел - их произведение = 808157282. То есть нужно получить все оставшиеся числа в промежутке от k (где k - первое число, которое не делится по модулю на 1228 простых) до k + 808157282. Судя по расчетам их около 53 млн - при размере u_int64 = 8 байт это занимает порядка 420 мб. Остается только получить эти числа =) ну или посчитать на сколько можно уменьшить данное количество.
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,520
|
|
29.10.2012, 23:38 | 26 |
Я не помню предлагал или нет
предварительно рассчитываем простые числа до 2^32 и записываем их в файл это 16 гигабайт интов на самом деле меньше мы же не все туда будем записывать а только простые можно создать файл для чисел 2^16 это 260 кБ (важна идея) а потом при расчете если число попадает в диапазон берем из таблицы(из файла) а если больше, то делим на делители из файла( т.е) делим только на простые числа этим мы выбрасываем и кратные 2 и кратные 3 5, 7, 11 ....... скорость должна возрасти, хотя не просчитывал не знаю основная работа ляжет на создание файла ( но это один раз)
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
30.10.2012, 09:10 | 27 |
ValeryS, а что, если у нас число например порядка 10^19 = 2^19 * 5^19 и кончатся делители из файла?_)
0
|
30.10.2012, 09:35 [ТС] | 28 |
AEXks, я уже ходил этим путем, прочитайте пост 16 этой темы. прироста в скорости нет. прирост в скорости начинается, если числа ОЧЕНЬ большие
При этом я рассматривал очень большие значения m, а чем ближе m к корню из тестируемого числа, тем больше убирается составных тестируемых чисел. например, если , то остаются только простые тестируемые числа в роли потенциальных делителей. но реализация этого всего не позволяет добиться быстрой скорости, поэтому индийские ученые (AKS) пошли другим путем. Дело же в чем. Мы же все равно фиксирует этот модуль m, а тестируемые числа могут быть сколь угодно большими, так и так возникнет процент лишних проверок с использованием составных делителей. да и реализовать это эффективно с массивами не удается. ValeryS, такой алгоритм подойдет только для чисел из фиксированного диапазона, но не для произвольного числа.
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,520
|
|
30.10.2012, 10:34 | 29 |
это меньше чем 2^64 ???
при использовании таблицы простых чисел до 2^32 можно проверять числа до 2^64 если этого мало то можно создать большую таблицу вообще мне трудно решать,поскольку не могу представить прикладную задачу для применения таких больших простых чисел
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
30.10.2012, 10:59 | 30 |
ValeryS, окей , задача состоит в взломе ключа RSA , длина которого как минимум 1000бит , так что тут даже не обойтись простой арифметикой, а вообще это все нужно для криптографии в том числе.
Thinker, Вы исходите из производительности одного ядра процессора, но на видеокарте это будет выглядеть по другому. Надо думать в этом направлении. И чем больше мы исключаем чисел, тем фактически большее количество делителей можно проверить за секунду. Пока, исключив только 2 и 3 я смог добиться проверки 16,6 млрд делителей в секунду. то есть 1,6 * 1010 / сек. Теперь по теоретическом расчету для проверки 232 делителей уйдет 232 / 1,6 * 1010 = 0,26 секунд. ( Что на практике так и есть, так как в 64 битное число можно как раз записать 20ти значные числа.) ValeryS, То есть по рассуждениям выше не нужно ничего городить) числа 264 проверяются в худшем случае за 260ms , и в принципе можно считать , что для таких числе задача решена.
0
|
30.10.2012, 20:58 [ТС] | 31 |
AEXks, если зафиксировать модуль m, то в этом случае сложность алгоритма будет , где n - исследуемое число. Поэтому есть ли смысл идти в этом направлении. Вы же прекрасно понимаете, что в ассимметричных шифрах используются ОЧЕНЬ большие числа, а если речь об эллиптических кривых, то там совсем принцип другой. Изначально моя цель была, действительно, улучшить широко используемый алгоритм проверки на простоту, но при общих равных условиях (при активном одном ядре), третий алгоритм из первого поста получился самым удачным. Другие алгоритмы, которые я здесь не выкладывал, уступают относительно (условной) сложности реализации и скорости. Да, при больших числах скорость медленно начинает расти относительного третьего алгоритма, но сложность остается , поэтому я эту затею бросил.
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
30.10.2012, 21:01 | 32 |
Thinker, а есть ли другие точные алгоритмы при меньшей сложности? так как скорость просчета на _int64 быстр, то нужно как то попробовать реализовать деление по модулю двух _int64 , _int64 на максимум _int64 . Я уже написал мысли по этому поводу.. там нужны битовые операции, а именно я не знаю есть ли функции вычисляющие номер самого старшего значимого бита.
0
|
30.10.2012, 21:08 [ТС] | 33 |
Тот же AKS, но им не интересовался. Мне интересно было применить некоторые познания из теории чисел на практике и, отчасти, это сделать удалось. Ваша идея с GPU очень интересна, но не понятно как Вы это реализовали.
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
30.10.2012, 21:25 | 34 |
Thinker, в каком плане не понятно ? могу выложить код функции обработчика и ядра =) обсудим
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
||||||
30.10.2012, 21:38 | 36 | |||||
Тут все просто: так как мы выкинули 2ки и 3ки то зачем нам их проверять? из-за этого получается две последовательности чисел, которую мы и задаем. на GPU мы имеем много нитей, которые выполняют "свой" код. По этому мы берем и выполняем параллельно проверку сразу нескольких делителей. Этот код заточен на проверку сразу массива чисел, но я тут проверял всегда одно =)
0
|
30.10.2012, 21:50 [ТС] | 37 | ||||||||||||||||||||||||||||||
Занятно) Ну, можно некоторые моменты переделать. вместо
может Вам попробовать третий алгоритм так переделать?
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
|
30.10.2012, 21:53 | 38 |
это какой именно? я чет прочитав все что тут было написано так и не понял чем они особо отличаются?
0
|
30.10.2012, 21:56 [ТС] | 39 |
скоростью отличаются. третий алгоритм из поста 1, как минимум, в два раза быстрее чем первый алгоритм. Но это для чисел из диапазона от 2 до 10^8. А при росте чисел прирост скорости будет существенно расти.
0
|
24 / 3 / 0
Регистрация: 28.10.2012
Сообщений: 35
|
||||||||||||||||||||||||||||||||||||||||||||||
30.10.2012, 22:14 | 40 | |||||||||||||||||||||||||||||||||||||||||||||
Thinker, а ну да, вы собственно и воспользовались тем, что период последовательности числе будет равен произведению выкинутых. Я написал тестовую прогу для вычисления всего этого и вот что у меня вышло:
0
|
30.10.2012, 22:14 | |
30.10.2012, 22:14 | |
Помогаю со студенческими работами здесь
40
Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту (нужны комментарии) Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |