Проверка на простоту.

[ICh[USU]]

Помогите, пожалуйста, решить такую задачу:

Дано натуральное число $n=10k+7$. Верно ли, что следующие два условия эквивалентны:

1. $n$ - простое.

2. $\left(\begin{array}{cc}25 & -1 \\ 5 & 0 \end{array}\right)^{k-1}\left(\begin{array}{c}13 \\ 3\end{array}\right) = (-5)^{3k+1}\left(\begin{array}{c}1 \\ 29\end{array}\right)$, где вычисления проводятся по модулю $n$.

Я проверил на компьютере, что при $n \leqslant 10^8$ это верно.

[worm2]

Вот здесь обсуждались похожие тесты простоты.

[maxal]

Нетрудно видеть, что при $k\geq 2$:

$$\begin{pmatrix}25 & -1 \\ 5 & 0 \end{pmatrix}^{k-1}\begin{pmatrix}13 \\ 3\end{pmatrix} = \begin{pmatrix}x_k\\ 5x_{k-1}\end{pmatrix},$$

где последовательность $\{ x_k \}$ задается рекуррентным соотношением:
$x_1=13$, $x_2=322$ и $x_{k+1}=25 x_k - 5 x_{k-1}$.

Тогда в виду явной формулы

$$x_k = \frac{3+\sqrt{5}}{10}\left(\frac{25+11\sqrt{5}}{2}\right)^k + \frac{3-\sqrt{5}}{10}\left(\frac{25-11\sqrt{5}}{2}\right)^k$$

сравнение

$$\begin{pmatrix}x_k\\ 5x_{k-1}\end{pmatrix}\equiv (-5)^{3k+1}\begin{pmatrix}1 \\ 29\end{pmatrix}\pmod{n}$$

равносильно сравнению:

$$\left(\frac{25+11\sqrt{5}}{2}\right)^{k-1}\equiv (-5)^{3k+1}(38-17\sqrt{5})\pmod{n}$$

или

$$(\star)\qquad\left(\frac{-1-\sqrt{5}}{2\sqrt{5}}\right)^{\frac{n-1}{2}}\equiv \frac{1-\sqrt{5}}{2}\pmod{n}.$$

Это сравнение можно рассматривать как равенство в кольце $\mathbb{Z}_n[\sqrt5]$ (заметим, что $\left(\frac{5}{n}\right)=-1$), которое при простом $n$ является полем.

...продолжение следует...

[Руст]

Если бы условия были равносильны, то мы бы имели линейный от $\ln(n)$ тест на простоту. Если не ошибаюсь пока минимальные полиномиальные тесты имеют степень 4. Даже тест Рабина-Миллера при предположении недоказанной ОГР дает третью степень. Тем не менее такие линейные тесты у которых исключений очень мало интересны. Хотелось бы узнать у автора задачи откуда они взялись?
maxal можно подробнее отсюда.

maxal писал(а):

сравнение

$$\begin{pmatrix}x_k\\ 5x_{k-1}\end{pmatrix}\equiv (-5)^{3k+1}\begin{pmatrix}1 \\ 29\end{pmatrix}\pmod{n}$$

равносильно сравнению:

$$\left(\frac{25+11\sqrt{5}}{2}\right)^{k-1}\equiv 5^{3k+1}(38-17\sqrt{5})\pmod{n}$$

или

$$(\star)\qquad\left(\frac{-1-\sqrt{5}}{2\sqrt{5}}\right)^{\frac{n-1}{2}}\equiv \frac{1-\sqrt{5}}{2}\pmod{n}.$$

Почему $(-5)^{3k+1}\equiv 5^{3k+1}$, и если получено
$(\frac{25+11\sqrt 5}{2})^{k-1}\equiv (-5)^{3k+1}(a+b\sqrt 5) \mod n$ то должен получится и
$(\frac{25-11\sqrt 5}{2})^{k-1}\equiv (-5)^{3k+1}(a-b\sqrt 5 ) \mod n$.

[maxal]

Руст писал(а):

Почему $(-5)^{3k+1}\equiv 5^{3k+1}$,

Это была описка, исправил.

Руст писал(а):

и если получено
$(\frac{25+11\sqrt 5}{2})^{k-1}\equiv (-5)^{3k+1}(a+b\sqrt 5) \mod n$ то должен получится и
$(\frac{25-11\sqrt 5}{2})^{k-1}\equiv (-5)^{3k+1}(a-b\sqrt 5 ) \mod n$.

Логично, поэтому из этих двух сравнений достаточно оставить только одно.

[Руст]

Ещё одно замечание, непонятно что здесь имелось ввиду:

maxal писал(а):

Это сравнение можно рассматривать как равенство в кольце $\mathbb{Z}_n[\sqrt5]$ (заметим, что $\left(\frac{5}{n}\right)=-1$), которое при простом $n$ является полем.

Что здесь $Z_n[\sqrt 5]$ и почему оно поле? По видимому имелочсь ввиду $Z[\sqrt 5 ]/nZ$.
Лучше работать в кольце $Z[\frac{1+\sqrt 5}{2}]$ являющимся целочисленным замыканием кольца $Z[\sqrt 5 ]$ в его поле частных. К тому же здесь однозначно разложение на простые. Тогда $a=\frac{25+11\sqrt 5}{2}=b\sqrt 5$, $b=\frac{11+5\sqrt 5}{2}$ - обратимый элемент кольца. Перейдя к нормам получаем $5^{k-1}\equiv 5^{6k+2}(-1)$, что эквивалентно $5^{(n-1)/2}=(\frac 5n )=-1$. Получаем ещё сравнение:
$b^{k-1}\equiv (\sqrt 5 )^{(n-1)/2}(-1)^{3k+1}c, \ c=38-17\sqrt 5$.
Основной единицей кольца является $\phi =\frac{1+\sqrt 5}{2}$ c нормой -1. Выразим через него единицы $b=-\phi ^{5}$ и $с=\phi^{-9}$, тогда сравнение будет иметь более простой вид: $\phi^{5k+4}=(\sqrt 5 )^{(n-1)/2}$ или $\phi \phi^{(n-1)/2}=(\sqrt 5 )^{(n-1)/2} \mod n$.
На самом деле это сравнение эквивалентно двум
$n|5^{(n-1)/2}+1$ и $n|L_{(n+1)/2}, \ n=3\mod 4, \ n|F_{(n+1)/2}, \ n=1\mod 4$.
Из первого следует, что все простые делители р числа n имеют вид $n=3,7\mod 10$. Соответственно существуют полупериоды $T_p: \ 5^{T_p}=-1\mod p$ и $\frac{n-1}{2T_p}$ нечётное число.
Из $2L_kL_n=L_{n+k}+(-1)^kL_{n-k}, \ 2L_kF_n=F_{n+k}+(-1)^kF_{n-k}$ получаем, что если $p|L_k$ то 2k (если k нечётное) иначе 4k период по модулю p для $F_n$ и $L_n$.
Учитывая, что $L_p=1\mod p$ и $(\frac 5p)=-1$ получаем, что $p|F_{p+1}$.
Отсюда получаем, что условие эквивалентно тому, что для всех простых делителей n $\frac{n-1}{2T_p}$ нечётное и $\frac{n+1}{a_p}$ нечётное для $n=3\mod 4$ и $b_p|n+1$ для $n=1\mod 4$, где $a_p$ минимальное число для которого $p|L_{a_p}$, и $b_p$ минимальное, для которого $p|F_{b_p}$.
По этим данным можно найти контрпример. Однако минимальный контрпример может оказаться очень большим, так как такое число "вдвойне Кармайклово" как по $n-1$ так и по $n+1$.

[Профессор Снэйп]

Руст писал(а):

Что здесь $Z_n[\sqrt 5]$ и почему оно поле? По видимому имелочсь ввиду $Z[\sqrt 5 ]/nZ$.

Я в предыдущую дискуссию не вникал и что такое $\mathbb{Z}_n[\sqrt{5}]$ не знаю. Но, по-моему, такого кольца, как $Z[\sqrt 5 ]/nZ$, не существует, потому что $n\mathbb{Z}$ не является идеалом в $\mathbb{Z}[\sqrt{5}]$.

[Руст]

Профессор Снэйп писал(а):

Руст писал(а):

Что здесь $Z_n[\sqrt 5]$ и почему оно поле? По видимому имелочсь ввиду $Z[\sqrt 5 ]/nZ$.

Я в предыдущую дискуссию не вникал и что такое $\mathbb{Z}_n[\sqrt{5}]$ не знаю. Но, по-моему, такого кольца, как $Z[\sqrt 5 ]/nZ$, не существует, потому что $n\mathbb{Z}$ не является идеалом в $\mathbb{Z}[\sqrt{5}]$.

Да точнее $(Z/nZ)[\sqrt 5 ]$.

[maxal]

Руст писал(а):

Что здесь $Z_n[\sqrt 5]$ и почему оно поле?

Потому что при простом $n$ кольцо вычетов $\mathbb{Z}_n$ является полем и $\mathbb{Z}_n[\sqrt{5}]\cong \mathbb{Z}_n[x]/\langle x^2 - 5\rangle$, где многочлен $x^2-5$ неприводим над $\mathbb{Z}_n$. Поэтому $\mathbb{Z}_n[\sqrt{5}]$ при простом $n$ является ничем иным как $GF(n^2)$.

Руст писал(а):

тогда сравнение будет иметь более простой вид: $\phi^{5k+4}=(\sqrt 5 )^{(n-1)/2}$ или $\phi \phi^{(n-1)/2}=(\sqrt 5 )^{(n-1)/2} \mod n$.

Это в точности сравнение (*) из моего предыдущего сообщения (с точностью до знака - см. ниже):
http://dxdy.ru/viewtopic.php?p=131096#131096

Добавлено спустя 7 минут 23 секунды:

Руст писал(а):

$\phi \phi^{(n-1)/2}=(\sqrt 5 )^{(n-1)/2} \mod n$.
На самом деле это сравнение эквивалентно двум
$n|5^{(n-1)/2}+1$ и $n|L_{(n+1)/2}, \ n=3\mod 4, \ n|F_{(n+1)/2}, \ n=1\mod 4$.

Ну-ка поподробнее про эту эквивалентность. Особенно интересует, как при составном $n$ из второго вытекает первое.

[Руст]

maxal писал(а):

Руст писал(а):

$\phi \phi^{(n-1)/2}=(\sqrt 5 )^{(n-1)/2} \mod n$.
На самом деле это сравнение эквивалентно двум
$n|5^{(n-1)/2}+1$ и $n|L_{(n+1)/2}, \ n=3\mod 4, \ n|F_{(n+1)/2}, \ n=1\mod 4$.

Ну-ка поподробнее про эту эквивалентность. Особенно интересует, как при составном $n$ из второго вытекает первое.

Из $\phi^{(n+1)/2}=(\sqrt 5 )^{(n-1)/2}\mod n$ вытекает также $\phi_*^{(n+1)/2}=(-\sqrt 5 )^{(n-1)/2}, \ \phi_*=\frac{1-\sqrt 5}{2}.$
Взяв произведение и сумму ($n=3\mod 4$) или разность ($n=1\mod 4$) получаем эти следствия. Но из двух следствий получается и первоначальное.

[maxal]

Руст писал(а):

maxal писал(а):

Руст писал(а):

$\phi \phi^{(n-1)/2}=(\sqrt 5 )^{(n-1)/2} \mod n$.
На самом деле это сравнение эквивалентно двум
$n|5^{(n-1)/2}+1$ и $n|L_{(n+1)/2}, \ n=3\mod 4, \ n|F_{(n+1)/2}, \ n=1\mod 4$.

Ну-ка поподробнее про эту эквивалентность. Особенно интересует, как при составном $n$ из второго вытекает первое.

Из $\phi^{(n+1)/2}=(\sqrt 5 )^{(n-1)/2}\mod n$ вытекает также $\phi_*^{(n+1)/2}=(-\sqrt 5 )^{(n-1)/2}, \ \phi_*=\frac{1-\sqrt 5}{2}.$
Взяв произведение и сумму ($n=3\mod 4$) или разность ($n=1\mod 4$) получаем эти следствия. Но из двух следствий получается и первоначальное.

Вот с обратным как раз и непонятка.
Как, скажем, из $n|(5^{(n-1)/2}+1)$ и $n|L_{(n+1)/2}$ (для составного $n\equiv 3\pmod4$) вытекает, что $\phi^{(n+1)/2}\equiv (\sqrt 5 )^{(n-1)/2}\equiv 5^{(n-3)/4}\cdot \sqrt{5} \pmod{n}$ ?

В данном случае из тождества

$$\phi^k = \frac{L_k + F_k\sqrt{5}}{2}$$

следует, что

$$\phi^{(n+1)/2}\equiv \frac{F_{(n+1)/2}}{2}\sqrt{5} \pmod{n}.$$

Таким образом, необходимо показать, что $F_{(n+1)/2}\equiv 2\cdot 5^{(n-3)/4} \pmod{n}$.

Легко установить следующую сравнимость:

$$F_{(n+1)/2}^2 = \frac{L_{(n+1)/2}^2-4}{5} \equiv \frac{-4}{5} \equiv 4\cdot 5^{(n-3)/2} \pmod{n},$$

но при извлечении из нее квадратного корня возникает неопределенность:

$$F_{(n+1)/2}\equiv 2\cdot 5^{(n-3)/4}\cdot r \pmod{n},$$

где $r$ - некоторый квадратный корень из $1$ - но вот какой? (уже при простом $n$ их два, а при составном и того больше)
Чтобы указанная эквивалентность имела место, необходимо, чтобы $r=1$ - но откуда это следует?

Добавлено спустя 1 час 25 минут 42 секунды:

Руст писал(а):

$n|5^{(n-1)/2}+1$ и $n|L_{(n+1)/2}, \ n=3\mod 4, \ n|F_{(n+1)/2}, \ n=1\mod 4$

Некоторые замечания о сложности нахождения составных $n$ вида $10k+7$ удовлетворяющих таким делимостям.

Делимость $n|5^{(n-1)/2}+1$ можно переписать в виде сравнения:

$$5^{(n-1)/2}\equiv \left(\frac5n\right)\pmod{n},$$

которое означает, что $n$ является псевдопростым Эйлера-Якоби по основанию $5$. При этом оно, конечно же, также является и псевдопростым Ферма по основанию $5$ (заметим, что псевдопростота Ферма - это более слабое условие).

Делимость $n|L_{(n+1)/2}$ означает, что $n$ является псевдопростым Эйлера-Люка. При этом опять же оно также является псевдопростым Люка с параметрами $(P,Q)=(1,-1)$ (и снова заметим, что псевдопростота Люка - это более слабое условие, чем псевдопростота Эйлера-Люка, которое в свою очередь слабее сильной псевдопростоты Люка).

Делимость $n|F_{(n+1)/2}$, как нетрудно видеть, также связана с понятием псевдопростоты Люка (но сильнее его).

Итак, контрпример к обсуждаемому тесту должен быть как минимум псевдопростым Ферма (по основанию $5$) и псевдопростым Люка. В тоже время, одна из известных открытых проблем - это существование числа $n\equiv 3\ \text{or}\ 7\pmod{10}$, которое одновременно является псевдопростым Ферма по основанию $2$ и псевдопростым Люка с параметрами $(P,Q)=(1,-1)$ - за ее решение обещана награда в $620. Наша задача, скорее всего, ничуть не проще.

Добавлено спустя 21 минуту 7 секунд:

Re: Проверка на простоту.

ICh[USU] писал(а):

Я проверил на компьютере, что при $n \leqslant 10^8$ это верно.

Проверил все $n\leq 10^{10}$ - контрпримеров также не найдено.

[Руст]

maxal писал(а):

Делимость $n|5^{(n-1)/2}+1$ можно переписать в виде сравнения:

$$5^{(n-1)/2}\equiv \left(\frac5n\right)\pmod{n},$$

которое означает, что $n$ является псевдопростым Эйлера-Якоби по основанию $5$. При этом оно, конечно же, также является и псевдопростым Ферма по основанию $5$ (заметим, что псевдопростота Ферма - это более слабое условие).

Делимость $n|L_{(n+1)/2}$ означает, что $n$ является псевдопростым Эйлера-Люка. При этом опять же оно также является псевдопростым Люка с параметрами $(P,Q)=(1,1)$ (и снова заметим, что псевдопростота Люка - это более слабое условие, чем псевдопростота Эйлера-Люка, которое в свою очередь слабее сильной псевдопростоты Люка).

Делимость $n|F_{(n+1)/2}$, как нетрудно видеть, также связана с понятием псевдопростоты Люка (но сильнее его).

Итак, контрпример к обсуждаемому тесту должен быть как минимум псевдопростым Ферма (по основанию $5$) и псевдопростым Люка. В тоже время, одна из известных открытых проблем - это существование числа, которое одновременно является псевдопростым Ферма по основанию $2$ и псевдопростым Люка с параметрами $(P,Q)=(1,1)$ - за ее решение обещана награда в $620. Наша задача, скорее всего, ничуть не проще.

В нашем случае $(P,Q)=(1,-1)$. Я могу написать эффективную программу для нахождения контрпримера. Если и в задаче за 620$ (P,Q)=(1,-1) то найду и для этого случая.

[maxal]

Руст писал(а):

В нашем случае $(P,Q)=(1,-1)$. Я могу написать эффективную программу для нахождения контрпримера. Если и в задаче за 620$ (P,Q)=(1,-1) то найду и для этого случая.

Ну да, и там, и там $(P,Q)=(1,-1)$ (что порождает классические числа Фибоначчи и Люка) - исправил. А программу напиши, конечно - посмотрим, что из этого получится. Ну и доказательство эквивалентности в обратную сторону хотелось бы увидеть.

[Руст]

Подкралась ошибка. Посмотрев при р=17 получилось несовпадение знаков. Более внимательно выводится $(-\phi )^{(n+1)/2}=(\sqrt 5 )^{(n-1)/2}$.

[maxal]

Руст писал(а):

Более внимательно выводится $(-\phi )^{(n+1)/2}=(\sqrt 5 )^{(n-1)/2}$.

Ну да. На самом деле это и есть сравнение (*)
Если (*) умножить на $-\phi$ и $(\sqrt{5})^{(n-1)/2}$, то как раз и получается:

$$(-\phi)^{(n+1)/2}\equiv (\sqrt 5 )^{(n-1)/2}\pmod{n}.$$

Но в качественном плане этот знак несущественен. Все те же вопросы по-прежнему остаются без ответа.