Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2 3      [все]
 Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Ещё раз рассмотрим тест Миллера-Рабина.

Из вики:
«Тест Миллера — Рабина – вероятностный полиномиальный тест простоты, позволяет эффективно определить,
является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа.
Тем не менее, тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел.»

В тесте Миллера-Рабина имеют место два условия для числа n, связанные с определением степени числа a по mod (n).
Число a определяется как случайное число из отрезка (2, n-2).
Показатели степени формируются из чисел d и r, где r берется из отрезка (1, s), а d и r определяются формулой
, где d – нечётно.

Теперь предлагается в условиях теста Миллера-Рабина уйти от использования случайных чисел
и перейти на построение эвристического алгоритма.
В тесте Миллера-Рабина имеет место две выборки:
- случайного числа из отрезка (2, n-2),
- перебор чисел из отрезка (1, s).

Эвристический алгоритм будет строиться с использованием чисел из отрезков (2, n-2) и (1, s),
которые выбираются по определённому закону.
Данный закон будет определён после анализа всех возможных вариантов степени числа a по mod (n) для небольших чисел
с последующим распространением полученного закона на все последующие числа
3 сен 19, 06:28    [21962199]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
В сообщении 21958523 были показаны первые результаты анализа всех возможных вариантов степени числа a по mod (n)
по первому условию теста Миллера-Рабина для небольших чисел.
Анализ возможных вариантов степени числа a по mod (n) по первому условию теста Миллера-Рабина был проведен
после выполнения небольшой программы 21959374.

На основании этих анализов были построены две программы, которые:
- сначала определяется простое число обычным делением на возможные множители,
а затем полученное простое число проверяется с помощью полученного эвристического алгоритма;
- сначала определяется простое число с помощью полученного эвристического алгоритма,
а затем полученное возможное простое число проверяется с помощью обычным делением на возможные множители.

Данные программы проверяли числа от 5 до 250 000 000, и результаты двух программ совпали.

Полученный алгоритм позволил определить только половину простых чисел из всего перечня простых чисел до 250 000 000,
что совпадает с 21958523.
3 сен 19, 06:55    [21962200]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Как видно из сообщения 21958523,
для половины простых чисел при применении первого условия теста Миллера-Рабина
остатки по модулю будут либо 1, либо (n – 1).

Эвристический алгоритм по первому условию теста Миллера-Рабина будет заключаться
в определении последовательности n-3 чисел Р, начиная с числа а = 2:

в которой будет только либо 1, либо (n – 1).

Для каждого числа рассматривались остатки по модулю для основания степени а, начиная с 2, и до 10 (так удобнее).
Это удовлетворяет условию теста Миллера-Рабина для выбора случайных чисел на отрезке (2, n-2).
Если исследуемое число меньше 13, то вместо 10 берётся число n-2.

Анализ результатов тестовой программы 21959374 показал, что у большинства составных чисел,
которые «прошли» тест Ферма, отличие остатков по модулю от 1 или (n – 1), начинается с а <= 5.

На диапазоне от 5 до 250 000 000 были найдено несколько составных числа, прошедшие тест Ферма,
у которых отличие остатков по модулю от 1 или (n – 1) начинается с а = 6,
а для числа 25326001 уже при а = 7 получилось такое отличие.
3 сен 19, 08:22    [21962217]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Теперь можно сформулировать эвристический алгоритм для первого условия теста Миллера-Рабина:

Пусть n – нечетное число и , где d – нечётно.
Выбирается последовательность чисел а от 2 до 10.
Для каждого числа а из этой последовательности определяются числа P на основании формулы

Если для всех чисел Р остатки по модулю равны либо 1, либо (n – 1), то число n будет простым числом.


Число 10 взято с запасом ( нет превышения 7).
Пока подтверждено только одно число 25326001 при а = 7.
Можно увеличить число 10. Но для этого нужны проверки для чисел, больших 250 000 000.
3 сен 19, 09:18    [21962235]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел.  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1755
Gennadiy Usov,

это Спарта Математика!

Забудьте, наконец, все эти эвристики.
Если утверждение строго доказано, то это теорема.
Если утверждение не доказано и не опровергнуто, то это гипотеза.
3 сен 19, 10:06    [21962264]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Aleksandr Sharahov
Gennadiy Usov,
это Спарта Математика!
Забудьте, наконец, все эти эвристики.
Если утверждение строго доказано, то это теорема.
Если утверждение не доказано и не опровергнуто, то это гипотеза.
Aleksandr Sharahov,
а как Вы не заметили математику в эвристическом алгоритме?

В алгоритме присутствует известная всем формула Миллера — Рабина!
И доказанная

У теста Миллера-Рабина свой порядок поиска чисел для этой формулы.
И у меня свой порядок поиска чисел для этой формулы, более оптимальный.

И всё...
3 сен 19, 11:00    [21962304]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Как известно, для теста Миллера-Рабина рекомендуется брать r раундов для оценки остатков по модулю, где
r = log (n)

Для очень больших чисел количество раундов будет то же большое.
В эвристическом алгоритме количество раундов 9 (пока).
Поэтому, при поиске половины простых чисел используется в несколько раз меньше количество раундов.

Таким образом,
эвристический алгоритм будет работать быстрее при поиске простых чисел,
чем первое условие теста Миллера-Рабина.


И самое главное,
эвристический алгоритм для первого условия теста Миллера –Рабина является достаточным!
3 сен 19, 11:09    [21962310]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел.  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1755
Gennadiy Usov,

Если вы добавили что-то новое к известным теоремам,
то, конечно, сможете сформулировать это новое в виде утверждения,
т.е. в виде гипотезы или теоремы.

Именно это имеет смысл обсуждать, а не "более оптимальные эвристики".
3 сен 19, 11:14    [21962315]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Немного из вики:

Гипотеза – предположение или догадка; утверждение, требующее доказательств.

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

У меня не гипотеза, у меня эвристика.

В тесте Миллера-Рабина много путей расчета первого условия,
при этом применяются раунды,
что-бы оценить результаты поиска нужных параметров для выполнения этого условия.

Я применяю эвристический алгоритм для первого условия теста Миллера-Рабина,
упрощающий поиск нужных параметров для выполнения этого условия.
3 сен 19, 11:29    [21962331]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Было рассмотрено второе условие теста Миллера-Рабина.

Для этого условия была аналогично применена программа по определению всех возможных вариантов степени числа a по mod (n)
по первому условию теста Миллера-Рабина для небольших чисел.
Здесь уже два параметра: s и a.
Был проведён анализ этих вариантов.

В результате анализа вариантов степеней была подтверждена необходимость объединения
двух условий теста Миллера-Рабина в одно условие, а именно, во второе условие для теста Миллера-Рабина.
С помощью этого условия и с помощью упрощающего поиска (эвристический алгоритм) нужных параметров
для выполнения этого условия можно будет определять большинство простых чисел (или все).

Для проведения тестовых работ применяется программа одновременного тестирования числа на наличие делителей
и на выполнение второго условия для теста Миллера-Рабина.

Если результаты по наличию составных чисел (или наличию простых чисел) совпадут,
то эвристический алгоритм для определения простых чисел можно будет строить
«на базе» второго условия для теста Миллера-Рабина.
6 сен 19, 13:14    [21965303]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Посмотрел числа Прота –

где k – нечётное положительное число.

Оказалось, что числами Прота будут все нечётные числа. Однако, почему-то не все нечётные числа были включены в числа Прота. Наверное, из-за формулы числа Прота:


Можно сделать следующую таблицу:
- все нечётные числа чередуются через 2 числа от 2^0 + 1
- все числа с (s = 1) чередуются через 4 числа от 2^1+1
- все числа с (s = 2) чередуются через 8 чисел от 2^2+1
- все числа с (s = 3) чередуются через 16 чисел от 2^3+1
- все числа с (s = 4) чередуются через 32 чисел от 2^4+1,
и т.д., пока не определяться все нечётные числа.

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

Кстати, уже ранее рассматривались числа Прота 21933488
8 сен 19, 19:16    [21966343]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Посмотрел числа Прота –

где k – нечётное положительное число.

Оказалось, что числами Прота будут все нечётные числа. Однако, почему-то не все нечётные числа были включены в числа Прота.
Надо быть внимательнее и не забыть условие k < 2s
8 сен 19, 19:42    [21966349]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Barlone
Надо быть внимательнее и не забыть условие k < 2s
Я это условие видел, и, естественно, хочу обсудить это условие.

Почему нужно это условие? Из-за формулы?

Ведь, если нет этого условия, "покрываются" все нечётные числа.
8 сен 19, 19:57    [21966354]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Просто, именно такие числа Прота "проверяет" на простоту тест Миллера-Рабина,
причем проверяет числа при любых k и n.

То есть, удобнее числа представлять в виде числа Прота.
8 сен 19, 21:05    [21966369]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
В сообщении 21966343 говорилось о том, что можно составить подмножества как нечётных чисел,
так и простых чисел, в зависимости от величины числа s 21962235.

Результат определения числа s для всех простых чисел, начиная с 3,
до некоторого числа N (ограничено временем работы ПК) показал,
что количество простых чисел с (s = 1) составляет около 50% от всех простых чисел.
Далее,
- для чисел с (s = 2) количество простых чисел составляет около 25% от всех простых чисел;
- для чисел с (s = 3) количество простых чисел составляет около 12,5% от всех простых чисел;
- для чисел с (s = 4) количество простых чисел составляет около 6,25% от всех простых чисел;
и т.д.

То есть, применение достаточного эвристического алгоритма по первому условию теста Миллера-Рабина 21962217
позволяет быть уверенными в том, что определяемые по алгоритму числа будут простыми,
и таких простых чисел будет около 50% от всех простых чисел на диапазоне
(подмножество простых чисел для s = 1).
10 сен 19, 16:53    [21967927]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Анализ проведённых вычислений показал,
что эвристический алгоритм для первого условия теста Миллера-Рабина
справедлив для всех тех чисел n, у которых s = 1 (около 50% всех простых чисел).
Позднее будет показано, что этот алгоритм справедлив и для ряда чисел, у которых s > 1.

Тогда можно немного изменить формулировку этого эвристического алгоритма
для первого условия теста Миллера-Рабина21962235.

Пусть n – нечетное число и имеется формула , где d – нечётное число.
Тогда для тех чисел n, у которых s = 1, выбирается последовательность чисел а от 2 до А.
Для каждого числа а из этой последовательности определяются числа P на основании формулы

Если для всех полученных чисел Р остатки по модулю равны либо 1, либо (n – 1),
то число n будет простым числом.


Число А выбирается равное 10, с запасом – пока подтверждено только одно число 25326001 при а = 7.
Можно увеличить число 10.
Но для этого нужны проверки для чисел, больших 250 000 000.
11 сен 19, 13:17    [21968478]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
В качестве применения эвристического алгоритма можно рассмотреть определение простых чисел Мерсенна.

Для чисел Мерсенна имеем s= 1.
Применение эвристического алгоритма для первого условия теста Миллера-Рабина
позволило определить все простые числа Мерсенна Мр (пока до р < 25000) 21958707
11 сен 19, 15:36    [21968618]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Теперь рассмотрим числа n, у которых s = 2.

Оказалось,
что для данного варианта подходит формула эвристического алгоритма для первого условия теста Миллера-Рабина (s = 1).
Таким образом, появляется единая формула эвристического алгоритма для всего теста Миллера-Рабина.


Однако, для случая, когда рассматриваются числа n, у которых s = 2, необходимо некоторое дополнение:
если среди последовательности из Р чисел (последовательность чисел а от 2 до А) нет ни одного числа (n – 1),
то необходимо повторить работу с формулой эвристического алгоритма при (s – 2).

Таким образом, эвристический алгоритм теста Миллера-Рабина для чисел n, у которых s = 2, будет выглядеть следующим образом:

Пусть n – нечетное число и имеется формула , где d – нечётно.
Тогда для чисел n, у которых s = 2, выбираем последовательность чисел а от 2 до А.
Для каждого числа а из этой последовательности определяются числа P на основании формулы

Если для всех чисел Р остатки по модулю равны либо 1, либо (n – 1), и при этом существует хоть одно из чисел Р, которое равно (n – 1),
то число n будет простым числом.
Если среди этой последовательности Р нет чисел, равных (n – 1),
то необходим ещё одно определение последовательности чисел Р для чисел а от 2 до А по следующей формуле

Если для всех чисел Р новой последовательности остатки по модулю равны либо 1, либо (n – 1),
то число n будет простым числом.


Поскольку имеется эвристический алгоритм для теста Миллера-Рабина для чисел n, у которых s = 1 или 2,
то этот алгоритм позволяет определять уже около 75% простых чисел.
11 сен 19, 19:49    [21968870]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Он ещё с ребе и Миллером не закончил.
Кажется, закончил…

И теперь можно обобщить предыдущие исследования и ответить на вопрос
о едином эвристическом алгоритме, достаточном, для определения простых чисел.

Ранее был получен эвристический алгоритм для теста Миллера-Рабина для чисел n, у которых s = 1 или 2.
Были проведены исследования о распространении этого алгоритма на любое число s.
В результате можно сказать:
получен единый достаточный эвристический алгоритм для теста Миллера-Рабина,
который определяет наличие простоты для любого целого положительного числа.


Формулировка единого эвристического, достаточного, алгоритма для теста Миллера-Рабина будет следующая:

Пусть n – нечетное число и имеется формула , где d – нечётно.
Тогда для этого числа n выбирается последовательность чисел а от 2 до А.
Для каждого числа а из этой последовательности определяются числа P на основании формулы

Если для всех чисел Р остатки по модулю равны либо 1, либо (n – 1),
и при этом, только для s > 1, существует хоть одно из чисел Р, которое равно (n – 1),
то число n будет простым числом.

Если среди этой последовательности Р для s >2 нет чисел, равных (n – 1),
то необходим цикл по s2 по определению последовательностей чисел Р для чисел а от 2 до А по следующей формуле

где s2 меняется от (s - 2) до 0.

Цикл заканчивается следующим образом:
- если для всех чисел Р новой последовательности (для s2 = 0) остатки по модулю равны либо 1, либо (n – 1),
то число n будет простым числом;
- если для всех чисел Р новой последовательности (для s2 > 0) остатки по модулю равны либо 1, либо (n – 1),
и при этом существует хоть одно из чисел Р, которое равно (n – 1),
то число n будет простым числом;
- если одно из чисел Р новой последовательности имеет остатки по модулю, не равные ни 1, ни (n – 1),
то число n будет составным.


Число А выбирается равное 10, с запасом – пока подтверждено только одно число 25326001 при а = 7.
Можно увеличить число 10. Но для этого нужны проверки для чисел, больших 250 000 000.
11 сен 19, 20:37    [21968895]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
А хде исходники на Питоне? Мы тут народ - недоверчивый.
11 сен 19, 21:10    [21968909]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
А хде исходники на Питоне? Мы тут народ - недоверчивый.
Заранее прошу меня извинить за стиль программы.

Лет 30 не программировал на серьезном языке, только на EXCEL.

Была подготовлена программа на Python, в которой решались следующие задачи:
- рассматривались все нечётные числа, начиная с 5, далее блоками по 50 000 000;
- каждое число проверялось на простоту;
- для каждого числа определялось число s;
- устанавливался предел по выбору чисел а;
- формируется цикл по s;
- определяется максимальное число max_a2_1, когда находится число, отличное от 1 или (n – 1);
- определяется максимальное число количества раудов по s - max_a2_2;
- найденное простое число проверяется на делимость;
- отвергнутое число проверяется на делимость;
- поскольку много простых чисел, то печатается только их количество на очередном диапазоне чисел со всеми оценочными числами;
- в конце печатается количество найденных простых чисел;
- печатаются все случаи, если они встретятся, когда программа, либо пропускает простые числа, либо определяет составные числа как простые.

По отдельным случаям s программа «доходила» до 250 000 000.
По всем s программа пока дошла до 68 200 187. Найдено 1 017 273 простых числа.

import math											
def delit_vse(p):											
	b1 = 0											
	b = p % 2											
	if b > 0:											
		j =3											
		q = math.sqrt(p)//1								
		while j <= q:									
			b = p % j									
			if b == 0:									
				b1 = j									
				j = q+1								
				#print (j1)								
			j +=2										
	else:												
		b1= 2											
	return b1											
q = 0													
max_a2_1 = 0											
max_a2_2 = 0											
													
nhp = 0												
nhp1 = 0												
proct_col = 0											
p =   5												
P = p + 50000000											
while p <=P:											
	#print (p)											
	num = delit_vse(p)									
													
	t = p - 1											
	s = 0												
	while (t % 2 == 0):										
		t //= 2;										
		s += 1;										
	t1 = t//1											
	#y = math.log( p )//1									
	#print (t,s)											
	col_raund = 0										
	a2 = 10	# p-2										
	if a2  > p-2:											
		a2 = p-2										
	s2 = s-1											
	hp = 0											
	while hp == 0:										
		nhp1 += 1										
		hp = 0										
		col1 = 0										
		a1 = 2										
		while a1 <= a2:									
			#print (a1, t1, p)								
			t2 = (2**s2)*t1								
			x = pow(a1, t2, p)								
			#print (x, a1, p)								
			if x == 1 or x == p-1 :							
				col1 += 1								
				if x == p-1 :								
					hp = 1							
			else:										
				if max_a2_1 <  a1 :						
					max_a2_1 = a1						
				a1 = a2								
				hp = 1								
			a1 +=1									
													
													
		s2 = s2 - 1										
		col_raund  += 1									
		if s2 <  0 :										
			hp = 1									
													
	if max_a2_2 < col_raund :								
		max_a2_2 = col_raund 								
													
	#print (p, col1, a2)									
	if col1 == a2 - 1:										
		if num > 0:										
			print ("-not-a-", p, proct_col, a2, col1, num)			
		else:											
			#print ("-blok-a-",p, "-s-", s)		# очередное простое число
			proct_col += 1								
	else:												
		if num == 0:										
			print ("-not-obr-", p, proct_col, num)				
	p +=2												
	q +=1												
	if q > 100000:										
		print ("-perep-",p,proct_col, nhp1, nhp, max_a2_1, max_a2_2 )	
# количество простых на диапазоне
		q = 0											
print ("-N blok-", proct_col)									
12 сен 19, 06:35    [21969065]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Можно существенно убыстрить работу программы 21969065.

Для этого вводятся дополнительно два цикла:
1. Предварительная проверка числа на делимость, например, до 180 (с учётом корня из числа).
2. Применение теста Ферма к числу.

После этого проверка числа на делимость проводится уже с тех 181(с учётом корня из числа).

Здесь нужно проводить исследования при выборе этого числа 180:
до какого делителя числа лучше применять сначала делители, а уже потом тест Ферма.
12 сен 19, 09:03    [21969105]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Gennadiy Usov
Ошибся.

Вместо
После этого проверка числа на делимость проводится уже с тех 181(с учётом корня из числа).

Нужно
После этого проверка числа на делимость (с учётом корня из числа).
12 сен 19, 09:22    [21969119]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
У меня - другое число.
./pbfa64 250000000 -ns | wc -l
.....
Completed: 97 %
Completed: 98 %
Completed: 99 %

Primes detected      : 13679318
Twin primes          : 991445
Triplet primes       : 236934
Range                : [2..250000000]
Memory cache used    : 131072 K
Square root algorithm: Henry Warren's 'isqrt64'
AVG speed generation : 28738 units/sec
Elapsed time         : 476 sec
12 сен 19, 09:29    [21969123]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
У меня - другое число.
Верно.

Забыл приплюсовать 2989855 из другого блока по 50 000 000.
12 сен 19, 09:33    [21969124]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Говоришь загадками. Какой блок? Сколько у тебя получилось?
12 сен 19, 09:36    [21969127]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Говоришь загадками. Какой блок? Сколько у тебя получилось?
Мне удобно работать блоками по 50 000 000 чисел. Это видно по программе. Следующий блок от 50 000 005 и ещё 50 000 000 чисел. И т.д.

В первом блоке определилось 3 001 132 простых чисел.
От 50 000 005 (начало второго блока) до 68 200 187 найдено 1 017 273 простых числа.

Итого на диапазоне от 5 до 68 200 187 было найдено 4 018 405 простых чисел.
12 сен 19, 13:24    [21969405]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Primes detected      : 4018407
Twin primes          : 314068
Triplet primes       : 80895
Range                : [2..68200187]
Memory cache used    : 32768 K
Square root algorithm: Henry Warren's 'isqrt64'
AVG speed generation : 52187 units/sec
Elapsed time         : 77 sec

Итого 4018407 минус 2 числа (2 и 3) получается 4 018 405

Теперь поговорим об оптимизациях. Вырожденный Миллер Рабин превращается в метод грубой силы?

Или нет?
12 сен 19, 15:20    [21969571]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Теперь поговорим об оптимизациях.
Вырожденный Миллер Рабин превращается в метод грубой силы?
Или нет?
Тест Миллера-Рабина (сами формулы) остаётся в силе.

Просто меняется последовательность поиска параметров для формул теста Миллера-Рабина.

В эвристическом алгоритме:
Для 50 % чисел достаточно для проверки только 9 раундов (автоматически - может быть меньше) расчета по формулам теста Миллера-Рабина.
Для других 25 % чисел достаточно для проверки только 9 раундов (автоматически - может быть меньше) расчета по формулам теста Миллера-Рабина, а также иногда имеет место 2-й этап (автоматически) - ещё 9 раундов (автоматически - может быть меньше) .
И т.д.

По тесту Миллера-Рабина:
количество раундов равно log( p ).
И считать по двум формулам,
И то - то ли простое число, то ли нет.

Разница есть?

Это для начала оптимизации...
12 сен 19, 15:38    [21969586]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Ещё одно наблюдение при тестировании программы.

Предварительное определение множителей чисел (метод грубой силы до определённого множителя)
позволяет уменьшить количество применяемых циклов для величины s2 21968895,
что помогает уменьшить среднее время при определении простоты для каждого из этих чисел.
12 сен 19, 21:07    [21969892]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Решил проверить программу на числах 2^1024.

Для этого поменял немного заставку программы - смотрел 5000 чисел после 2^1024:
Q = 2**(1024)								
p1 =   5								
P1 = p1 + 5000								
while p1 <=P1:								
	p = Q + p1							
	num =  delit_vse_pre(p, 160)	# проверка на множители до 160						
								
	if num == 0:							
		x =   pow(2,p-1, p)		# тест Ферма				
		if x == 1:						
			print (Q -p)


Получилось:
+
2019-09-13-06.04.01
-643
-blok-a- 643 -s- 1
-1081
-blok-a- 1081 -s- 3
-2113
-blok-a- 2113 -s- 6
-2715
-blok-a- 2715 -s- 1
-3711
-blok-a- 3711 -s- 1
-N blok- 5

2019-09-13-06.04.09
13 сен 19, 06:12    [21969978]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Так что, критика и обсуждения закончились?

А как же дежурные фразы, mayton 21908442?
13 сен 19, 16:41    [21970552]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Сколько времени он у тебя работал?
13 сен 19, 17:15    [21970591]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Сколько времени он у тебя работал?
Эвристический алгоритм для формул теста Миллера-Рабина окончательно "сформировался" дня три назад.

До этого были пробные тесты для s = 1, для s = 2, для s = 3.
После этого был пробный тест для всех s.

Поскольку ПК - старенький, то прогон проводился для отдельных s до 250 000 00, а для всех s - до 68 000 000.
Стараюсь запускать программу тогда, когда нахожусь рядом.

Поскольку для небольших n всё проходит, то наступает "эвристика". Можно распространять на большие числа.

В частности, был прогон для чисел около 2^1024.
13 сен 19, 17:47    [21970615]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Надо оценить асимптоматику.
Не вычислить. А именно оценить.
Для этого надо сделать штук 5 запусков
С линейно меняющимся параметром
И засечь с точностью до секунд время.
После этого посмотреть в Экселе график
И прикинуть что это. Полином? Экспонента? Etc.
13 сен 19, 19:00    [21970664]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Надо оценить асимптоматику.
Не вычислить. А именно оценить.
Для этого надо сделать штук 5 запусков
С линейно меняющимся параметром
И засечь с точностью до секунд время.
После этого посмотреть в Экселе график
И прикинуть что это. Полином? Экспонента? Etc.
Ваши предложения по диапазонам?

Нужно ли предварительное деление?

Нужен ли предварительный тест Ферма?
13 сен 19, 19:02    [21970667]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Выше ты делил по 50 лимонов.

Вот пускай так и будет.

По Ферма не понял. Мы ведь один алгоритм обсуждаем? Или несколько?
13 сен 19, 20:03    [21970714]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Основные параметры эвристического алгоритма:
- число значений s2;
- число раундов при одном s2, после которого узнаём, что число составное ( остаток не равен ни 1, ни (n - 1))
- число значений s2, после которых определяется простое число.

По каждому значению можно определить мax или min на некотором интервале чисел (у меня либо 200000, либо 1000000).
13 сен 19, 20:05    [21970716]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Выше ты делил по 50 лимонов.
Вот пускай так и будет.
По Ферма не понял. Мы ведь один алгоритм обсуждаем? Или несколько?
Ферма по любому быстрее определяет множество чисел, среди которых все простые числа.

Ведь тест Ферма - это один раунд.
Тест Миллера-Рабина - это несколько раундов.
Причём, это по всем числам: и составным, и простым.

Мне видится следующий подход: тест Ферма ограничивает количество чисел, среди которых все простые числа,
а тест Миллера-Рабина (с эвристическим алгоритмом или с другим алгоритмом) "зачищает" полученные числа,
выбирая из них только простые числа.

Это моё видение процесса поиска простых чисел,
при этом ещё в начале процесса поиска - деление на небольшие множители.

Можно рассмотреть вопрос применения одного эвристического алгоритма для формул теста Миллера-Рабина,
и сравнить результат применения алгоритма с результатами теста Ферма.
13 сен 19, 20:17    [21970721]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Сейчас у меня заканчилась работа программы для второго диапазона: от 50 000 005 до 100 000 005.
На этом диапазоне получено 2760321 простых чисел.
Программа не ошиблась - среди полученных простых чисел нет составных чисел.

Вначале программы идёт проверка на множители до 643 (так решил),
далее тест Ферма,
далее алгоритм.

И даже в таком виде диапазон из 1 000 000 чисел рядом с числом 100 000 000 программа "проходит" за 3 минуты.

Применение множителей и Ферма, как я уже говорил ранее,
позволило уменьшить количество изменений значений s2 для одного числа до 4 (ранее были случаи 7 ).

Основное значение количества раундов (а1) при одном значении s2,
когда выявляется составное число, в основном - значение 3,
но есть случаи, когда встречается значение 5, очень редко 7.
(обращаю внимание - значения нечётные)
13 сен 19, 20:31    [21970727]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Вот ты мастак все усложнять.

Я хотел посмотреть имеет ли смысл изучать твой Питонский исходник. И хотел посмотреть его отклик.

Знаешь как в радиоэлектронике. Подали входной сигнал. Встали осцилографом на выход. Посмотрели.
Поменяли сигнал и т д.
13 сен 19, 20:36    [21970730]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Убрал все добавления, оставил один эвристический алгоритм.

Программа считает.
На 2 000 000 чисел 148932 простых.
Время работы 1,5 минуты.
Программа продолжает работу...
13 сен 19, 21:02    [21970735]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Нужно хотя-бы 5 точек на плоскости чтоб мы построили график зависимости времени от параметра алгоритма.
13 сен 19, 22:32    [21970755]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Геннадий? Куда-то пропал. Или построение 5 измерений так долго?
14 сен 19, 14:05    [21970891]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Геннадий? Куда-то пропал. Или построение 5 измерений так долго?
Не пропал.

Продолжаю считать. Уже прошёл (с остановками) число 153 000 000.
Есть интересное число 133800661, разбирался с ним.
14 сен 19, 14:14    [21970899]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Так долго? Ладно побей на интервалы поменьше.
14 сен 19, 15:37    [21970927]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Так долго? Ладно побей на интервалы поменьше.
В начале на диапазон в 1 000 000 чисел уходило 1,5 минуты.
На отметке 175 000 000 уходит уже 2,5 минуты
14 сен 19, 15:43    [21970930]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Ну дык... цифры есть? 4-5 штук.
14 сен 19, 15:45    [21970931]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Ну дык... цифры есть? 4-5 штук.
Сейчас основные цифры, которые печатаются после мини диапазона (1 000 000), это:
- на каком раунде (а1) выявляется составное число (максимальное по мини диапазону);
- сколько может быть значений s2 (максимум на мини диапазоне) - дополнительные 9 раундов на каждое значение.

На текущий момент max a1 - очень редко 7, один раз - 11,
а для s2 - почти всегда 4.
14 сен 19, 16:14    [21970943]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Прошел 250 000 000.

В конце этого диапазона время обработки мини диапазона увеличилась до 3 мин. 09 сек.

На текущий момент max a1 - очень редко 7,
а для s2 - почти всегда 4, редко 5,6, один раз 8.
14 сен 19, 19:29    [21970980]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Кто из вас на хабр пишет вот это?
https://habr.com/ru/post/466887/
https://habr.com/ru/post/467203/
https://habr.com/ru/post/467463/
вчера, 06:42    [21971061]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Barlone
Кто из вас на хабр пишет вот это?
https://habr.com/ru/post/466887/
https://habr.com/ru/post/467203/
https://habr.com/ru/post/467463/
Это хорошо или это плохо?

Но не я.

Хотя было бы в дальнейшем интересно прочитать.
Уж очень много лирики!
вчера, 06:57    [21971062]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Почему кто-то из нас?
вчера, 08:57    [21971078]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Почему кто-то из нас?
Теперь на нас всё будут списывать.

Как в том анекдоте: чуть что, так ....
вчера, 09:50    [21971083]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1755
это не мы, там нет слова "'эвристический"
вчера, 09:51    [21971084]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Наш вклад в теорию чисел пока слишком ничтожен.
вчера, 12:49    [21971117]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1287
mayton
Почему кто-то из нас?
Много общего с этой с соседними темами.
А лирики и правда много. И не очень строго математически.
вчера, 14:57    [21971166]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Прошел 350 000 000.

В конце этого диапазона время обработки мини диапазона увеличилась до 3 мин. 42 сек.

На текущий момент max a1 - очень редко 7,
а для s2 - почти всегда 4, редко 5.[/quot]
вчера, 15:19    [21971177]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1674
Озвучьте уже, плз, для постороннего.
Обсуждаемый предмет, имеет строгое доказательство? Например сокращение вычислений лишь предполагается или свершившийся факт?
Обсуждаемые алгоритмы сравниваются на одинаковом диапазоне?
Статус достоверности/правдоподобности алгоритмов одинаков? чей статус весомее?
Насколько значим этот диапазон?
вчера, 19:05    [21971237]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
exp98
Озвучьте уже, плз, для постороннего.
Обсуждаемый предмет, имеет строгое доказательство?
Например сокращение вычислений лишь предполагается или свершившийся факт?
Обсуждаемые алгоритмы сравниваются на одинаковом диапазоне?
Статус достоверности/правдоподобности алгоритмов одинаков? чей статус весомее?
Насколько значим этот диапазон?
1. Насчет доказательства: (из вики)
"Эвристический алгоритм (эвристика) — алгоритм решения задачи, включающий практический метод, не являющийся гарантированно точным или оптимальным, но достаточный для решения поставленной задачи."

2. Эвристический алгоритм предполагает уменьшение количества вычислений.

3. Эвристический алгоритм проверяется, начиная с 1, с помощью делителей.
Диапазоны появились, так как программа считает долго.
Поэтому проверка идёт диапазонами.

4. "Статус достоверности/правдоподобности алгоритмов одинаков? чей статус весомее?" - это о чём? Алгоритм один.
вчера, 19:21    [21971238]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Прошел 400 000 000.

В конце этого диапазона время обработки мини диапазона увеличилась до 4 мин. 53 сек.

На текущий момент max a1 - очень редко 7,
а для s2 - почти всегда 4, редко 5, 6.
вчера, 19:24    [21971240]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Ты попутно веди учот количеству найденных простых. Если где-то проскочит ложное значени
то мы сможем сравнить с PBFA и найти его.
вчера, 19:33    [21971243]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1674
Gennadiy Usov,
и никаких упоминаний родительского алгоритма? т.е. новый сам по себе, и ни с чем не сравнивается?

поставленной задачи - и какова она, постановка?

Вы и в суде тоже будуте на свистипедию сыслаться? гаишнику тоже на неё пенять?
вчера, 19:47    [21971248]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1674
Gennadiy Usov
Диапазоны появились, так как программа считает долго.
Поэтому проверка идёт диапазонами.
попробую другими словами: Различаются ли множества чисел, пригодных к тестированию, для сравниваемых алгоритмов? (я не спрашиваю про процент прохождения теста)

4. "Статус достоверности/правдоподобности алгоритмов одинаков? чей статус весомее?" - это о чём? Алгоритм один.
Это об онтологическом статусе вашего и "сравниваемого(мых)" алгоритма.
вчера, 19:55    [21971250]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
exp98
Gennadiy Usov
Диапазоны появились, так как программа считает долго.
Поэтому проверка идёт диапазонами.
попробую другими словами: Различаются ли множества чисел, пригодных к тестированию, для сравниваемых алгоритмов? (я не спрашиваю про процент прохождения теста)

4. "Статус достоверности/правдоподобности алгоритмов одинаков? чей статус весомее?" - это о чём? Алгоритм один.
Это об онтологическом статусе вашего и "сравниваемого(мых)" алгоритма.
Алгоритм проверяется на всех нечётных числах, начиная с 1.

Каждое нечётное число проверяется на делители и на эвристический алгоритм.
Пока нет случаев, когда число, прошедшее алгоритм, имело делители.
Пока нет случая, когда число, имеющее делителей, прошло алгоритм.

Существующие алгоритмы - вероятностные, у меня - эвристический алгоритм, без использования вероятности.
вчера, 20:10    [21971251]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1674
Вам надо скорее патентовать его в просчитанном диапазоне.
А то ведь на хабру глянет пара вдумчивых глаз, придёт сюда, и скажет: "Ага!" И бабла у неё будет больше, и возможностей, и выч-х мощностей.
Патентовать - подольше будет, чем считать до ярда, а вот статейку тиснуть можно быстрее.
Так что, не упускай из виду.
вчера, 21:00    [21971263]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1755
Gennadiy Usov
Пока нет случаев, когда число, прошедшее алгоритм, имело делители.
Пока нет случая, когда число, имеющее делителей, прошло алгоритм.


Осталось понять, были ли случаи,
когда число, прошедшее алгоритм, не имело делителей,
когда число, имеющее делителей, не прошло алгоритм,
когда число, не прошедшее алгоритм, имело делителей,
когда число, не имеющее делителей, прошло алгоритм,
когда число, не прошедшее алгоритм, не имело делителей,
когда число, не имеющее делителей, не прошло алгоритм.
вчера, 21:27    [21971266]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3      [все]
Все форумы / Программирование Ответить