2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Проверка на простоту.
Сообщение04.07.2008, 15:19 


30/06/08
6
Екатеринбург
Помогите, пожалуйста, решить такую задачу:

Дано натуральное число $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$ это верно.

 Профиль  
                  
 
 
Сообщение04.07.2008, 16:01 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Вот здесь обсуждались похожие тесты простоты.

 Профиль  
                  
 
 
Сообщение05.07.2008, 01:03 
Модератор
Аватара пользователя


11/01/06
5660
Нетрудно видеть, что при $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$ является полем.

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

 Профиль  
                  
 
 
Сообщение05.07.2008, 08:47 
Заслуженный участник


09/02/06
4382
Москва
Если бы условия были равносильны, то мы бы имели линейный от $\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$.

 Профиль  
                  
 
 
Сообщение05.07.2008, 08:58 
Модератор
Аватара пользователя


11/01/06
5660
Руст писал(а):
Почему $(-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$.

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

 Профиль  
                  
 
 
Сообщение05.07.2008, 11:45 
Заслуженный участник


09/02/06
4382
Москва
Ещё одно замечание, непонятно что здесь имелось ввиду:
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$.

 Профиль  
                  
 
 
Сообщение05.07.2008, 16:23 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Руст писал(а):
Что здесь $Z_n[\sqrt 5]$ и почему оно поле? По видимому имелочсь ввиду $Z[\sqrt 5 ]/nZ$.


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

 Профиль  
                  
 
 
Сообщение05.07.2008, 17:53 
Заслуженный участник


09/02/06
4382
Москва
Профессор Снэйп писал(а):
Руст писал(а):
Что здесь $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 ]$.

 Профиль  
                  
 
 
Сообщение05.07.2008, 20:13 
Модератор
Аватара пользователя


11/01/06
5660
Руст писал(а):
Что здесь $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$ из второго вытекает первое.

 Профиль  
                  
 
 
Сообщение05.07.2008, 21:26 
Заслуженный участник


09/02/06
4382
Москва
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$) получаем эти следствия. Но из двух следствий получается и первоначальное.

 Профиль  
                  
 
 
Сообщение08.07.2008, 08:06 
Модератор
Аватара пользователя


11/01/06
5660
Руст писал(а):
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}$ - контрпримеров также не найдено.

 Профиль  
                  
 
 
Сообщение08.07.2008, 13:25 
Заслуженный участник


09/02/06
4382
Москва
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) то найду и для этого случая.

 Профиль  
                  
 
 
Сообщение08.07.2008, 13:43 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение08.07.2008, 20:15 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение08.07.2008, 21:00 
Модератор
Аватара пользователя


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group