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

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

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

В тесте Миллера-Рабина имеют место два условия для числа 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, 12:20
3 сен 19, 06:28    [21962199]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
В сообщении 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

Откуда:
Сообщений: 1842
Как видно из сообщения 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

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

Пусть 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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где 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

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

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

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

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

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

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

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

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

Откуда:
Сообщений: 1842
В сообщении 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

Откуда:
Сообщений: 1842
Анализ проведённых вычислений показал,
что эвристический алгоритм для первого условия теста Миллера-Рабина
справедлив для всех тех чисел 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

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

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

Откуда:
Сообщений: 1842
Теперь рассмотрим числа 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

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

Откуда:
Сообщений: 1842
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

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

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

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

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

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

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

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

Откуда: loopback
Сообщений: 42946
У меня - другое число.
./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

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

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

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

Откуда:
Сообщений: 1842
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
Сообщений: 42946
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

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

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

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

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

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

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

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

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

Откуда:
Сообщений: 1842
Решил проверить программу на числах 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Откуда:
Сообщений: 1842
Сейчас у меня заканчилась работа программы для второго диапазона: от 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
Сообщений: 42946
Вот ты мастак все усложнять.

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

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

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

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

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

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

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

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

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

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

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

Откуда:
Сообщений: 1842
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

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

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

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

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

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

Но не я.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Откуда:
Сообщений: 1842
Замечено, что время расчета на мини диапазоне может меняться среднее время.

Например, вечером, при завершении диапазона 400 000 000 время работы на мини диапазоне было около 4 мин. 53 сек.

2019-09-15-18.46.09
-perep- 397000099 2381160 23578929 0 5 4
2019-09-15-18.50.58
-perep- 398000101 2431740 24080651 0 2 4
2019-09-15-18.55.52
-perep- 399000103 2482096 24582290 0 3 4
2019-09-15-19.00.45

Сейчас утро, обрабатывается следующий диапазон, и на мини диапазоне время работы уже 3 мин 50 сек.

2019-09-16-06.46.29
-perep- 402000009 100834 1003457 0 3 4
2019-09-16-06.50.16
-perep- 403000011 151317 1505094 0 2 4
2019-09-16-06.54.03
-perep- 404000013 201794 2006786 0 3 4
2019-09-16-06.57.50

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

Откуда:
Сообщений: 1848
Винда чем-либо занята, диск фрагментирован, какое-нить свопирование на диск не постоянно ... (анти)вирус ...
16 сен 19, 17:22    [21971844]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
exp98,

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

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

019-09-16-17.38.35
-perep- 496000097 2303201 23076481 0 3 4
2019-09-16-17.44.39
-perep- 497000099 2353085 23578171 0 3 4
2019-09-16-17.50.43
-perep- 498000101 2403048 24079773 0 3 4
2019-09-16-17.57.19
-perep- 499000103 2452945 24581438 0 5 4
2019-09-16-18.03.52

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

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

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

2019-09-18-15.20.45
-perep- 748000101 2352519 24078107 0 3 4
2019-09-18-15.25.43
-perep- 749000103 2401212 24579746 0 3 3
2019-09-18-15.30.49
-N blok- 2450249 3 4


В конце этого диапазона время обработки мини диапазона составляет 5 мин. 06 сек.

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

Откуда: loopback
Сообщений: 42946
Ну дык. График хде? Хде график-та?
18 сен 19, 17:12    [21973440]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Ну дык. График хде? Хде график-та?
График чего от чего?

Программа выдаёт основные параметры алгоритма по мини диапазонам:
время работы мини диапазона
величина а1
величина s2
количество простых чисел
18 сен 19, 18:06    [21973498]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
mayton, это называется: "Я под вашу дудку не пляшу."
18 сен 19, 18:51    [21973540]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Я чуть позже построю тот-же график для своего pbfa. Ожидаю что там будет полином.
18 сен 19, 18:55    [21973544]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Нашел время понять, что такое - асимптоматика.

Но здесь трудно оценить процесс вычисления, поскольку используются процедуры Питона.

Если рассматривать результаты вычислений по времени, то они очень отличаются:
утром ПК считает быстро, а вечером медленнее.

Если в среднем, то для мини диапазона на 500 000 нечётных чисел на проверку уходит 4 - 5 минут уже довольно давно.

А в этом диапазоне числа, разные с точки зрения параметра s.
У 50% s = 1, у 25% s = 2 и т.д.
18 сен 19, 19:58    [21973602]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
У меня было 15 диапазонов по 50 000 000.
Я взял в каждом диапазоне 1-й мини диапазон по 1 000 000 и посмотрел на время его выполнения.

Получилось (мин.сек.):
0.21, 1.36, 2.24, 2.34, 2.56, 3.11, 3.58, 3.53, 3.46, 5.41, 4.10, 4.27, 4.46, 4.42, 5.34
18 сен 19, 20:18    [21973616]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
В предыдущем сообщении асимптоматика эвристического алгоритма считается с учётом проверки чисел на делители.
Это ошибочно.

Поэтому для асимптоматики были проведены расчёты эвристического алгоритма без учёта проверки на делители.

В результате:
на диапазоне от 5 до 50 000 000 время проверки мини диапазона из 1 000 000 чисел составляет 9 сек.

на диапазоне от 350 000 000 до 400 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 12 сек.

на диапазоне от 700 000 000 до 750 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 13 сек.

на диапазоне от 1 500 000 000 до 1 550 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 13 сек.

на диапазоне от 2^200 +1 до 2^200 +1 + 50 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 2 мин. 06 сек. (найдено на мини диапазоне 7134 простых числа)

на диапазоне от 2^500 +1 до 2^500 +1 + 400 000 время проверки мини диапазона
уже из 200 000 чисел составляет 3 мин. 21 сек. (найдено на мини диапазоне 576 простых числа)

на диапазоне от 2^1024 +1 до 2^1024 +1 + 400 000 время проверки мини диапазона
уже из 200 000 чисел составляет 21 мин. 59 сек. (найдено на мини диапазоне 281 простое число)
19 сен 19, 07:20    [21973799]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
автор
В результате:
на диапазоне от 5 до 50 000 000 время проверки мини диапазона из 1 000 000 чисел составляет 9 сек.

на диапазоне от 350 000 000 до 400 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 12 сек.

на диапазоне от 700 000 000 до 750 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 13 сек.

на диапазоне от 1 500 000 000 до 1 550 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 13 сек.

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

Откуда: loopback
Сообщений: 42946
на диапазоне от 2^200 +1 до 2^200 +1 + 50 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 2 мин. 06 сек. (найдено на мини диапазоне 7134 простых числа)

на диапазоне от 2^500 +1 до 2^500 +1 + 400 000 время проверки мини диапазона
уже из 200 000 чисел составляет 3 мин. 21 сек. (найдено на мини диапазоне 576 простых числа)

на диапазоне от 2^1024 +1 до 2^1024 +1 + 400 000 время проверки мини диапазона
уже из 200 000 чисел составляет 21 мин. 59 сек. (найдено на мини диапазоне 281 простое число)

На этих диапазонах я могу сверить с BigInteger::isProbablePrime и полученое тобой значение
должно быть порядка моего. Если найдем различия - можно будет говорить что либо
у тебя ошибка. Либо мы нашли ложно-позитивное срабатываение isProbablePrime.
19 сен 19, 09:16    [21973865]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
exp98
Вам надо скорее патентовать его в просчитанном диапазоне.
А то ведь на хабру глянет пара вдумчивых глаз, придёт сюда, и скажет: "Ага!" И бабла у неё будет больше, и возможностей, и выч-х мощностей.
Патентовать - подольше будет, чем считать до ярда, а вот статейку тиснуть можно быстрее.
Так что, не упускай из виду.
http://sci-article.ru/articles_current.php

Кажется, получилось "тиснуть" статью в журнал.
19 сен 19, 09:37    [21973888]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Gennadiy Usov, рано еще писать статьи. Надо баги поискать.
19 сен 19, 10:09    [21973927]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Gennadiy Usov, рано еще писать статьи. Надо баги поискать.
В статье описан эвристический алгоритм.
Программа не рассматривается, есть только ссылка на неё.

В статье указаны некоторые исходные данные для программы, но они указаны для чисел до 700 000 000.
Если в программе для больших чисел что-то изменится,
то поменяются исходные данные, но уже в новой возможной публикации.
19 сен 19, 10:18    [21973932]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Давно бы так. А то прикидывался шлангом, дескать, писать не умею и не знаю как.
Вопрос от дилетанта. Последнее предложение
автор
В большинстве случаев на отрезке (1, 750 000 000) простое число находится через 15 раундов.
число 15 точно не опечатка? будь я в редакции, попросил бы гистограмму распределения кол-ва раундов.
19 сен 19, 12:50    [21974130]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Ах ,забыл. Повторю старый вопрос. На месте редакции также попросил бы сравнение со стариной Мюллером по кол-ву раундов, коль скоро взялись Мюллера оптимизировать.
19 сен 19, 12:52    [21974134]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
exp98
Ах ,забыл. Повторю старый вопрос. На месте редакции также попросил бы сравнение со стариной Мюллером по кол-ву раундов, коль скоро взялись Мюллера оптимизировать.
Спасибо за вопрос!

Отвечаю:

По тесту Мюллера-Рабина количество раундов оптимально около log (n).
При этом, если два условия теста не выполняются, то число - составное.
В этом случае количество раундов будет намного меньше.

По эвристическому алгоритму:
- для s = 1 (50% всех нечётных чисел) количество раундов А (пока 10 - 15, дальше покажут проверки).
- для s > 1 количество раундов может быть А * s. Исследования до 1 000 000 000 показали, что количество раундов не превышает А * 8.
При этом, если при некоторой комбинации a (основание степени) и s2 (0=< s2 < s) определяется остаток по модулю, отличный от 1 и от (n - 1), то число n - составное.
В этом случае количество раундов будет намного меньше.
19 сен 19, 13:27    [21974195]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
автор
В результате:
на диапазоне от 5 до 50 000 000 время проверки мини диапазона из 1 000 000 чисел составляет 9 сек.
на диапазоне от 350 000 000 до 400 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 12 сек.
на диапазоне от 750 000 000 до 800 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 13 сек.
на диапазоне от 1 500 000 000 до 1 550 000 000 время проверки мини диапазона
из 1 000 000 чисел составляет 13 сек.
По этим диапазонам мы сверим с моим алгоритмом. Количество штук.
В первом случае - 3001132,
во втором - 2532800,
в третьем - 2442998 (я изменил диапазон),
в четвертом - 2364554
19 сен 19, 14:42    [21974323]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Нарисовал теоретическую табличку. Primes theoretical взял по формуле.
Range Primes Found Primes (theoretical) Elapsed time
3 - 50 000 000 2 820 471
350_000_000 - 400_000_000 2 404 426
700_000_000 - 750_000_000 2 330 675
1_500_000_000 - 1_550_000_000 2 252 774
2^200 +1 - 2^200 + 1 + 50 000 000 7134
2^500 +1 - 2^500 + 1 + 400 000 576
2^1024 +1 - 2^1024 +1 + 400 000 281


Здесь надо в формулу с логарифмом поставить вещественное число (double) для толстых чисел.
Вида 2^N + .... Математики. Помогайте.
+

scala> def primesInterval(a : Double, b : Double) : Double = b / Math.log(b) - a / Math.log(a)
primesInterval: (a: Double, b: Double)Double

scala>

scala> primesInterval(3.0 , 50_000_000)
res23: Double = 2820468.5898528607

scala> primesInterval(350_000_000 , 400_000_000)
res24: Double = 2404426.330841452

scala>

scala>

scala> primesInterval(700_000_000 , 750_000_000)
res25: Double = 2330675.484381996

scala> primesInterval(700_000_000 , 750_000_000)
res26: Double = 2330675.484381996

scala> primesInterval(1_500_000_000 , 1_550_000_000)
res27: Double = 2252774.7513875216
19 сен 19, 15:31    [21974382]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Следующие уточнения:

1. Лучше для Range ввести 2 колонки, может быть придётся вычитать.
2. 2-я и 3-я колонки - эти цифры посчитаны алгоритмом, почему они в разных колонках?
3. Что будем заносить в колонку Elapsed time?
Время всего диапазона или мини диапазона.
У меня иногда "глючит" время - приходится выключать ПК (наверное, охлаждаться).
4. О какой формуле с логарифмом идёт речь?
5. В коде - число за точкой это ....?
19 сен 19, 16:19    [21974439]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Gennadiy Usov
2. 2-я и 3-я колонки - эти цифры посчитаны алгоритмом, почему они в разных колонках?
3. Что будем заносить в колонку Elapsed time?

Заполни пожалуйста пустые колонки. Мне просто очень лень рыскать во всех текстах и собирать.

Elapsed Time - потраченное время работы алгоритма.
19 сен 19, 16:31    [21974450]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Нарисовал теоретическую табличку. Primes theoretical взял по формуле.
Range Primes Found Primes (theoretical) Elapsed time
3 - 50 000 000 2 820 471 8,38
350_000_000 - 400_000_000 2 404 426 9,59
750_000_000 - 800_000_000 2 330 675 10,06
1_500_000_000 - 1_550_000_000 2 252 774 надо пересчитать
2^200 +1 - 2^200 + 1 + 1 000 000 7134 2,06
2^500 +1 - 2^500 + 1 + 200 000 576 3,21
2^1024 +1 - 2^1024 +1 + 200 000 281 21,59
19 сен 19, 16:48    [21974471]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
2 820 471 - это приближённая величина. Я ее взял по формуле плотности простых чисел. А ты впиши туда фактическую.

Сколько нашел твой алгоритм. Это как-бы такая проверка.
19 сен 19, 16:51    [21974476]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Нарисовал теоретическую табличку. Primes theoretical взял по формуле.
Range Primes Found Primes (theoretical) Elapsed time
3 - 50 000 000 3 001 132 2 820 471 8,38
350_000_000 - 400_000_000 2 532 800 2 404 426 9,59
750_000_000 - 800_000_000 2 442 998 2 330 675 10,06
1_500_000_000 - 1_550_000_000 2 364 554 2 252 774 надо пересчитать
2^200 +1 - 2^200 + 1 + 1 000 000 7134 2,06
2^500 +1 - 2^500 + 1 + 200 000 576 3,21
2^1024 +1 - 2^1024 +1 + 200 000 281 21,59
19 сен 19, 17:04    [21974497]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
По натуральному логарифму.

Я осилил посчитать.



Деление посчитаю в больших десятичных. А вот как учесть плюс 1 миллион?
19 сен 19, 17:19    [21974516]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
По натуральному логарифму.
Я осилил посчитать.

Деление посчитаю в больших десятичных. А вот как учесть плюс 1 миллион?
Через о(малое)...
19 сен 19, 18:25    [21974600]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Не понял.
19 сен 19, 18:28    [21974605]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Тут у вас диалог 2-х посвящённых.
Когда закончите, свистните.
19 сен 19, 18:29    [21974607]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Gennadiy Usov
mayton
По натуральному логарифму.
Я осилил посчитать.

Деление посчитаю в больших десятичных. А вот как учесть плюс 1 миллион?
Через о(малое)...
Разница между и очень мала.

Разница где-то на 50-м знаке. Это надо обязательно учесть?
19 сен 19, 19:01    [21974641]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Gennadiy Usov
Gennadiy Usov
пропущено...
Через о(малое)...
Разница между и очень мала.

Разница где-то на 50-м знаке. Это надо обязательно учесть?

Да. В этом проблема больших чисал. Эта малая разница встанет в знаменатель и даст нам приближенное
количество простых на самом проблемном интревале. На малом криптографическом пороге. На 2^512 степени.
А я уверен что у тебя в коде есть слабое место. И эту слабость можно проверить через такую приближённую
оценку.
19 сен 19, 19:19    [21974649]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Gennadiy Usov
Разница между и очень мала.
Разница где-то на 50-м знаке. Это надо обязательно учесть?
Да. В этом проблема больших чисал. Эта малая разница встанет в знаменатель и даст нам приближенное
количество простых на самом проблемном интревале. На малом криптографическом пороге. На 2^512 степени.
А я уверен что у тебя в коде есть слабое место. И эту слабость можно проверить через такую приближённую
оценку.
Но у нас нет точной формулы количества простых чисел на интервале.
Только оценка количества.

Так что, там допуск, здесь допуск...
19 сен 19, 19:35    [21974665]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Нам нужно сравить твой алгоритм с чем-то эталонным.
Самое простое сравнение на малых числах - это гонять решето и метод грубой силы.

Для толстых чисел я пока придумал просто учет количества. Если он не прокатит - я попробую
метод isProbablePrime. Поскольку твой метод считает точное количество - мы можем делать
взаимные сверки.
19 сен 19, 19:40    [21974668]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Нам нужно сравить твой алгоритм с чем-то эталонным.
Самое простое сравнение на малых числах - это гонять решето и метод грубой силы.
Для толстых чисел я пока придумал просто учет количества. Если он не прокатит - я попробую
метод isProbablePrime. Поскольку твой метод считает точное количество - мы можем делать
взаимные сверки.
Метод грубой сила или что-то подобное "заканчивается" где-то далеко от 2^1024.

Один известный мне "калькулятор - определение простых чисел" работает только до 2^420.
19 сен 19, 19:52    [21974680]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
По поводу толстых натуральных логарифмов я создам отдельный топик.
19 сен 19, 19:57    [21974682]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
https://www.sql.ru/forum/1317260/tolstye-naturalnye-logarifmy
20 сен 19, 12:11    [21975121]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Хотел ещё уточнить. Вы писали, что эталонный мюллер работает со скор-ю ln(n) или что-то подобное. Но ведь это теоретическая оценка? Мне непонятно, может на практике он работает как получится? и может очень часто получается гораздо быстрее, нет? у вас чевой-то говорилось про раунды, про то, про сё. Может в большинстве случаев всё как у вас?
20 сен 19, 19:00    [21975680]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
exp98
Хотел ещё уточнить. Вы писали, что эталонный мюллер работает со скор-ю ln(n) или что-то подобное. Но ведь это теоретическая оценка? Мне непонятно, может на практике он работает как получится? и может очень часто получается гораздо быстрее, нет? у вас чевой-то говорилось про раунды, про то, про сё. Может в большинстве случаев всё как у вас?
В тесте Миллера-Рабина упор идёт на вероятность.
Он не знает, что делать с получаемыми числами:
у многих составных чисел по разным a и s иногда "выскакивают" нужные для простых чисел значения остатков по модулю.

А раз есть вероятность, то надо быть уверенным:
чем больше нужных чисел, тем большая уверенность.

Появился log(n) для полной уверенности.
Часть составных чисел быстро "вылетают" - там нет нужных для простых чисел величин.
А у другой части составных чисел "большое засилье" таких величин.

У меня простая система, без вероятностей, с определённым количеством раундов,
проверенная уже на числах от 5 до 930 000 000.
20 сен 19, 19:32    [21975695]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Прошел число 1 000 000 000.

-perep- 998000131 3045476 31524295 0 5 3
2019-09-21-11.58.37
-perep- 999000133 3093917 32024662 0 3 3
2019-09-21-12.04.52
-N blok- 3141866 3 3

В конце этого диапазона время обработки мини диапазона составляет 6 мин. 15 сек.

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

Откуда: loopback
Сообщений: 42946
Добавил колонку average speed.
Range Primes Found Primes (theoretical) Elapsed time Average Speed (primes/sec)
3 - 50 000 000 3 001 132 2 820 471 8,38 358 130
350_000_000 - 400_000_000 2 532 800 2 404 426 9,59 264 108
750_000_000 - 800_000_000 2 442 998 2 330 675 10,06 242 842
1_500_000_000 - 1_550_000_000 2 364 554 2 252 774 надо пересчитать
2^200 +1 - 2^200 + 1 + 1 000 000 7134 2,06 3 463
2^500 +1 - 2^500 + 1 + 200 000 576 3,21 179
2^1024 +1 - 2^1024 +1 + 200 000 281 21,59 13
23 сен 19, 00:26    [21976406]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Добавил колонку average speed.
Range Primes Found Primes (theoretical) Elapsed time Average Speed (primes/sec)
3 - 50 000 000 3 001 132 2 820 471 8,38 358 130
350_000_000 - 400_000_000 2 532 800 2 404 426 9,59 264 108
750_000_000 - 800_000_000 2 442 998 2 330 675 10,06 242 842
1_500_000_000 - 1_550_000_000 2 364 554 2 252 774 11,04
2^200 +1 - 2^200 + 1 + 1 000 000 7134 2,06 3 463
2^500 +1 - 2^500 + 1 + 200 000 576 3,21 179
2^1024 +1 - 2^1024 +1 + 200 000 281 21,59 13
23 сен 19, 10:08    [21976531]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Добавил 100 тысяч на диапазоне 2048 бит.

Вот данные для проверки. Две таблички надо соединить. Но уже поздно. Я засыпаю.

Range Primes Found(Usoff) Primes Found(JDK::BigInteger) Primes (theoretical) Elapsed time(s) Average Speed (primes/sec)
2^200 +1 - 2^200 + 1 + 1 000 000713561189
2^500 +1 - 2^500 + 1 + 200 0005772288
2^1024 +1 - 2^1024 + 1 + 200 000282835
2^2048 +1 - 2^2048 + 1 + 100 00079272


public static void test(String label, BigInteger a, BigInteger b) {
        long t1 = currentTimeMillis();
        int cnt = 0;
        while(a.compareTo(b) < 0) {
            a = a.nextProbablePrime();
            cnt++;
        }
        long t2 = currentTimeMillis();
        long elapedTimeS = (t2 - t1) / 1000;
        long avgSpeed = elapedTimeS != 0 ? cnt / elapedTimeS : 0;
        printf("%s;;%d;;%d;%d\n", label, cnt, elapedTimeS, avgSpeed);
    }

    public static void main(String[] args) {
        printf("[CSV=;]Range; Primes Found(Usoff) ; Primes Found(JDK::BigInteger) ; Primes (theoretical) ; Elapsed time(s) ; Average Speed (primes/sec)\n");
        test("2^200 +1 - 2^200 + 1 + 1 000 000", TWO.pow(200).add(ONE),  TWO.pow(200).add(ONE).add(BigInteger.valueOf(1_000_000)));
        test("2^500 +1 - 2^500 + 1 + 200 000",   TWO.pow(500).add(ONE),  TWO.pow(500).add(ONE).add(BigInteger.valueOf(200_000)));
        test("2^1024 +1 - 2^1024 + 1 + 200 000", TWO.pow(1024).add(ONE), TWO.pow(1024).add(ONE).add(BigInteger.valueOf(200_000)));
        test("2^2048 +1 - 2^2048 + 1 + 100 000", TWO.pow(2048).add(ONE), TWO.pow(2048).add(ONE).add(BigInteger.valueOf(100_000)));
        printf("[/CSV]");
    }
30 сен 19, 00:50    [21982245]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Здесь я выскакиваю за range.

while(a.compareTo(b) < 0) {
            a = a.nextProbablePrime();
            cnt++;
        }


Последний инкремент - лишний. Поэтому от всех результатов можно вычесть 1.
30 сен 19, 09:28    [21982363]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Поскольку появилась новая строка в таблице, то решил ещё раз эту строку пересчитать
(не помню, чтобы считал диапазон на 100000)

2^2048 +1 - 2^2048 + 1 + 100 000

Определено 78 простых чисел.
Программа считала с 2019-09-30-11.35.28 по 2019-09-30-13.14.28
30 сен 19, 13:19    [21982636]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Это мы протестили генерацию простых на крипто-диапазоне. 2^2048 e.t.c.
В принципе Рабин-Миллер+Люка и создавались для этого.
30 сен 19, 13:40    [21982670]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Это мы протестили генерацию простых на крипто-диапазоне. 2^2048 e.t.c.
В принципе Рабин-Миллер+Люка и создавались для этого.
Так это прекрасное сообщение!

Мы расходимся в одном числе! (79 и 78)

Прекрасно!
30 сен 19, 14:12    [21982712]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Яж говорю. Я допустил ошибку. Самое последнее простое число превышает правую границу. Поэтому надо делать мину 1 ко всем
моим результатам.
30 сен 19, 14:45    [21982760]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Но не обольщайся. Миллер-Рабит хоть и шумит но имеет шанс поймать составное. Тоесть несколько запусков
Миллера - выровняют картинку. У тебя-же 100% детерминизм. Невыявленная ошибка.
30 сен 19, 14:56    [21982780]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Но не обольщайся. Миллер-Рабит хоть и шумит но имеет шанс поймать составное. Тоесть несколько запусков
Миллера - выровняют картинку. У тебя-же 100% детерминизм. Невыявленная ошибка.
Или строгая формула (алгоритм)
30 сен 19, 15:13    [21982814]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Gennadiy Usov
mayton
Но не обольщайся. Миллер-Рабит хоть и шумит но имеет шанс поймать составное. Тоесть несколько запусков
Миллера - выровняют картинку. У тебя-же 100% детерминизм. Невыявленная ошибка.
Или строгая формула (алгоритм)

Рано хвастаешся.
30 сен 19, 17:05    [21983001]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Почему Primes (theoretical) до сих пор не заполнено? Может это тоже теперь эвристика для всех последующих диапазонов.
30 сен 19, 17:34    [21983038]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Ребята я все не успеваю. Заполните плиз табличку.
30 сен 19, 18:06    [21983064]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Это любой же может. Ну дык ведь я теперь девочка для набивки, с длинными ноготочками.
Range	Primes(theoretical)
2^200+1млн	7161
2^500+200тыр	575
2^1024+200тыр	281
2^2048+1тыр	70
2^4096+5тыр	176
2^4096+1млн	352
2^8192+5тыр	88
2^8192+1млн	176

....... и так далее )) Можно даже не считать уже
Достаточно делить и умножать предыдущее. Но вы пока это посчитайте ... а я потом ещё оценок подкину.
30 сен 19, 22:06    [21983312]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Опровержение)

RangePrimes(theoretical)
2^200+1млн7161
2^500+200тыр575
2^1024+200тыр281
2^2048+100тыр70
2^4096+500тыр176
2^4096+1млн352
2^8192+500тыр88
2^8192+1млн176

Модератор: Поправил


Сообщение было отредактировано: 1 окт 19, 14:42
30 сен 19, 22:10    [21983315]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Я говорю табличку заполните.
1 окт 19, 11:28    [21983596]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
mayton, я первым это сказал. И потом, кто больше всех заинтересован в пиаре этой темы, того пусть и тапки. Имхо, отчёты и презентации - занятие для благородных особ, а я - золушка, мне бы вечером принц приехал на серебрянном коне.
1 окт 19, 14:38    [21983913]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Усов - твой принц.

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

Откуда:
Сообщений: 1842
mayton
Усов - твой принц.

Его ответственность что-то доказывать. Наша позиция - позиция критиков. Мы - опровергаем.
Что конкретно опровергаете?

А то много чего есть на форуме.
Много чего и вашего (от слова - мы).
1 окт 19, 15:17    [21983971]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Не скажу. Иш ты какой хитрый. Вот скажу - тогда побежишь исправлять.
1 окт 19, 15:25    [21983982]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Раз ничего нет, значит, и исправлять нечего

Строгое математическое доказательство
1 окт 19, 15:30    [21983992]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Ну я-то скорее скептик, чем критик.
И скажу крылатыми словами: Такой принц нам не нужен!
Gennadiy Usov
Раз ничего нет, значит, и исправлять нечего
Строгое математическое доказательство
Хотелось бы верить ... да только в суде так строго бывает: на "Нэт!" и суда нет(цэ)

Нет, а ну-ка, погоди, что значит "ничего нет"? т.е. все ку-ка-ре-ку - лажа?
2 окт 19, 22:32    [21985441]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Интересная ситуация получается

Есть эвристический алгоритм для определения всех простых чисел.
Есть упрощения алгоритма для определения всех чисел Мерсенна и их окружения.
Есть упрощение алгоритма для быстрого поиска 50% простых чисел.
Конечно, с учётом возможностей ПК.

И вдруг:
mayton
Наша позиция - позиция критиков. Мы - опровергаем.
Далее
Gennadiy Usov
Что конкретно опровергаете?
И итог
mayton
Не скажу. Иш ты какой хитрый. Вот скажу - тогда побежишь исправлять.
А это вообще ни в какие ворота не лезет
exp98
Ну я-то скорее скептик, чем критик.
И скажу крылатыми словами: Такой принц нам не нужен!
Gennadiy Usov
Раз ничего нет, значит, и исправлять нечего
Строгое математическое доказательство
Хотелось бы верить ... да только в суде так строго бывает: на "Нэт!" и суда нет(цэ)
Нет, а ну-ка, погоди, что значит "ничего нет"? т.е. все ку-ка-ре-ку - лажа?
А где логика с математикой?
3 окт 19, 05:53    [21985510]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Ребята я все не успеваю. Заполните плиз табличку.
Кстати, mayton,
а как поживает табличка?

"Завяла"?
3 окт 19, 06:07    [21985512]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Усов. Алгоритм чего ты разработал?
3 окт 19, 08:32    [21985529]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
3 окт 19, 09:40    [21985560]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Усов. Алгоритм чего ты разработал?
Справка из начала сообщения21985510:

Есть эвристический алгоритм для определения всех простых чисел.
Есть упрощение алгоритма для определения всех чисел Мерсенна и их окружения.
Есть упрощение алгоритма для быстрого поиска 50% простых чисел.
3 окт 19, 10:03    [21985571]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Шикарно.
3 окт 19, 10:03    [21985572]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Всё уже придумано до нас. Усов, если вы думаете, что придумали что-то новое, то вы ошибаетесь, все это уже известно, просто вы плохо искали.

Придумал я как-то раз, как как можно добавить в сообщение контрольных битов, чтобы можно было не только обнаружить, что один из битов сообщения по дороге изменился, но и узнать какой именно, и исправить его. А оказалось, что Хэмминг придумал то же самое еще 50 лет назад.

Или вот тесты простоты и факторизация. Что делает тест Миллера-Рабина? Он фактически пытается убедиться в том, что порядок мультипликативной группы вычетов по модулю P делит P-1. По теореме о структуре конечной абелевой группы порядок любого элемента группы делит порядок группы. И если мы находим элемент, порядок которого не делит P-1 - значит число составное.
А можно, используя делители P-1, доказать простоту числа, не перебирая делители самого P.
И есть метод факторизации - p-1 метод Полларда - предполагая, что N=P*Q, пытаемся, перебрав все возможные делители P-1, получить единицу по модулю P.

Повторюсь, всё это базируется на мультипликативной группе вычетов по модулю P. А если взять другую группу?
Возьмем например матрицы 2х2. Умножение матриц не коммутативно, плохо, группа не абелева. Но можно выбрать коммутативную подгруппу. Например, для матриц вида
 x y
ny x
где n фиксированное, умножение будет коммутативным:
 x1 y1      x2 y2      (x1x2+ny1y2) (x1y2+x2y1)
ny1 x1 * ny2 x2 = n(x1y2+x2y1) (x1x2+ny1y2)
Если дополнительно потребовать, чтобы определитель такой матрицы был равен 1, получим уравнение Пелля, и решения этого уравнения можно умножать, получая новые решения - это как раз соответствует умножению таких матриц.

Ну вот у нас есть абелева группа решений уравнения Пелля. А давайте рассмотрим их по модулю простого числа P, и поинтересуемся порядком этой группы.
Оказывается, что если n квадратичный вычет по модулю P, то порядок этой группы равен P-1, а если n квадратичный невычет, то порядок равен P+1.
Первый случай неинтересен, такая группа изоморфна мультипликативной группе вычетов по модулю P. А вот случай невычета можно рассмотреть поподробнее.
Тут можно построить тест простоты по аналогии с Ферма: найдем n такое, что символ Якоби (n/P) был равен -1 и решение уравнения Пелля для этого n. Возведем это решение в степень P+1 по модулю P. Убедимся, что получили тривиальное решение (1,0).
Или даже аналог Миллера-Рабина: представим P+1 в виде 2sd, d нечетно. Возводим начальное решение в степень d, и убеждаемся, что либо сразу получили (1,0), либо, после не более s возведений в квадрат, (-1,0).

И вот придумал я значит эту конструкцию, проверил, что работает, а потом посмотрел повнимательней - а оказалось, что Люка это уже больше ста лет назад придумал. Только описано оно у него немножко по другому - через последовательности Люка.
Последовательности Люка определяются как линейные рекуррентные последовательности Vn и Un, параметризованные парой коэффициентов P, Q.
Но можно получить матричное представление: считаем дискриминант характеристического многочлена D = P*P - 4Q и подставляем в матрицу
P/2 1/2
D/2 P/2
Определитель этой матрицы равен Q, а возводя ее в степень n, получим Vn/2 и Un/2 в первой строке. Сильный вариант теста как раз требует Q=1 - вот и уравнение Пелля.

И P+1 метод факторизации также можно описать через степени решений уравнения Пелля вместо последовательностей Люка.
Так что всё придумано до нас...
3 окт 19, 10:30    [21985604]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Всё уже придумано до нас. Усов, если вы думаете, что придумали что-то новое, то вы ошибаетесь, все это уже известно, просто вы плохо искали.
.....
Так что всё придумано до нас...
Вы ещё забыли указать, что:

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

И непонятно, каким образом все идеи и методы, что Вы перечислили в сообщении, помогают определять простые числа.

Это инструменты для решения проблемы определения простых чисел.

А теперь у меня к Вам вопросы:

1. А где написано, что числа Мерсенна определяет ещё какой-нибуть тест, кроме теста Люка-Лемера, да ещё с сопоставимой скоростью?

2. Где написано, что можно БЕЗ ВЕРОЯТНОСТИ определять ВСЕ простые числа (с учётом мощности ПК)?

3. Где написано, что можно за менее 4-х раундов для каждого числа определять 50% ВСЕХ простых чисел (с учётом мощности ПК)?

Говорите конкретно, а не пересказывайте всю высшую математику.
3 окт 19, 10:49    [21985615]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
И главное, кто определял простые числа в окрестности чисел Мерсенна?
Плюс 4, плюс 8, плюс 12 и т.д.

А эвристический алгоритм определяет такие числа.

То есть, кроме последовательности простых чисел Мерсенна
Mn = 2^n - 1
эвристический алгоритм определяет простые числа
Mnk = 2^n - 1 + k, k = 4, 8, 12, 16, 20, ...

Это тоже уже было?
3 окт 19, 11:17    [21985646]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
1. А где написано, что числа Мерсенна определяет ещё какой-нибуть тест, кроме теста Люка-Лемера, да ещё с сопоставимой скоростью?

2. Где написано, что можно БЕЗ ВЕРОЯТНОСТИ определять ВСЕ простые числа (с учётом мощности ПК)?

3. Где написано, что можно за менее 4-х раундов для каждого числа определять 50% ВСЕХ простых чисел (с учётом мощности ПК)?

1. Тест Люка-Лемера для простоты проверки 2p-1 требует p-1 возведений в квадрат. Возведение в степень 2p-1-1 потребует p-2 возведений в квадрат плюс p-2 умножений, что минимум в два раза медленнее, а с учетом того, что возведение в квадрат быстрее, чем умножение произвольных чисел, более чем в два раза медленнее. Для поиска максимальных известных простых чисел это весьма существенно - там каждое число на обычном компьютере проверяется несколько месяцев.

2. Для математиков, пока вы строго математически не ДОКАЗАЛИ, что ваш алгоритм действительно это определяет, он не имеет никакого значения. А с практической точки зрения, для криптографических целей комбинация одного раунда Миллера-Рабина с тестом Люка достаточна.

3. Опять же, для математиков 50% простых - совсем не интересно. Либо вы доказываете теорему, которая выполняется для всех простых, либо это никому не нужно.
3 окт 19, 12:02    [21985695]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
3. Опять же, для математиков 50% простых - совсем не интересно. Либо вы доказываете теорему, которая выполняется для всех простых, либо это никому не нужно.
Как сказать...

Согласно тесту Миллера-Рабина для очень больших чисел N количество раундов при поиске простого числа составляет около log(N).

Допустим, нужно быстро найти несколько простых чисел на диапазоне очень больших чисел.

И для этого диапазона находится 50% простых чисел всего за 4 раунда.

Это никому не нужно?

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

Откуда:
Сообщений: 1842
Barlone
2. Для математиков, пока вы строго математически не ДОКАЗАЛИ, что ваш алгоритм действительно это определяет, он не имеет никакого значения.
А эвристический алгоритм и не надо доказывать по определению.

То что, алгоритм работает, доказано проведёнными расчётами на диапазоне чисел от 5 до 1 000 000 000.
Программа приведена на топике.

Далее, согласно эвристике, алгоритм можно распространить на большие числа.

Barlone
А с практической точки зрения, для криптографических целей комбинация одного раунда Миллера-Рабина с тестом Люка достаточна.
Данное утверждение не совсем верно.

Данные тесты - вероятностные.
Следовательно, есть вероятность сразу "попасть", а есть вероятность "промахнуться" с одного раза.
Что выбираете?
3 окт 19, 12:31    [21985735]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Вот на этих числах свой алгоритм проверьте: https://oeis.org/A074773
3 окт 19, 12:34    [21985740]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Вот еще хорошее число: 3825123056546413051
3 окт 19, 12:37    [21985749]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
1. Тест Люка-Лемера для простоты проверки 2p-1 требует p-1 возведений в квадрат.
Возведение в степень 2p-1-1 потребует p-2 возведений в квадрат плюс p-2 умножений, что минимум в два раза медленнее,
а с учетом того, что возведение в квадрат быстрее, чем умножение произвольных чисел, более чем в два раза медленнее.
Для поиска максимальных известных простых чисел это весьма существенно -
там каждое число на обычном компьютере проверяется несколько месяцев.
Сошлюсь на эвристику (практика - это сила) ...

Взял из вики описание теста Люка-Лемера и написал программу на Питоне.
Взял эвристический алгоритм (одно уравнение) и написал программу на Питоне.

Обе программы определяли простые числа Мерсенна Mn для n < 20000.
Дальше - программа очень медленно работала.

Результаты работы программ совпали: по простым числам и почти по времени (несколько процентов).

При отдельном прогоне конкретного простого числа иногда эвристический алгоритм чуточку обгонял тест по времени.
3 окт 19, 12:50    [21985763]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9508
Gennadiy Usov
Сошлюсь на эвристику (практика - это сила) ...
... но не доказательство.
Любое число подтверждений в конкретных частных случаях не позволяет доказать гипотезу, зато единственное опровержение требует отвергнуть гипотезу.
3 окт 19, 12:55    [21985775]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Взял из вики описание теста Люка-Лемера и написал программу на Питоне.
На питоне? Да, хороший вариант для измерения скорости :)
3 окт 19, 13:00    [21985784]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Вот еще хорошее число: 3825123056546413051
Программа оценила число:

2019-10-03-13.00.20
-число- 3825123056546413053
-Нет простых чисел- 0
2019-10-03-13.00.20
3 окт 19, 13:01    [21985790]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9508
Gennadiy Usov
Программа оценила число:
2019-10-03-13.00.20
-число- 3825123056546413053
-Нет простых чисел- 0
2019-10-03-13.00.20
Этот загадочный ответ сообщает, что число простое или как?
3 окт 19, 13:04    [21985794]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Gennadiy Usov
Взял из вики описание теста Люка-Лемера и написал программу на Питоне.
На питоне? Да, хороший вариант для измерения скорости :)
Но сравнивались две прогроммы на Питоне.

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

Откуда:
Сообщений: 1348
А насчет практики - есть такое число Скьюза. Это про гипотезу, что количество простых чисел, не превосходящих n, меньше чем интегральный логарифм li(n). Она выполняется до 10316, а потом перестает выполняться... Вы свой алгоритм хотя бы до 10316 проверяли?
3 окт 19, 13:08    [21985803]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9508
Gennadiy Usov
Я говорю об одинаковых условиях для двух программ: старенький ПК, Питон.
И что?
Вот я в детстве иногда лепил из пластилина. Кое-что из моих "творений" даже стояло дома на видном месте.
И что? Кому и зачем всё это может быть интересно?

P.S.
"Всё" - не столько мои излияния, сколько ваши "труды". Уж не обижайтесь.
3 окт 19, 13:10    [21985806]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Basil A. Sidorov
Gennadiy Usov
Программа оценила число:
2019-10-03-13.00.20
-число- 3825123056546413053
-Нет простых чисел- 0
2019-10-03-13.00.20
Этот загадочный ответ сообщает, что число простое или как?
Программа "приняла" число и "сказала",

что среди представленных чисел (одно число в перечне) 0 простых чисел. (слово "нет" - лишнее, убираю)

2019-10-03-13.09.54
-число- 3825123056546413053
-простых чисел- 0
2019-10-03-13.09.54
3 окт 19, 13:11    [21985809]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
пропущено...
На питоне? Да, хороший вариант для измерения скорости :)
Но сравнивались две прогроммы на Питоне.

Я же не говорю о времени работы программ.
Я говорю об одинаковых условиях для двух программ: старенький ПК, Питон.
Не, просто питон известен своей тормознутостью...
Хотя, вы в степень то наверное встроенной функцией возводили?
3 окт 19, 13:11    [21985810]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Basil A. Sidorov
пропущено...
Этот загадочный ответ сообщает, что число простое или как?
Программа "приняла" число и "сказала",

что среди представленных чисел (одно число в перечне) 0 простых чисел. (слово "нет" - лишнее, убираю)

2019-10-03-13.09.54
-число- 3825123056546413053
-простых чисел- 0
2019-10-03-13.09.54
Эй, у меня последняя цифра была 1
3 окт 19, 13:15    [21985812]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9508
Gennadiy Usov
Программа "приняла" число и "сказала", что среди представленных чисел (одно число в перечне) 0 простых чисел. (слово "нет" - лишнее, убираю)
"Ясвасхудею".
А выдать что-то вроде:
  Всего чисел - xxx
Проверено чисел - yyy
Простых чисел - zzz
?

Ну или учитывая, что простые числа, типа, "редкие", по мере проверки просто печать список "эвристически простых", а по итогу выдать общую статистику?
3 окт 19, 13:16    [21985814]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
Вот еще хорошее число: 3825123056546413051
Программа оценила число:

2019-10-03-13.00.20
-число- 3825123056546413053
-Нет простых чисел- 0
2019-10-03-13.00.20
не то число
3 окт 19, 13:16    [21985815]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Gennadiy Usov
пропущено...
Программа оценила число:

2019-10-03-13.00.20
-число- 3825123056546413053
-Нет простых чисел- 0
2019-10-03-13.00.20
не то число
Разобрался.

У меня цикл по нечётным числам с шагом 2 на диапазоне, я назначил число и ограничил на +1,
а цикл (на то он и цикл) прибавляет и сравнивает с ограничителем.

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

Исправил (отнял 2):

2019-10-03-13.19.53
-число- 3825123056546413051
-простых чисел- 0
2019-10-03-13.19.53
3 окт 19, 13:26    [21985834]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
А насчет практики - есть такое число Скьюза. Это про гипотезу, что количество простых чисел, не превосходящих n, меньше чем интегральный логарифм li(n). Она выполняется до 10316, а потом перестает выполняться... Вы свой алгоритм хотя бы до 10316 проверяли?
На топике считал для некоторой таблички числа порядка 2^2048.

На диапазоне 2^1024 количество простых чисел на диапазоне совпало с расчётом mayton.

А вопрос один - с чем сравнивать, как проверять.
Делители "будут очень долго считать"...
3 окт 19, 13:34    [21985843]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
пропущено...
не то число
Разобрался.

У меня цикл по нечётным числам с шагом 2 на диапазоне, я назначил число и ограничил на +1,
а цикл (на то он и цикл) прибавляет и сравнивает с ограничителем.

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

Исправил (отнял 2):

2019-10-03-13.19.53
-число- 3825123056546413051
-простых чисел- 0
2019-10-03-13.19.53
Не сходится с тем, что вы про свой алгоритм рассказываете...
3 окт 19, 13:42    [21985851]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Basil A. Sidorov
Gennadiy Usov
Программа "приняла" число и "сказала", что среди представленных чисел (одно число в перечне) 0 простых чисел. (слово "нет" - лишнее, убираю)
"Ясвасхудею".
А выдать что-то вроде:
  Всего чисел - xxx
Проверено чисел - yyy
Простых чисел - zzz
?
Ну или учитывая, что простые числа, типа, "редкие", по мере проверки просто печать список "эвристически простых", а по итогу выдать общую статистику?
Согласен.

Поскольку задают вопросы, нужно привести программу в порядок:
красиво оформить выходные данные.

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

Откуда:
Сообщений: 1842
Barlone
Gennadiy Usov
Разобрался.
У меня цикл по нечётным числам с шагом 2 на диапазоне, я назначил число и ограничил на +1,
а цикл (на то он и цикл) прибавляет и сравнивает с ограничителем.
А печать идёт после выхода из цикла.
Внутри цикла составные числа программе не нужны, поэтому эти числа там не печатаются.
Исправил (отнял 2):

2019-10-03-13.19.53
-число- 3825123056546413051
-простых чисел- 0
2019-10-03-13.19.53
Не сходится с тем, что вы про свой алгоритм рассказываете...
И где расхождение?
3 окт 19, 13:47    [21985859]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
n = 3825123056546413051
n-1 = 21*1912561528273206525

a(n-1)/2 mod n равно 1 или n-1 для всех a от 2 до 36...
3 окт 19, 13:51    [21985863]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
n = 3825123056546413051
n-1 = 21*1912561528273206525
a(n-1)/2 mod n равно 1 или n-1 для всех a от 2 до 36...
Хороший пример!

У меня записано:
"Число А выбирается равное 10, с запасом – пока подтверждено только одно число 25326001 при а = 7.
Можно увеличить число 10.
Но для этого нужны проверки для чисел, больших 250 000 000."

Просто увеличиваем А до 15 простых чисел!
То есть до 47.
И смотрим дальше.

Ещё есть примеры?
3 окт 19, 14:58    [21985926]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Aleksandr Sharahov
Member

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

Откуда:
Сообщений: 1842
Насчет простых чисел поторопился...

У числа 3825123056546413051 log (n) = 42...

Поэтому ставим А = 42 и рассматриваем все числа от 2 до 42.

Число 36 - попадает.

Ещё раз уточнил старые расчёты.

Для тестовых расчётов log (1 000 000 001) = 20.

Мне встречались числа 11, 13, 15.

Поэтому, A = log (n).

И в тесте Миллера-Рабина log (n).
Однако ушли от вероятности.
3 окт 19, 15:36    [21985967]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Насчет простых чисел поторопился...

У числа 3825123056546413051 log (n) = 42...

Поэтому ставим А = 42 и рассматриваем все числа от 2 до 42.

Число 36 - попадает.

Ещё раз уточнил старые расчёты.

Для тестовых расчётов log (1 000 000 001) = 20.

Мне встречались числа 11, 13, 15.

Поэтому, A = log (n).

И в тесте Миллера-Рабина log (n).
Однако ушли от вероятности.

Эх, опять промахнулись... 3317044064679887385961981 - вот тут уже 43 надо.
3 окт 19, 15:41    [21985973]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
А насчет простых то как раз всё правильно: понятно, что если am mod n = 1 и bm mod n = 1 то и (ab)m mod n = 1
3 окт 19, 15:44    [21985979]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
import math

def jacobi(a, n):
    assert(a > 0 and n % 2 == 1)
    a %= n
    t = 1
    while a != 0:
        while a % 2 == 0:
            a = a // 2
            r = n % 8
            if r == 3 or r == 5:
                t = -t
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            t = -t
        a %= n
    if n == 1:
        return t
    else:
        return 0

def pair2(a, d, n):
    return ((a[0] * a[0] + n - 2) % n, (a[0] * a[1]) % n)
        
def pairmul(a, b, d, n):
    x = (a[0] * b[0] + d * a[1] * b[1]) % n
    if x % 2 == 0:
        x = x // 2
    else:
        x = (n + x) // 2
    y = (a[0] * b[1] + b[0] * a[1]) % n
    if y % 2 == 0:
        y = y // 2
    else:
        y = (n + y) // 2
    return (x, y)

def pairpow(a, m, d, n):
    r = (1, 0)
    while m != 0:
        if m % 2 == 1:
            r = pairmul(r, a, d, n)
        a = pair2(a, d, n)
        m = m // 2
    return r

def isprime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    if n == 3:
        return True
    if n % 3 == 0:
        return False
    if n == 5:
        return True
    if n % 5 == 0:
        return False

    m = int(math.sqrt(n))
    if m * m == n:
        return False

    p = 3
    d = p * p - 4
    j = jacobi(d, n)
    while j == 1:
        p = p + 1
        d = p * p - 4
        j = jacobi(d, n)

    if j == 0:
        return False

    if pow(d, n // 2, n) != n - 1:
        return False

    a = pairpow((p, 1), (n + 1) // 2, d, n)
    if a[1] != 0:
        return False
    if a[0] != 1 and a[0] != n - 1:
        return False
    return True
Вот вам тест простоты на питоне, вызывать isprime(n) - проверяйте, ищите контрпримеры. Это как раз Люка.
3 окт 19, 15:46    [21985985]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Точнее, один раунд Ферма Соловея-Штрассена плюс Люка
3 окт 19, 15:53    [21985994]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Поторопился, если подсунуть квадрат очень большого числа, math.sqrt вычисляется с ошибкой, и в цикле поиска квадратичного невычета зависает... Поправил.
import math

def jacobi(a, n):
    assert(a > 0 and n % 2 == 1)
    a %= n
    t = 1
    while a != 0:
        while a % 2 == 0:
            a = a // 2
            r = n % 8
            if r == 3 or r == 5:
                t = -t
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            t = -t
        a %= n
    if n == 1:
        return t
    else:
        return 0

def pair2(a, d, n):
    return ((a[0] * a[0] + n - 2) % n, (a[0] * a[1]) % n)
        
def pairmul(a, b, d, n):
    x = (a[0] * b[0] + d * a[1] * b[1]) % n
    if x % 2 == 0:
        x = x // 2
    else:
        x = (n + x) // 2
    y = (a[0] * b[1] + b[0] * a[1]) % n
    if y % 2 == 0:
        y = y // 2
    else:
        y = (n + y) // 2
    return (x, y)

def pairpow(a, m, d, n):
    r = (1, 0)
    while m != 0:
        if m % 2 == 1:
            r = pairmul(r, a, d, n)
        a = pair2(a, d, n)
        m = m // 2
    return r

def isprime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    if n == 3:
        return True
    if n % 3 == 0:
        return False
    if n == 5:
        return True
    if n % 5 == 0:
        return False

    m = int(math.sqrt(n))
    if m * m == n:
        return False
    k = (m + n // m) // 2
    while k != m:
        m, k = k, (m + n // m) // 2
    if m * m == n:
        return False
    
    p = 3
    d = p * p - 4
    j = jacobi(d, n)
    while j == 1:
        p = p + 1
        d = p * p - 4
        j = jacobi(d, n)

    if j == 0:
        return False

    if pow(d, n // 2, n) != n - 1:
        return False

    a = pairpow((p, 1), (n + 1) // 2, d, n)
    if a[1] != 0:
        return False
    if a[0] != 1 and a[0] != n - 1:
        return False
    return True
    

n = 3317044064679887385961981
m = n // 2
print(isprime(3317044064679887385961981*3317044064679887385961981))

#for i in range (2, 44):
#    print (i, pow(i,m,n), jacobi(i,n))
3 окт 19, 16:10    [21986008]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
С куском отладочного кода в конце :)
3 окт 19, 16:13    [21986011]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Эх, опять промахнулись... 3317044064679887385961981 - вот тут уже 43 надо.
А вот и нет!

Здесь s = 2.
При s = 1 одни 1 и (n - 1) до 42.
А при s = 0 при 2 сразу составное!
3 окт 19, 16:23    [21986019]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Поторопился, если подсунуть квадрат очень большого числа, math.sqrt вычисляется с ошибкой, и в цикле поиска квадратичного невычета зависает...
Поправил.
Спасибо!

А если пройтись по всем нечётным, где s = 1, и считать 1 и (n - 1) до "выбывания"?
3 окт 19, 16:32    [21986033]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Barlone
Gennadiy Usov
Взял из вики описание теста Люка-Лемера и написал программу на Питоне.
На питоне? Да, хороший вариант для измерения скорости :)

В нашем случае это норм вариант. Тут-же принципиальная возможность изучается.
Перформанс - второе дело. Тем более что для Питона есть библиотеки поддержки длинных.
3 окт 19, 16:45    [21986047]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
Эх, опять промахнулись... 3317044064679887385961981 - вот тут уже 43 надо.
А вот и нет!

Здесь s = 2.
При s = 1 одни 1 и (n - 1) до 42.
А при s = 0 при 2 сразу составное!
Не понял, это как?
>>> a=3317044064679887385961981
>>> pow(2,a//4,a)
806966215798523717614900
>>> pow(2,a//2,a)
3317044064679887385961980
тут не видно, что составное
3 окт 19, 17:26    [21986094]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Будем категоризировать числа на "простые", "составные" и "неизвестные"?

Это было-бы честно в данном топике.
3 окт 19, 17:30    [21986099]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Что-то у меня сомнения, не наврал ли я в спешке где-то в алгоритме... Надо перепроверить еще раз
3 окт 19, 17:39    [21986109]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Gennadiy Usov
Здесь s = 2.
При s = 1 одни 1 и (n - 1) до 42.
А при s = 0 при 2 сразу составное!
Не понял, это как?
>>> a=3317044064679887385961981
>>> pow(2,a//4,a)
806966215798523717614900
>>> pow(2,a//2,a)
3317044064679887385961980
тут не видно, что составное
Вот мои расчёты по s = 0 (справа - основание степени, слева - s)

(0, 806966215798523717614900L, 2)
(0, 1L, 3)
(0, 3317044064679887385961980L, 4)
(0, 1L, 5)
(0, 806966215798523717614900L, 6)
(0, 806966215798523717614900L, 7)
(0, 2510077848881363668347081L, 8)

Уже при основании степени 2 видно, что остаток не равен ни 1, ни (n - 1).
А раз этот остаток не равен, то исходное число - составное.
3 окт 19, 17:50    [21986125]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
пропущено...
Не понял, это как?
>>> a=3317044064679887385961981
>>> pow(2,a//4,a)
806966215798523717614900
>>> pow(2,a//2,a)
3317044064679887385961980
тут не видно, что составное
Вот мои расчёты по s = 0 (справа - основание степени, слева - s)

(0, 806966215798523717614900L, 2)
(0, 1L, 3)
(0, 3317044064679887385961980L, 4)
(0, 1L, 5)
(0, 806966215798523717614900L, 6)
(0, 806966215798523717614900L, 7)
(0, 2510077848881363668347081L, 8)

Уже при основании степени 2 видно, что остаток не равен ни 1, ни (n - 1).
А раз этот остаток не равен, то исходное число - составное.
Чего?
13 - 1 = 22*3
Берем основание 2, 23 = 8, это не 1 и не 12 по модулю 13. 13 - составное число?
3 окт 19, 19:39    [21986221]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Barlone
Что-то у меня сомнения, не наврал ли я в спешке где-то в алгоритме... Надо перепроверить еще раз
Разобрался. Небольшая неточность, которая не влияет на результат проверки. Неканонично получилось, результат возведения в степень поделен пополам, но и сравнивается с единицей, а не с 2. Вобщем, можно не исправлять.
3 окт 19, 19:51    [21986234]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Чего?
13 - 1 = 22*3
Берем основание 2, 23 = 8, это не 1 и не 12 по модулю 13. 13 - составное число?
Уговорил. Будет 56.
Тем более, что log = 56.

Я забыл, что по алгоритму сначала (s - 1), а потом (s - 2) и т.д. А не наоборот.
3 окт 19, 19:55    [21986238]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Barlone
Barlone
Что-то у меня сомнения, не наврал ли я в спешке где-то в алгоритме... Надо перепроверить еще раз
Разобрался. Небольшая неточность, которая не влияет на результат проверки. Неканонично получилось, результат возведения в степень поделен пополам, но и сравнивается с единицей, а не с 2. Вобщем, можно не исправлять.
Да, а вот с квадратным корнем надо что-то сделать. 2^1023 еще лезет, а 2^1024 говорит "OverflowError: int too large to convert to float"
3 окт 19, 19:59    [21986239]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Ну теперь вот так:
import math

def jacobi(a, n):
    assert(a > 0 and n % 2 == 1)
    a %= n
    t = 1
    while a != 0:
        while a % 2 == 0:
            a = a // 2
            r = n % 8
            if r == 3 or r == 5:
                t = -t
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            t = -t
        a %= n
    if n == 1:
        return t
    else:
        return 0

def pair2(a, d, n):
    return ((a[0] * a[0] + n - 2) % n, (a[0] * a[1]) % n)
        
def pairmul(a, b, d, n):
    x = (a[0] * b[0] + d * a[1] * b[1]) % n
    if x % 2 == 0:
        x = x // 2
    else:
        x = (n + x) // 2
    y = (a[0] * b[1] + b[0] * a[1]) % n
    if y % 2 == 0:
        y = y // 2
    else:
        y = (n + y) // 2
    return (x, y)

def pairpow(a, m, d, n):
    r = (2, 0)
    while m != 0:
        if m % 2 == 1:
            r = pairmul(r, a, d, n)
        a = pair2(a, d, n)
        m = m // 2
    return r

def isprime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    if n == 3:
        return True
    if n % 3 == 0:
        return False
    if n == 5:
        return True
    if n % 5 == 0:
        return False

    q = n.bit_length()
    if q < 1023:
        m = int(math.sqrt(n))
        if m * m == n:
            return False
    else:
        m = n >> (q // 2)
    k = (m + n // m) // 2
    while k != m:
        m, k = k, (m + n // m) // 2
    if m * m == n:
        return False
    
    p = 3
    d = p * p - 4
    j = jacobi(d, n)
    while j == 1:
        p = p + 1
        d = p * p - 4
        j = jacobi(d, n)

    if j == 0:
        return False

    if pow(d, n // 2, n) != n - 1:
        return False

    a = pairpow((p, 1), (n + 1) // 2, d, n)

    if a[1] != 0:
        return False
    if a[0] != 2 and a[0] != n - 2:
        return False
    return True
    

for i in range (1,3999,2):
    if (isprime(pow(2,1024)+i)):
        print(i)
Ищем простые от 2^1024 - нашлись 2^1024 + (643, 1081, 2113, 2715, 3711)
3 окт 19, 20:12    [21986247]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Barlone
пропущено...
Разобрался. Небольшая неточность, которая не влияет на результат проверки. Неканонично получилось, результат возведения в степень поделен пополам, но и сравнивается с единицей, а не с 2. Вобщем, можно не исправлять.
Да, а вот с квадратным корнем надо что-то сделать. 2^1023 еще лезет, а 2^1024 говорит "OverflowError: int too large to convert to float"
У меня то же самое.

Либо без корня (я не использую корень на больших числах), либо "делить" на части и перемножать.
3 окт 19, 20:45    [21986274]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Ищем простые от 2^1024 - нашлись 2^1024 + (643, 1081, 2113, 2715, 3711)
Ещё 5335, 5793, 5947, 7015, 7447, 7935, 8953, 8995, 9855.

1 мин. 48 сек.
3 окт 19, 20:50    [21986276]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
Ищем простые от 2^1024 - нашлись 2^1024 + (643, 1081, 2113, 2715, 3711)
Ещё 5335, 5793, 5947, 7015, 7447, 7935, 8953, 8995, 9855.

1 мин. 48 сек.
У меня секунд за 15 те же.
3 окт 19, 21:19    [21986280]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Наконец послушали специалиста. Вы уж там разбирайтесь, но так скоропалительно, а то быстро 30 страниц набежит типа "о-опс, ошибка", "блин, снова ошибся", "ёлы-палы, поспешил" ... ну вы помните. И мой вопрос затеряется, и никто не ответит((

А вопрос у меня сбоку от ваших проблем. Почему остановились на 2^2k ? и диапазон 100тыс хиленький.

Мог бы кто-нибудь найти кол-во простых в след-х дипаз-х (для сравнения с оценкой, к-рую я давал 2-3 дня назад):
2^p	диапазон	оценка
50	1000000	28021,35
100	1000000	14218,81
2048	200000	140,79
4096	500000	176,05
4096	1000000	352,10
8192	500000	88,04
8192	1000000	176,08
Попутно интересно отработать модные теперь эвристики для погрешности оценки. Это чтобы не вычислять типа 1/(Ln x - 2) для больших x и т.п.

Интересно посмотреть насколько относительная погрешность апроксимируется величиной sqrt(1/f(x)), где f(x) есть кол-во простых в диапазоне. И тогда абсолютная погрешность sqrt(f(x)).
Вообще я догадываюсь, что далеко не всегда так будет, но на нашем скудном материале даже различие 70 и 79 примерно на границе такой погрешности (прикидывал на бумажке, без калькулятора).
А тоя смотрю, как после p=1024 относит-я погр-ть скакнула в 1000 раз для p=2K(2024)

Ну и сами диапазоны в будущем хочется подлиннее.
3 окт 19, 21:27    [21986281]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
exp98, чтобы такие диапазоны обсчитывать, надо бы с питона на что-то более быстрое перейти.
4 окт 19, 05:14    [21986369]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Gennadiy Usov
Ещё 5335, 5793, 5947, 7015, 7447, 7935, 8953, 8995, 9855.
1 мин. 48 сек.
У меня секунд за 15 те же.
С предварительным делением на малые множители или нет?

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

Откуда:
Сообщений: 1842
exp98
Наконец послушали специалиста.
Почему остановились на 2^2k ? и диапазон 100тыс хиленький.
Попутно интересно отработать модные теперь эвристики для погрешности оценки. Это чтобы не вычислять типа 1/(Ln x - 2) для больших x и т.п.
Интересно посмотреть насколько относительная погрешность апроксимируется величиной sqrt(1/f(x)), где f(x) есть кол-во простых в диапазоне. И тогда абсолютная погрешность sqrt(f(x)).
Вообще я догадываюсь, что далеко не всегда так будет, но на нашем скудном материале даже различие 70 и 79 примерно на границе такой погрешности (прикидывал на бумажке, без калькулятора).
А тоя смотрю, как после p=1024 относит-я погр-ть скакнула в 1000 раз для p=2K(2024)
Ну и сами диапазоны в будущем хочется подлиннее.
Что нам даёт погрешность от "специалиста"?

Вот и sqrt после p=1024 не работает, и "скакнула" скорость после p=1024.
И всё.

Есть формула количества, а есть расчёты.
Уточняем формулу или уточняем расчёты?

У одного 70, у другого 79, а что у "специалиста" - неизвестно.
И что это даёт?
Наверное не формулу, а что-то другое
4 окт 19, 06:28    [21986380]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
exp98, чтобы такие диапазоны обсчитывать, надо бы с питона на что-то более быстрое перейти.
Обсчитали, и что это даст?

Будем прыгать и радоваться, что посчитали около 2^(какое-то)?
Кого сейчас этим удивишь, когда существуют мощные компьютеры.

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

Чтобы сравнивать алгоритмы, надо считать не время, а считать раунды.

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

Раунды не зависят ни от языка, ни от ПК.
4 окт 19, 06:39    [21986381]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

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

Почти правильно. Я добавлю что надо считать не время а некие элементарные мат-операции
которые надо выполнить чтобы достичь результата. И оценить как эти операции растут
от объема данных.

Обычно - нелинейно. И есть также заблуждение о том что умножение занимает единицу времени.
Для длинных целых чисел умножений зависит квадратично от разрядной сетки числа.
Это тоже надо учитывать. Как - не знаю но надо.

Если всё правильно оценить - получим асимптоматику.
4 окт 19, 11:16    [21986538]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9508
Gennadiy Usov
Чтобы сравнивать алгоритмы, надо считать не время, а считать раунды.
"Сколько времени придётся ждать?" - это я понимаю.
"Сколько раундов будет сделано?" - не понимаю, да и какая мне разница???
4 окт 19, 11:22    [21986543]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Gennadiy Usov
Что нам даёт погрешность от "специалиста"? ... Уточняем формулу или уточняем расчёты?
Вам - ничего, мне - удовольствие.
Каждый косит свой газон. Да вы и свои рассчёты не торопились ещё недавно уточнять, что изменилось вдруг?

Не принц, конечно, но что есть,то есть, за сколько мне вам отдаться?
4 окт 19, 11:44    [21986576]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Basil A. Sidorov, я не вдаюсь в подробности, видимо это некая агрегированная прмежуточная величина алгоритма. Возможно пропорциональная вычислительной сложности этого модуля. Щас речь не о пользователях.
4 окт 19, 11:47    [21986583]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Basil A. Sidorov
Gennadiy Usov
Чтобы сравнивать алгоритмы, надо считать не время, а считать раунды.
"Сколько времени придётся ждать?" - это я понимаю.
"Сколько раундов будет сделано?" - не понимаю, да и какая мне разница???
Почитайте про тест Миллера-Рабина
https://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина
Там всё написано про раунды.

Главная трудность работы тестов простоты - это количество раундов.
Этим количеством увеличивают вероятность получения нужного числа случайным образом.
4 окт 19, 15:06    [21986817]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Basil A. Sidorov
Member

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

Откуда:
Сообщений: 1842
А вот интересная задача (по поводу определения раундов)

import math
a1= math.sqrt(1000000000000000000000001)//1
a2 = math.sqrt(1000000000000000000000000000000000000000000001)//1
print (a1, a2)

И печать результатов:

(1000000000000.0, 3.1622776601683792e+22)

Вот почему одно число целое, а другое число вещественное?
4 окт 19, 15:59    [21986879]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Что-то у меня на диапазоне 200000 с 22048 нашлось 151 число. Черт возьми, надо было их вывести, а не просто посчитать.
4 окт 19, 16:09    [21986889]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
А вот интересная задача (по поводу определения раундов)

import math
a1= math.sqrt(1000000000000000000000001)//1
a2 = math.sqrt(1000000000000000000000000000000000000000000001)//1
print (a1, a2)

И печать результатов:

(1000000000000.0, 3.1622776601683792e+22)

Вот почему одно число целое, а другое число вещественное?
А черт его знает, надо в исходники питона смотреть.
Вот вам целочисленный корень:
def intsqrt(n):
    q = n.bit_length()
    if q <= 129:
        m = int(math.sqrt(n))
    else:
        k = (q - 128) >> 1
        m = int(math.sqrt(n >> (2*k))) << k
    k = (m + n // m) >> 1
    while k != m:
        m, k = k, (m + n // m) >> 1
    return k    
4 окт 19, 16:12    [21986893]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Спасибо!

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

Откуда:
Сообщений: 1348
Gennadiy Usov
А вот интересная задача (по поводу определения раундов)

import math
a1= math.sqrt(1000000000000000000000001)//1
a2 = math.sqrt(1000000000000000000000000000000000000000000001)//1
print (a1, a2)

И печать результатов:

(1000000000000.0, 3.1622776601683792e+22)

Вот почему одно число целое, а другое число вещественное?
А вообще-то первое тоже вещественное - там же в конце ".0".
Просто во втором нечетное количество ноликов, и в 52 бита (точность мантиссы в double) оно не лезет, поэтому в экспоненциальной форме
4 окт 19, 16:25    [21986907]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Barlone
Что-то у меня на диапазоне 200000 с 22048 нашлось 151 число. Черт возьми, надо было их вывести, а не просто посчитать.
Перепроверил, на 60 раундов Соловея-Штрассена, все простые:
+
22048+...
(981,1617,3063,3211,4143,7405,9843,10665,10725,11097,11467,13137,13333,15703,17001,
17787,18523,21397,24963,25405,26697,26935,30475,31627,34005,34431,35281,35763,36535,
37653,38841,39825,42637,43965,44281,45303,46303,46995,49957,54613,54873,57325,62847,
65377,65545,67701,67953,68415,68535,68941,69493,69543,72207,75775,76413,76647,77797,
78003,81081,81093,81795,83335,83593,84397,84463,89023,89835,89965,90127,90147,90993,
93795,94593,97455,97707,98077,99867,99945,100431,105435,107025,107385,107851,109197,
111343,115911,115941,116667,117601,123327,124381,125523,129051,130453,130551,130773,
131203,131301,131877,132915,133221,133651,134085,135751,135771,136383,136711,137443,
141901,147783,148455,150997,152751,153097,153817,155013,155191,156027,156057,157543,
160747,162385,162747,162891,164191,166843,167001,172603,173373,174157,175503,176563,
180081,182811,183397,184021,184167,186235,187017,187803,192091,192883,193107,193635,
193831,194205,195321,196261,197587,198213,199425)
4 окт 19, 18:11    [21987027]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Надо базу вести. Типа "Простые числа по версии Соловея-Штрассена". Потом еще базу. Простые по версии Усова.
4 окт 19, 18:14    [21987034]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Прогнал через свой вариант теста все числа до 232. Количество найденных простых совпало с количеством простых, полученных решетом. Также сравнил список до 224. Ничего лишнего, ничего не пропущено.
5 окт 19, 07:06    [21987246]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Попробовал перейти на раунды.
Пусть раунд - это обращение к основной формуле: pow(a1, t2, p).
Все остальные операторы не так затратны по времени, особенно для больших чисел.
Тогда:

-проверка чисел от- 5 -до - 1000005
-количество простых чисел- 78497
-количество раундов - 3482972
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 421362
-максимальное количество раундов для числа - 39
5 окт 19, 11:19    [21987284]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Далее, ещё интереснее.

Пусть ограничитель для проверки числа 39 раундов.
Для чисел после 2**1024-1 в количестве 10000 получается следующая картинка:

2019-10-05-12.59.02
-количество простых чисел- 14
-количество раундов - 1733
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 1185
-максимальное количество раундов для числа - 39
-количество максимальных раундов - 546
-остаток- 2
2019-10-05-12.59.27

То есть, программа либо сразу сообщает, что число составное, либо все 39 раундов для простого числа.
И всего 2 раунда на более сложную проверку.
5 окт 19, 13:11    [21987307]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Небольшое уточнение.

В предыдущем сообщении представлена распечатка работы программы, когда имеются делители до 100.

Та же программа, в которой нет делителей, выдаёт следующий результат:

-количество простых чисел- 14
-количество раундов - 5520
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 4986
-максимальное количество раундов для числа - 38
-количество максимальных раундов - 532
-остаток- 2
5 окт 19, 20:26    [21987422]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Интересно. Во главе угла криптографии стоит операция деления. как некий бастион
который ограничивает перформанс криптоанализа. Что-бы мы не делали а эта
операция в стеке - принципиально не оптимизируема. Я думал о машинной реализации.
Судя по описаниям она принципиально не отличается от классического деления в столбик
с той разницей что работает двоичная логика вычитаний. И я подумал - а какую собсвенно
пользу можно извлечь из результата деления. В классическом варианте любая операция
машинного деления на самом деле делает больше. Она фиксирует остаток. Кроме
того если мы используем делители достаточно длинные по разрядной сетке но имеющие
вид последовательности простых то делители не будут сильно отличаться. Фактически
от шага к шагу меняются младшие разряды делителя.
5 окт 19, 22:10    [21987462]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Ещё пример работы программы:

Пусть ограничитель для проверки числа 39 раундов.
Для чисел после 2**2048-1 в количестве 10000 получается следующая картинка:

-количество простых чисел- 7
-количество раундов - 5261
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 4993
-максимальное количество раундов для числа - 38
-количество максимальных раундов - 266
-остаток- 2
6 окт 19, 06:26    [21987527]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Далеко не для каждого составного числа найдется "свидетель простоты" по Рабину-Миллеру, то есть основание, по которому это число будет псевдопростым. На самом деле, такие составные числа, для которых существует хотя бы один свидетель простоты, довольно редки. Но уж если один свидетель простоты существует для некоего составного числа, то их (свидетелей) для этого числа обязательно будет несколько: все они будут корнями какой-то степени из единицы по модулю одного из делителей этого составного числа. Вот именно потому, что свидетели простоты по Миллеру-Рабину всегда появляются пачками, выгоднее не гонять кучу раундов, а использовать другой, независимый тест Люка, который опирается не на мультипликативную группу вычетов, а на другую группу.
6 окт 19, 17:59    [21987680]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Далеко не для каждого составного числа найдется "свидетель простоты" по Рабину-Миллеру, то есть основание, по которому это число будет псевдопростым. На самом деле, такие составные числа, для которых существует хотя бы один свидетель простоты, довольно редки. Но уж если один свидетель простоты существует для некоего составного числа, то их (свидетелей) для этого числа обязательно будет несколько: все они будут корнями какой-то степени из единицы по модулю одного из делителей этого составного числа. Вот именно потому, что свидетели простоты по Миллеру-Рабину всегда появляются пачками, выгоднее не гонять кучу раундов, а использовать другой, независимый тест Люка, который опирается не на мультипликативную группу вычетов, а на другую группу.
Тест Люка тоже выполняет серию раундов (основание степени, степень, модуль).
Почему нельзя посчитать количество этих раундов для различных чисел?

Тест Люка вероятностный, следовательно, получаются псевдопростые числа.
6 окт 19, 18:15    [21987688]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Конечно тест Люка вероятностный. Я вообще не про то.
Вот есть списки сильных псевдопростых чисел по разным основаниям. Так вот, далеко не каждое число попадет хотя бы в один такой список. Ну то есть, можно перебрать например все составные нечетные числа n от 15 до 9999, и для каждого перебрать все основания от 2 до n-2 и провести тест Миллера-Рабина. Получить список составных чисел, являющихся псевдопростыми хотя бы по одному основанию.
Потом получить аналогичный список для теста Люка - то есть провести тест по всем вариантам параметров, которые могут использоваться для этого теста, и выписать псевдопростые по Люка хотя бы по одному варианту параметров.
А потом проверить, есть ли в этих двух списках совпадения.
6 окт 19, 19:49    [21987722]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Конечно тест Люка вероятностный. Я вообще не про то.
...
можно перебрать например все составные нечетные числа n от 15 до 9999, и для каждого перебрать все основания от 2 до n-2 и провести тест Миллера-Рабина. Получить список составных чисел, являющихся псевдопростыми хотя бы по одному основанию.
Потом получить аналогичный список для теста Люка - то есть провести тест по всем вариантам параметров, которые могут использоваться для этого теста, и выписать псевдопростые по Люка хотя бы по одному варианту параметров.
А потом проверить, есть ли в этих двух списках совпадения.
Есть два варианта: совпадают и не совпадают.
А что дальше?

Надо говорить об этом.
6 окт 19, 20:00    [21987727]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
Конечно тест Люка вероятностный. Я вообще не про то.
...
можно перебрать например все составные нечетные числа n от 15 до 9999, и для каждого перебрать все основания от 2 до n-2 и провести тест Миллера-Рабина. Получить список составных чисел, являющихся псевдопростыми хотя бы по одному основанию.
Потом получить аналогичный список для теста Люка - то есть провести тест по всем вариантам параметров, которые могут использоваться для этого теста, и выписать псевдопростые по Люка хотя бы по одному варианту параметров.
А потом проверить, есть ли в этих двух списках совпадения.
Есть два варианта: совпадают и не совпадают.
А что дальше?

Надо говорить об этом.
Есть гипотеза, что совпадений не будет.
6 окт 19, 20:44    [21987764]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Gennadiy Usov
Есть два варианта: совпадают и не совпадают.
А что дальше?
Надо говорить об этом.
Есть гипотеза, что совпадений не будет.
Кто бы сомневался.

Если не совпадает, то что делать?
6 окт 19, 20:57    [21987772]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Barlone
Что-то у меня на диапазоне 200000 с 22048 нашлось 151 число.
А ты мне отвечал, что долго считать. За это личное спасибо.
Может всё же сочтёшь кол-во персонально для меня ещё диапазончик
2^4096 +500000, предварительная оценка [ 176,05 + - 13,268 ] ??
Вроде не намного и дольше считать, раз в 5-6 ... я думаю. Мне только кол-во.
9 окт 19, 14:53    [21990502]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Gennadiy Usov, я несколько раз обращался к тебе с просьбой собрать отклик твоего кода через равные
промежутки интервалов. Я хотел построить график. И по нему оценить асимптоматику. Это важно.
Важные даже не числа а форма графика. Парабола. Экспонента. Или x в степени x как некая ссылка
на комбинаторную сложность. Но мне показалось что данные у тебя беспорядочны и их мало и я отбросил
эту затею.
Насколько я помню, последними таблицами были 21976531 и 21982245.
В последнем сообщении была фраза:
mayton
Добавил 100 тысяч на диапазоне 2048 бит.
Вот данные для проверки. Две таблички надо соединить. Но уже поздно. Я засыпаю.
А далее -
mayton
Я говорю табличку заполните.
В табличках есть параметры:
диапазон, количество простых чисел и время работы программы на диапазоне.

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

Откуда:
Сообщений: 1842
Barlone
Gennadiy Usov
Barlone
Ищем простые от 2^1024 - нашлись 2^1024 + (643, 1081, 2113, 2715, 3711)
Ещё 5335, 5793, 5947, 7015, 7447, 7935, 8953, 8995, 9855.
1 мин. 48 сек.
У меня секунд за 15 те же.
На каждом ПК и на каждом языке программирования свои скорости.

В работе 22011445 рассматривался эвристический алгоритм для определения простых чисел в окрестности чисел Mn = 2^n – 1.

Кроме того, была проведена оценка размера таких окрестностей
с точки зрения отсутствия возможности получения составных чисел при работе эвристического алгоритма.
Поэтому для чисел 2^1024-1 и 2^2048-1 размер такой окрестности будет составлять намного больше, чем 10000 чисел.
Следовательно, в этой окрестности при рассмотрении очередного числа достаточно одно вычисление вида «pow».
Допустим, это "рабочий диапазон".

Для чисел 2^1024-1 и 2^2048-1 рабочий диапазон имеет место как со знаком +, так и со знаком -.

Исследования на ПК для диапазона из 10000 чисел показали, что:
для знака + эвристический алгоритм работает на 4% медленнее оператора pow.
для знака - эвристический алгоритм работает на 3% быстрее оператора pow.

Вне рабочего диапазона (например, очень далеко от чисел 2^1024-1 и 2^2048-1), по всей видимости,
необходимо несколько проверок вида «pow».
13 ноя 19, 16:40    [22015600]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Gennadiy Usov
Следовательно, в этой окрестности при рассмотрении очередного числа достаточно одно вычисление вида «pow».
Допустим, это "рабочий диапазон".
...
Вне рабочего диапазона (например, очень далеко от чисел 2^1024-1 и 2^2048-1), по всей видимости,
необходимо несколько проверок вида «pow».
Конечно, необходимо заметить, что исследования проводились для "pow(3,", или для pow3.

Поэтому, если нужно быстро найти простые числа, то можно их найти в так называемом "рабочем диапазоне" от числа Мерсенна.
И для этого достаточно одно обращение к pow3.

Вне "рабочего диапазона" потребуется уже несколько обращений к pow3,
или несколько обращений к операторам pow с другим основанием степени.

При этом напоминаю, что для чисел Mnk, у которых k кратно 4, "рабочий диапазон" будет намного больше,
чем для остальных чисел Mnk.
16 ноя 19, 09:42    [22017831]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Прошу тебя, друг Аркадий Геннадий, не говори красиво!(цэ):
Gennadiy Usov
Кроме того, была проведена оценка размера таких окрестностей с точки зрения отсутствия возможности получения составных чисел при работе эвристического алгоритма.

Почти ничего не понял в ваших словах, но благодаря следущей строчке:
Gennadiy Usov
Поэтому для чисел 2^1024-1 и 2^2048-1 размер такой окрестности будет составлять намного больше, чем 10000 чисел.
решил прикинуть по науке. Фразу "отсутствия возможности получения составных" интерпретировал как диапазон, гарантирующий (с хорошей долей вероятности) наличие хоть 1 простого. Оценивал на бумажке. Почему-то у меня не получается "намного больше, чем 10000".
Наоборот, если исходить из прикида, что на дальности 1млн от 2^2K кол-во простых можно оценить как наиболее вероятный интервал 72тыс +- 268, то тогда уже на дальности 3620 весьма вероятно 1 простое. А на дальности 10тыс их весьма вероятно 5.
Соответственно, ведя отсчёт от 2^K, в 10тыс поместится простых 11-12 штук.
Кстати другим способом на дальности 10тыс от 2^K их оценивается 14.4 +- 4.
К сож, теорвер не позволяет мне оценить точнее малые кол-ва (точнее конечно будет не на бумажке).

Я это всё к тому, что как-то не понятна фраза про "намного больше, чем 10000".
17 ноя 19, 00:09    [22018018]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
exp98
Фразу "отсутствия возможности получения составных" интерпретировал как диапазон, гарантирующий (с хорошей долей вероятности) наличие хоть 1 простого. Оценивал на бумажке. Почему-то у меня не получается "намного больше, чем 10000".
Рабочий диапазон есть диапазон чисел,
где эвристический алгоритм определяет сколько угодно чисел, которые будут простыми числами,
причём ни одно из определённых чисел не будет составным числом.
17 ноя 19, 07:52    [22018063]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
автор
Рабочий диапазон есть диапазон чисел, где эвристический алгоритм определяет сколько угодно чисел, которые будут простыми числами, причём ни одно из определённых чисел не будет составным числом.
Видите, даже попытка разъяснить боле-мене конкретный вопрос, всё равно приводит к двусмысленности.
Писать по-русски ведь тоже ещё уметь надо. Тем более технический текст. Обычно почему-то полагается, что читатель проделал к этому моменту тот же самый мыслительный путь, и важно, что остановился на том же самом месте, что и писатель.
И тогда целиком воспроизводится ситуация анекдота: "Да пошла ты наф со своим утюгом!"

Однако практически всегда это не так. Но такой писатель никогда не оценивает со стороны, как писанина будет воспринята. Это не только ваша особенность, большинство прогеров так же пишут.
То же самое относится к вашей самооценке правильности собственной программы, сам сделал, сам написал и ку-ка-ре-ку. А вы все верьте.

Я уже не говорю о спец. подборе слов для выражения мысли ... Как же меня задрали за всю жизнь эти "постановщики задач", приходят и начаинают с "прерваного места". И вы ещё тут ... вот почти и не читаю, но только прочту, блин ... А попытка одной фразой ответиь на неск. вопросов ?..

Вашу двусмысленность наверное (я лищь предполагаю) можно было бы ликвидировать. Но "сколько угодно чисел", да ещё "которые будут простыми" ... наверное это бесконечность, да? впихнутая в конечный диапазон!

Как вариант: РД есть диапазон чисел, в к-ром ЭАGUОПЧ безошибочно определяет любое составное число как составное.

И всё равно остаётся необъяснённым вопрос, не пропускает ли ЭА при этом ПЧ, ошибочно принимая их за составное? (о том, что некто некогда как-то где-то это проверял, я наслышан)
17 ноя 19, 17:36    [22018253]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
exp98
автор
Рабочий диапазон есть диапазон чисел, где эвристический алгоритм определяет сколько угодно чисел, которые будут простыми числами, причём ни одно из определённых чисел не будет составным числом.
Как вариант: РД есть диапазон чисел, в к-ром ЭАGUОПЧ (других эвристических алгоритмов пока нет)
безошибочно определяет любое составное число как составное.
Наверное, так будет проще для читателя.

Хотя, любой тест простоты определяет простоту чисел,
то есть, "отсекает" составные числа.
exp98
И всё равно остаётся необъяснённым вопрос, не пропускает ли ЭА при этом ПЧ, ошибочно принимая их за составное? (о том, что некто некогда как-то где-то это проверял, я наслышан)
А всё очень просто. Перебор делителей.
Поэтому на моём ПК получается проверить только до 2^32-1 +k.

А дальше - эвристика... Хотите верьте, хотите нет.
17 ноя 19, 18:18    [22018259]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
exp98
автор
Рабочий диапазон есть диапазон чисел, где эвристический алгоритм определяет сколько угодно чисел, которые будут простыми числами, причём ни одно из определённых чисел не будет составным числом.
Видите, даже попытка разъяснить боле-мене конкретный вопрос, всё равно приводит к двусмысленности.
Писать по-русски ведь тоже ещё уметь надо. Тем более технический текст. Обычно почему-то полагается, что читатель проделал к этому моменту тот же самый мыслительный путь, и важно, что остановился на том же самом месте, что и писатель.
И тогда целиком воспроизводится ситуация анекдота: "Да пошла ты наф со своим утюгом!"

Я не знал этот анекдот. Погуглил. Шикарно.

Точно-точно отражает ситуацию.

Я-бы подарил Геннадию четырехтомник Дональда Кнута. Не знаю. Так просто. Мне кажется что стиль изложения
очень похож на топик. Не помню касался он простых чисел или нет но по алгоритмизации там дофига чего есть.
И по анализу complexity.
17 ноя 19, 19:13    [22018274]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
https://pikabu.ru/story/fiziki_shutyat_6033520
18 ноя 19, 06:30    [22018401]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
https://pikabu.ru/story/fiziki_shutyat_6033520
Осталось добавить сюда, так ведь эвристика, и теорему Ферма.
18 ноя 19, 06:46    [22018403]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
В сообщении 22015600 говорится о наличии в окрестности 2^n "рабочих диапазонов" чисел,
при проверки которых на простоту достаточно одного вычисления оператора pow3.

Было интересно узнать, а есть ли ещё такие "рабочие диапазоны"?

Оказалось, что есть.

Исследования показали, что "рабочие диапазоны" имеют место вокруг чисел вида:

2^n +- 2^(n-1) +- 2^(n-2) +- 2^(n-3) +- 2^(n-4) +-...
вчера, 11:32    [22019448]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Gennadiy Usov
...Исследования показали, что "рабочие диапазоны" имеют место вокруг чисел вида:
2^n +- 2^(n-1) +- 2^(n-2) +- 2^(n-3) +- 2^(n-4) +-...
Кто-нибудь в курсе, что в случае "+" эта сумма == 2^(n+1) - 1 ? а в случае "-" == 2^n - (2^n - 1)
Или я опять не так понял?
сегодня, 14:15    [22020648]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1848
Gennadiy Usov
Поэтому на моём ПК получается проверить только до 2^32-1 +k. А дальше - эвристика... Хотите верьте, хотите нет.
1)А разве в статье по ссылке выше написано, что проверено только до 2^32-1 +k ?
2) Науку совершенно не колышит, каким путём проверять? Казалось бы, Ф. такой весь был авторитет из себя, даже свою Большую теорему "доказал"(набросал) на полях книги (к-рую непредусмотрительно потом вернул в библиотеку). Нет, вишь ты, надо было добрую сотню-другую лет её потом всем кагалом доказывать, чтобы убедиться. Да и то лишь при помощи компа прикончили.
Тогда кажется автор тоже оповестил, что доказал. Но ... пришлось исправлять. Правда там речь о строгом доказательстве, ну так ведь он и не прятал свою программу, наоборот - отдал на проверку.
сегодня, 14:33    [22020682]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
exp98
Gennadiy Usov
...Исследования показали, что "рабочие диапазоны" имеют место вокруг чисел вида:
2^n +- 2^(n-1) +- 2^(n-2) +- 2^(n-3) +- 2^(n-4) +-...
Кто-нибудь в курсе, что в случае "+" эта сумма == 2^(n+1) - 1 ? а в случае "-" == 2^n - (2^n - 1)
Или я опять не так понял?
Например:
2^n + 2^(n-1) = 3 * 2^(n-1)
2^n + 2^(n-1) + 2^(n-2) = 7 * 2^(n-2)
2^n + 2^(n-1) - 2^(n-2) = 5 * 2^(n-2)
2^n + 2^(n-1) + 2^(n-2) + 2^(n-3) = 15 * 2^(n-3)
2^n + 2^(n-1) - 2^(n-2) + 2^(n-3) = 11 * 2^(n-3)
и т.д.
получаются числа вида k * 2^n
сегодня, 14:57    [22020745]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
exp98
Gennadiy Usov
Поэтому на моём ПК получается проверить только до 2^32-1 +k. А дальше - эвристика... Хотите верьте, хотите нет.
1)А разве в статье по ссылке выше написано, что проверено только до 2^32-1 +k ?
В статье по ссылке говорилось об одной ветви: 2^n-1 +k.
А в настоящее время проверяется несколько веток : m * 2^n-1 +k
exp98
2) Науку совершенно не колышит, каким путём проверять? Казалось бы, Ф. такой весь был авторитет из себя, даже свою Большую теорему "доказал"(набросал) на полях книги (к-рую непредусмотрительно потом вернул в библиотеку). Нет, вишь ты, надо было добрую сотню-другую лет её потом всем кагалом доказывать, чтобы убедиться. Да и то лишь при помощи компа прикончили.
Тогда кажется автор тоже оповестил, что доказал. Но ... пришлось исправлять. Правда там речь о строгом доказательстве, ну так ведь он и не прятал свою программу, наоборот - отдал на проверку.
И здесь отдано на проверку ...,
если есть интерес
сегодня, 15:12    [22020789]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4 5 6 7 8 9 10      [все]
Все форумы / Программирование Ответить