Поиск простых чисел

[yk2ru]

Аналог теста Люка-Лемера для чисел вида $Q_n=\frac{3^n-1}{2}$
$(S_n} - A) \mod {Q_n} = 0$ где $S_1 = 2$ и $S_{k+1} = S_k(5S_k^2-3)$
$A = 1$ для $n = 4m + 3$ и $A = 2$ для $n = 4m + 1$
Не скажу, что на 100 процентов тест правильный, но вроде бы для первых 10 чисел n всевдопростых нет.
Вот эти числа $n: 3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177$
Далее не пробовал, так как мой комп не настолько мощный.

[maxal]

yk2ru в сообщении #570788 писал(а):

Аналог теста Люка-Лемера для чисел вида $Q_n=\frac{3^n-1}{2}$
$(S_n} - A) \mod {Q_n} = 0$ где $S_1 = 2$ и $S_{k+1} = S_k(5S_k^2-3)$
$A = 1$ для $n = 4m + 3$ и $A = 2$ для $n = 4m + 1$
Не скажу, что на 100 процентов тест правильный, но вроде бы для первых 10 чисел n всевдопростых нет.
Вот эти числа $n: 3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177$
Далее не пробовал, так как мой комп не настолько мощный.

Другими словами, $S_k = \frac{1}{\sqrt{5}}\left( \left(\frac{\sqrt{5}+1}{2}\right)^{3^k} + \left(\frac{\sqrt{5}-1}{2}\right)^{3^k} \right)=F_{3^k}$ -- $3^k$-е число Фибоначчи.


Докажем, что если $Q_n$ простое, то $S_n \equiv \frac{3+(-1)^{\frac{n-1}{2}}}{2}\pmod{Q_n}.$

Квадратичный закон взаимности влечет, что для нечетного $n$

$$\left(\frac{5}{Q_n}\right) = (-1)^{\frac{n-1}{2}}.$$

То есть, 5 является квадратичным вычетом по модулю $Q_n$ при $n\equiv 1\pmod{4}$ и невычетом при $n\equiv 3\pmod{4}$.

Так как $Q_n$ - простое, то

$$\left(\frac{\sqrt{5}\pm 1}{2}\right)^{3^n} \equiv \left(\frac{\sqrt{5}\pm 1}{2}\right)^{2Q_n+1} \equiv \frac{\sqrt{5}\pm 1}{2}\cdot \left(\frac{3\pm\sqrt{5}}{2}\right)^{Q_n} \equiv \frac{\sqrt{5}\pm 1}{2}\cdot \frac{3\pm\sqrt{5}\cdot(-1)^{\frac{n-1}{2}}}{2} \equiv$$

$$\equiv \frac{\sqrt{5}\cdot(3+(-1)^{\frac{n-1}{2}}) \pm (3+5\cdot (-1)^{\frac{n-1}{2}})}{4} \pmod {Q_n}$$

и поэтому

$$S_n \equiv \frac{3+(-1)^{\frac{n-1}{2}}}{2}\pmod{Q_n}.$$

Ч.т.д.

Однако, в другую сторону пока непонятно, работает ли.

[yk2ru]

maxal в сообщении #571220 писал(а):

Однако, в другую сторону пока непонятно, работает ли.

Да.

[maxal]

Сомневаюсь, что оно работает в обратную сторону.
Если обобщить, то утверждение для нечетного $n$ (пусть некратного 3 и 5) выглядит так:
$m$ - простое тогда и только тогда, когда

$$F_{2m+1} \equiv \frac{3+\left(\frac{5}{m}\right)}2 \pmod{m}.$$

Для простых $n$ это действительно так, но вот для составных есть контрпримеры типа $n=77$. Впролне вероятно, что для $m$ вида $\frac{3^n-1}{2}$ тоже есть контрпримеры, только найти их сложнее.

[Руст]

maxal в сообщении #571419 писал(а):

Сомневаюсь, что оно работает в обратную сторону.
Если обобщить, то утверждение для нечетного $n$ (пусть некратного 3 и 5) выглядит так:
$m$ - простое тогда и только тогда, когда

$$F_{2m+1} \equiv \frac{3+\left(\frac{5}{m}\right)}2 \pmod{m}.$$

Для простых $n$ это действительно так, но вот для составных есть контрпримеры типа $n=77$. Впролне вероятно, что для $m$ вида $\frac{3^n-1}{2}$ тоже есть контрпримеры, только найти их сложнее.

Это слишком широкое обобщение. По видимому обобщением для чисел $\Phi_p(x)=\frac{x^p-1}{x-1}$ является

$$(x-1)U_{x^p}=x+(\frac{D}{p}),$$

где $D$ детерминант соответствующей последовательности Люка. Возможно что тест правильный. Смотрел в книге Крэндал, Померанс "Простые числа. Криптографические и вычислительные аспекты", там такого нет. Но думаю, что тамошними методами можно доказать правильность теста для такого рода чисел. Если это пройдет и для $x=-2$ получится тест для чисел $\frac{2^p+1}{3}.$

[maxal]

Руст в сообщении #571438 писал(а):

Это слишком широкое обобщение. По видимому обобщением для чисел $\Phi_p(x)=\frac{x^p-1}{x-1}$ является

$$(x-1)U_{x^p}=x+(\frac{D}{p}),$$

где $D$ детерминант соответствующей последовательности Люка. Возможно что тест правильный.

Он может быть правильным попросту в силу разреженности таких чисел (то есть, эмпирическая вероятность существования псевдопростого числа мала). И тут становится особенно не важно, чем тестировать - например, тест Ферма по основанию 2 для чисел вида $\frac{3^n-1}2$ с нечётным $n>1$ тоже, похоже, псевдопростых не дает.
Вообще что-то подобное мы уже обсуждали тут: topic15143.html

Руст в сообщении #571438 писал(а):

Если это пройдет и для $x=-2$ получится тест для чисел $\frac{2^p+1}{3}.$

$\frac{2^p+1}{3}$ - это числа Вагстафа, существование для них эффективного детерминированного теста простоты (типа Люка-Лемера) остается открытой проблемой.

[Руст]

maxal в сообщении #571537 писал(а):

Вообще что-то подобное мы уже обсуждали тут: topic15143.html

Там известный тест Фробениуса, и за нахождение контрпримера к нему обещано 620$, см. цитированную выше книгу. Здесь тест для специального вида чисел, наподобии теста Люка для чисел Мерсена.

[Droog_Andrey]

Проще всего сначала попробовать найти контрпример.

[dmd]

Простые из последовательности A086218:

Пусть $p$ - простое, и $T=3^p-2$. Тогда если выполняется $2^\frac{T-1}{4p}\equiv \pm 1 \pmod T$, то $T$ - число простое либо псевдопростое.

a086218()=
{
forprime(p=2, 3000,
 T= 3^p-2;
 s= (T-1)/p/4;
 r= Mod(2,T)^s;
 if((r==1)||(-r==1), print(p))
)
};

[yk2ru]

dmd в сообщении #581240 писал(а):

число простое либо псевдопростое.

Могу тоже дать последовательность простых вперемежку с всевдопростыми по основанию $2$:
Пусть $p_0>3$ - простое, и $p_{k+1}=\frac{2^{p_k}-2}{3} + 1$

Чтобы получить последовательность простых с всевдопростыми по простому основанию $n>2$ в числителе число $2$ следует заменить на $n$, в знаменателе заменить $3$ на $n+1$ или на $n-1$.

[vorvalm]

yk2ru в сообщении #581336 писал(а):

dmd в сообщении #581240 писал(а):

число простое либо псевдопростое.

Могу тоже дать последовательность простых вперемежку с всевдопростыми по основанию $2$:
Пусть $p_0>3$ - простое, и $p_{k+1}=\frac{2^{p_k}-2}{3} + 1$

Индексы простых чисел не совпадают с указанными в формуле. При $p_3=5,\;p_{k+1}=11.$

[megamix62]

[quote="dmd в сообщении #581240"]Простые из последовательности A086218:

У меня вопрос - А есть ли такая последовательность

$P{(k+1)}=(3*P{(k)}-1)/2$, если $P{(k+1)}$- нечетное,
$P{(k+1)}=(3*P{(k)}-1)/2+1$, если $P{(k+1)}$- четное,
где $P(k)$ простое чисел

1. $P{(1)}=2$
2. $P{(2)}=3$
3. $P{(3)}=(3*3-1)/2=4+1=5$
4. $P{(4)}=(5*3-1)/2=7$
5. $P{(5)}=(7*3-1)/2=11$....

[yk2ru]

vorvalm в сообщении #581376 писал(а):

Индексы простых чисел не совпадают с указанными в формуле.

Не понял высказывания. Получится последовательность чисел, где каждое число как минимум всевдопростое по основанию 2 (по малой теореме Ферма).
Числа: $5, 11, 683, ...$

[vorvalm]

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

[anwior]

Обнаружил последовательность, которая состоит либо из составных, либо из простых чисел.
Вероятность того, что в ней содержится хотя бы одно псевдопростое (по основанию 2) близка к 0.
Сей факт пытаюсь доказать самостоятельно. Не получится доказать, последовательность обнародую.

Я думаю, что аналога ей еще нет в интернете.