Новый тест проверки чисел на простоту

[reco reco]

$F_n=\frac{(1+\sqrt 5 )^n-(1-\sqrt 5)^n}{\sqrt 5}$

первый этап теста:
для чисел оканчивающихся на 3 и 7
Fn mod n = n-1
F(n+1) mod n = 0

для чисел оканчивающихся на 1 и 9
Fn mod n = 1
F(n-1) mod n = 0

второй этап теста:
(2^n) mod n = 2

если число прошло два этапа теста, то оно псевдопростое

среди чисел меньших миллиона всего 7 составных чисел, которые данный тест определяет как простые

интересно, что среди чисел, псевдопростых по этому тесту, меньших миллиона, 4 одновременно являются числами Кармайкла (252601=41*61*101, 399001=31*61*211, 512461=31*61*271, 852841=11*31*41*61)

[reco reco]

для чисел n, естественно

[worm2]

Вероятно, это какая-то вариация псевдопростых чисел Люка.
У нас на форуме что-то похожее тоже рассматривалось. Я там даже те же числа Кармайкла привёл.

[reco reco]

worm2 в сообщении #1646624 писал(а):

У нас на форуме что-то похожее тоже рассматривалось.

Здравствуйте! Так это я и был. Просто сейчас усовершенствовал тест

[Andrey A]

reco reco в сообщении #1646611 писал(а):

для чисел оканчивающихся на 3 и 7
Fn mod n = n-1
F(n+1) mod n = 0

для чисел оканчивающихся на 1 и 9
Fn mod n = 1
F(n-1) mod n = 0

В чем тут новизна? Эти закономерности, если не ошибаюсь, приведены хотя бы в брошюре Н.Н.Воробьева "Числа Фибоначчи".

reco reco в сообщении #1646611 писал(а):

среди чисел меньших миллиона всего 7 составных чисел, которые данный тест определяет как простые

Не могли бы Вы их перечислить? Интересно опробовать на них алгоритм дискретного логарифмирования по точке золотого сечения.

[reco reco]

Andrey A в сообщении #1646646
В чем тут новизна? Эти закономерности, если не ошибаюсь, приведены хотя бы в брошюре Н.Н.Воробьева "Числа Фибоначчи"

У Воробьёва не нашел


Andrey A в сообщении #1646646
Не могли бы Вы их перечислить? Интересно опробовать на них алгоритм дискретного логарифмирования по точке золотого сечения

Досчиталось уже почти до двух миллионов

Вот составные числа, которые тест определил как простые
Интересно, что у всех этих чисел, кроме одного, делители оканчиваются на 1

219781 271*811

252601 41*61*101

399001 31*61*211

512461 31*61*271

722261 491*1471

741751 431*1721

852841 11*31*41*61

1024651 19*199*271

1193221 31*61*631

1533601 31*61*811

1690501 751*2251

1735841 761*2281

1857241 31*181*331

1909001 41*101*461

[Dmitriy40]

reco reco в сообщении #1646611 писал(а):

второй этап теста:
(2^n) mod n = 2

Как понимаю это переформулировка малой теоремы Ферма об простоте чисел по основанию 2 (числа Пуле). Для них в сети есть полный список всех исключений до $2^{64}\approx1.84\cdot10^{19}$, все остальные составные им определяются правильно, потому нет нужды проверять все числа подряд, достаточно проверить только эти 119млн чисел по первому критерию. До $10^{12}$ список из сотни тысяч чисел есть и в A001567 (а среди ссылок есть и первый список), тоже достаточно проверить лишь их по первому критерию.

-- 18.07.2024, 15:50 --

Плюс за счёт очень небольшого усложнения второго критерия (причём нередко даже с увеличением скорости проверки) можно уменьшить количество исключений почти вчетверо, с 119млн до 32млн - сильные псевдопростые и A001262 (первые 10000 штук). И их тоже есть полный список исключений до $2^{64}\approx 1.84\cdot10^{19}$, только которые и достаточно проверить по первому критерию.

-- 18.07.2024, 15:53 --

А первый критерий очень похож на псевдопростые Фибоначчи.

Так что ничего нового похоже в таком тесте нет.

[reco reco]

А первый критерий очень похож на псевдопростые Фибоначчи.

Так что ничего нового похоже в таком тесте нет.


Псевдопростое Фибоначчи — это составное число n для которого...

Всё-таки в моём тесте подавляющее число чисел соответствующих первому критерию - простые числа. Не составные.


-- 18.07.2024, 17:30 --

Плюс за счёт очень небольшого усложнения второго критерия (причём нередко даже с увеличением скорости проверки) можно уменьшить количество исключений почти вчетверо, с 119млн до 32млн

А какое именно усложнение второго критерия Вы имеете ввиду? Можете формулу дать? Буду весьма признателен

[Andrey A]

reco reco в сообщении #1646651 писал(а):

Интересно, что у всех этих чисел, кроме одного, делители оканчиваются на 1

219781 271*811

.......................

Интересно, что здесь уже их больше семи, и взяты только с единицей на конце. Ведь есть и другие?

Дискретное логарифмирование оказывается нерезультативно, когда составное $m$ имет $2$ простых множителя $m=ab$ и $F_{\min}(m)=F_{\min}(a)=F_{\min}(b).$ Таково $m=219781=271\cdot 811.$ Тут $F_{\min}(219781)=F_{\min}(271)=F_{\min}(811)=F_{270}.$
Но уже для $F_{\min}(1735841)=F_{380}$ один из множителей имеет меньшее $F_{\min}.$ Делим $380/2=190$ и $\gcd(1735841,F_{190})=761,$ выводя таким образом квазипростое на чистую воду. Ну, а если множителей больше двух, то и подавно.

[Dmitriy40]

reco reco в сообщении #1646669 писал(а):

А какое именно усложнение второго критерия Вы имеете ввиду? Можете формулу дать? Буду весьма признателен

Я же дал ссылки и на псевдопростое Ферма, и на сильное псевдопростое (усиление условия), и там и там есть формулы, в первом случае формула $a^{p-1}=1\pmod p$, во втором случае $p=d\cdot2^s+1,\; a^d=1\pmod p \vee a^{d\cdot2^r}=-1\pmod p, 0\le r<s$ ($d$ нечётное), с частным случаем $a=2$.

[reco reco]

Интересно, что здесь уже их больше семи, и взяты только с единицей на конце. Ведь есть и другие?

Больше семи, потому что комп просчитал уже почти до двух миллионов. Семь было, когда просчитано было до миллиона. Да, все они оканчиваются на единицу. И простые делители у всех псевдопростых, кроме одного, заканчиваются на единицу. Просчитаю до трёх миллионов и посмотрю - будут ли псевдопростые оканчивающиеся не на единицу

[Ende]

reco reco
Чтобы процитировать нужный фрагмент сообщения, выделите его мышкой и нажмите кнопку "Вставка" под этим сообщением.