2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Формула разложения простого P=4n+1 на сумму двух квадратов
Сообщение21.06.2014, 16:00 
Заслуженный участник
Аватара пользователя


18/12/07
762
1.
Методика вывода формулы аналогична методике в теме
Представление простого P=3n+1 формой P=A^2-AB+B^2
Вывод даю схематично.

Пусть простое $$P \equiv 1\left( {\bmod 4} \right), g $ - его первообразный корень. $$\omega  = e^{\frac{{2\pi i}}{P}}$

Обозначим

$$  
\varsigma _{\left( m \right)}  = \sum\limits_{k = 1}^{\frac{{P - 1}}{4}} {\omega ^{g^{4k + m} } } 
$

$$ 
\eta _{\left( 0 \right)}  = \left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right) + \left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)i
$
Тогда
$$ 
\eta _{\left( m \right)}  = \left( {\varsigma _{\left( m \right)}  - \varsigma _{\left( m+1 \right)} } \right) + \left( {\varsigma _{\left( m+2 \right)}  - \varsigma _{\left( m+3 \right)} } \right)i = i^m \eta _{\left( 0 \right)} 
$

$$ 
\left\{ \begin{array}{l}
 P = 8k + 1 \to \bar \varsigma _{\left( m \right)}  = \varsigma _{\left( m \right)}  \\ 
 P = 8k + 5 \to \bar \varsigma _{\left( m \right)}  = \varsigma _{\left( {m + 2} \right)}  \\ 
 \end{array} \right.
$

$$ 
\left\{ \begin{array}{l}
 \bar \eta _{\left( 0 \right)}  = \left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right) - \left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)i \to P = 8k + 1 \\ 
 \bar \eta _{\left( 0 \right)}  =  - \left( {\left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right) - \left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)i} \right) \to P = 8k + 5 \\ 
 \end{array} \right.
$

Из $\[\eta _{\left( m \right)} ^4  = \eta _{\left( 0 \right)} ^4 \] $, следует, что все изоморфизмы $\[\eta _{\left( m \right)} ^4\] $ по $\omega $ равны. Значит
$$
\eta _{\left( 0 \right)} ^4  = c\left( {a + bi} \right) \to \left( {a,b} \right) = 1
$

Далее
$$
\lambda  = \left( {\bar \varsigma _{\left( 1 \right)}  - \bar \varsigma _{\left( 3 \right)} } \right)\left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right) - \left( {\bar \varsigma _{\left( 0 \right)}  - \bar \varsigma _{\left( 2 \right)} } \right)\left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right) = 0
$

$$
\eta _{\left( 0 \right)} \bar \eta _{\left( 0 \right)}  = \left( {\sum\limits_0^3 {\varsigma _{\left( k \right)} \bar \varsigma _{\left( k \right)} } } \right) - \left( {\sum\limits_0^3 {\varsigma _{\left( k \right)} \bar \varsigma _{\left( {k + 2} \right)} } } \right) + \lambda  = \left( {\frac{{3P + 1}}{4}} \right) - \left( { - \frac{{P - 1}}{4}} \right) = P
$

$$
\left( {\eta _{\left( 0 \right)} \bar \eta _{\left( 0 \right)} } \right)^4  = c^2 \left( {a^2  + b^2 } \right) = P^4  \to c = P
$
(Доказательство опускаю.) Значит
$$a^2  + b^2  = P^2 $

Из однозначности разложения для чисел Гаусса следует
$$
a + bi = \left( {m + in} \right)^2  \to m^2  + n^2  = P
$

Т.о.
$$
\eta _{\left( 0 \right)} ^4  = P\left( {m + in} \right)^2  \to \eta _{\left( 0 \right)} ^2  = \sqrt P \left( {m + in} \right)

$
Возможный знак минус перед выражением можно "спрятать" в полученное Гауссово число.

Окончательно получим
$$
m = \frac{{\eta _{\left( 0 \right)} ^2  + \bar \eta _{\left( 0 \right)} ^2 }}{{2\sqrt P }} = \frac{{\left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right)^2  - \left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)^2 }}{{\sqrt P }}
$

$$
n = \frac{{\eta _{\left( 0 \right)} ^2  - \bar \eta _{\left( 0 \right)} ^2 }}{{2i\sqrt P }} = 2\frac{{\left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right)\left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)}}{{\sqrt P }}
$

$$
P = m^2  + n^2 
$
Причём $n$ чётное

 Профиль  
                  
 
 Re: Формула разложения простого P=4n+1 на сумму двух квадратов
Сообщение22.06.2014, 22:13 
Заслуженный участник
Аватара пользователя


18/12/07
762
2.
Пример
$\[
P = 13,g = 2 \to \omega  = e^{\frac{{2\pi i}}{P}} 
\]
$

$\[
\left\{ \begin{array}{l}
 \varsigma _{\left( 0 \right)}  = \omega ^1  + \omega ^3  + \omega ^9  \\ 
 \varsigma _{\left( 1 \right)}  = \omega ^2  + \omega ^6  + \omega ^5  \\ 
 \varsigma _{\left( 2 \right)}  = \omega ^4  + \omega ^{12}  + \omega ^{10}  \\ 
 \varsigma _{\left( 3 \right)}  = \omega ^8  + \omega ^{11}  + \omega ^7  \\ 
 \end{array} \right.
\]
$

$\[
\left\{ \begin{array}{l}
 \eta _{\left( 0 \right)}  = \left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right) + \left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)i \\ 
 \bar \eta _{\left( 0 \right)}  =  - \left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right) + \left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)i \\ 
 \end{array} \right.
\]
$

$\[
\left[ {\left( {\varsigma _{\left( 0 \right)}  + \varsigma _{\left( 2 \right)} } \right) - \left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)} \right]^2  = 13
\]
$

$\[
\left\{ \begin{array}{l}
 \eta _{\left( 0 \right)} ^2  = \left( {3 - 2i} \right)\left[ {\left( {\varsigma _{\left( 0 \right)}  + \varsigma _{\left( 2 \right)} } \right) - \left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)} \right] = \left( {3 - 2i} \right)\sqrt {13}  \\ 
 \bar \eta _{\left( 0 \right)} ^2  = \left( {3 + 2i} \right)\left[ {\left( {\varsigma _{\left( 0 \right)}  + \varsigma _{\left( 2 \right)} } \right) - \left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)} \right] = \left( {3 + 2i} \right)\sqrt {13}  \\ 
 \end{array} \right.
\]
$

$\[
\left\{ \begin{array}{l}
 m = \frac{{\eta _{\left( 0 \right)} ^2  + \bar \eta _{\left( 0 \right)} ^2 }}{{2\sqrt {13} }} = 3 \\ 
 n = \frac{{\eta _{\left( 0 \right)} ^2  - \bar \eta _{\left( 0 \right)} ^2 }}{{2i\sqrt {13} }} =  - 2 \\ 
 \end{array} \right.
\]
$

$\[
m^2  + n^2  = 13
\]
$

 Профиль  
                  
 
 Re: Формула разложения простого P=4n+1 на сумму двух квадратов
Сообщение23.06.2014, 11:27 


23/02/12
3451
А как у Вас получаются остальные решения: $(3,2), (-3,2), (-3,-2)$ и симметричные 4 решения?

 Профиль  
                  
 
 Re: Формула разложения простого P=4n+1 на сумму двух квадратов
Сообщение24.06.2014, 13:45 
Заслуженный участник
Аватара пользователя


18/12/07
762
vicvolf в сообщении #878583 писал(а):
А как у Вас получаются остальные решения: $(3,2), (-3,2), (-3,-2)$ и симметричные 4 решения?

Цифровое воплощение результата не зависит от знака $m,n$ и перестановки слагаемых.
Разные же знаки $m,n$ зависят от выбора первообразного корня для данного простого числа, а какое слагаемое стоит на первом месте зависит от личного предпочтения. Но следует учесть, что получаемое по приведённой формуле $n$ всегда чётно.

3.
Я остановлюсь на кратком анализе полученных формул. Сначала для $m$.
Так как для простых $P=4k+1$

$$
P = \prod\limits_{k = 1}^{\frac{{P - 1}}{2}} {\left( {1 - \omega ^k } \right)^2 }  \to \sqrt P  = \prod\limits_{k = 1}^{\frac{{P - 1}}{2}} {\left( {1 - \omega ^k } \right)} 
$

то, разложив правую часть на множители, получим
$$
m\prod\limits_{k = 1}^{\frac{{P - 1}}{2}} {\left( {1 - \omega ^k } \right)}  = \left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)}  + \varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)\left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)}  - \varsigma _{\left( 1 \right)}  + \varsigma _{\left( 3 \right)} } \right)
$

$m$ - целое рациональное число. Остальные множители - целые приведённые алгебраические числа кольца $\mathbb{R}$$(\omega)$ с коэффициентами при $\omega  =  \pm 1$, свободным членом равным нулю и, следовательно, не имеют целых рациональных делителей (теория чисел).

$${\left( {1 - \omega ^k } \right)}$ - простое алгебраическое число. Оно уникально тем, что вне зависимости от однозначности или неоднозначности разложения на простые множители в данном кольце делится либо на первый, либо на второй множитель правый части.
Т.о. получим
$$m = \varphi _1 \left( \omega  \right)\varphi _2 \left( \omega  \right)$ - т.е. равно произведению двух целых алгебраических чисел данного кольца.
Это справедливо и для $n/2$.
Далее. Все эти рациональные делители можно описать, зная все подполя поля от $\omega $. Или попытаться решить обратную задачу - для каких простых чисел приведённые формулы могут дать определённое значение $m_0$ или $n_0$.

В сообщениях post130408.html#p130408 и post130803.html#p130803 я элементарно показал, что что существует бесконечное множество таких целых рациональных $m_0 $, что последовательность ${m_0}^2+x^2 $ содержит бесконечно много простых чисел.
Поэтому поставленная выше "обратная задача" возможно даст некий подход к проблеме бесконечности простых чисел в последовательности ${m_0}^2+x^2 $

 Профиль  
                  
 
 Re: Формула разложения простого P=4n+1 на сумму двух квадратов
Сообщение24.06.2014, 15:36 
Заслуженный участник


20/12/10
9179
Коровьев в сообщении #879155 писал(а):
В сообщениях post130408.html#p130408 и post130803.html#p130803 я элементарно показал, что что существует бесконечное множество таких целых рациональных $m_0 $, что последовательность ${m_0}^2+x^2 $ содержит бесконечно много простых чисел.
Что-то я не понимаю этого доказательства. Почему после вычеркивания бесконечных строк получится матрица с конечным числом столбцов? Ведь длины конечных строк не обязаны быть равномерно ограничены. А если обязаны, то по какой причине?

 Профиль  
                  
 
 Re: Формула разложения простого P=4n+1 на сумму двух квадратов
Сообщение24.06.2014, 18:16 
Заслуженный участник
Аватара пользователя


18/12/07
762
nnosipov в сообщении #879215 писал(а):
Ведь длины конечных строк не обязаны быть равномерно ограничены. А если обязаны, то по какой причине?

А этого и не требуется. В последнем столбце, (а он обязан быть, раз вычеркнуты все бесконечные строки) может быть даже один или несколько элементов и, естественно, величина суммы его членов тоже конечна и меньше $\frac{{\pi ^2 }}{6}$

 Профиль  
                  
 
 Re: Формула разложения простого P=4n+1 на сумму двух квадратов
Сообщение24.06.2014, 19:32 
Заслуженный участник


20/12/10
9179
Коровьев в сообщении #879311 писал(а):
В последнем столбце, (а он обязан быть, раз вычеркнуты все бесконечные строки)
С чего вдруг последний столбец обязан быть? Представьте себе бесконечную нижнетреугольную матрицу, где у неё последний столбец?

 Профиль  
                  
 
 Re: Формула разложения простого P=4n+1 на сумму двух квадратов
Сообщение25.06.2014, 01:55 
Заслуженный участник
Аватара пользователя


18/12/07
762
nnosipov в сообщении #879353 писал(а):
С чего вдруг последний столбец обязан быть? Представьте себе бесконечную нижнетреугольную матрицу, где у неё последний столбец?

Всё верно, гнилое доказательство. С бесконечностью аккуратно надо. Ну да бог с ним.

4.
Продолжу.
$P \equiv 1\left( {\bmod 4} \right)$, g - первообразный корень.
Достаточно известно (особенно в криптографии) разложение простого числа на сумму двух квадратов с применением символа Лежандра
$$
P = \left[ {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3  + mx}}{P}} \right)} } \right]^2  + \left[ {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3  + nx}}{P}} \right)} } \right]^2 
$

где $m$ - квадратичный вычет, а $n$ - квадратичный невычет по модулю $P$
Причём, второй квадрат чётное число.
Сравнивая с выведенными выше формулами и учитывая, что представление простого числа на сумму двух квадратов с точностью до перестановки квадратов единственно, можно записать

$$
\left| {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3  + mx}}{P}} \right)} } \right| = \left| {\frac{{\left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right)^2  - \left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)^2 }}{{\sqrt P }}} \right|
$

$$
\left| {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3  + nx}}{P}} \right)} } \right| = \left| {2\frac{{\left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right)\left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)}}{{\sqrt P }}} \right|
$
где
$$
\varsigma _{\left( m \right)}  = \sum\limits_{k = 1}^{\frac{{P - 1}}{4}} {\left( {e^{\frac{{2\pi i}}{P}} } \right)^{g^{4k + m} } } 
$

Далее.
Рассмотрим уравнение
$$y^2  \equiv a\left( {\bmod P} \right)$

Используя символ Лежандра число его решений можно записать так

$$N = 1 + \left( {\frac{a}{P}} \right)$

А число решений по модулю $P$ эллиптического уравнения
$$y^2  \equiv x^3  + ax\left( {\bmod P} \right)$
равно
$$
N = P + \sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3  + ax}}{P}} \right)}
 
$
Иными словами, получено явное выражение для числа точек на данной эллиптической кривой по простому модулю $P \equiv 1\left( {\bmod 4} \right)$

$$
N = 1 + P - \left| {2\frac{{\left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right)^2  - \left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)^2 }}{{\sqrt P }}} \right|
$

$$
N = 1 + P - \left| {4\frac{{\left( {\varsigma _{\left( 0 \right)}  - \varsigma _{\left( 2 \right)} } \right)\left( {\varsigma _{\left( 1 \right)}  - \varsigma _{\left( 3 \right)} } \right)}}{{\sqrt P }}} \right|
$

где в зависимости от $a$ вычет/не вычет надо в квадратных скобках выбирать первое или второе выражение.
Единица добавлена как спец.точка (аналог бесконечно удалённой точки)

 Профиль  
                  
 
 Re: Формула разложения простого P=4n+1 на сумму двух квадратов
Сообщение25.06.2014, 07:50 
Заслуженный участник


20/12/10
9179
Вот здесь http://www.ega-math.narod.ru/Books/Ireland.djv задача о представлении простого $p \equiv 1 \pmod{4}$ в виде $p=a^2+b^2$ и простого $p \equiv 1 \pmod{3}$ в виде $p=a^2-ab+b^2$ решается с помощью сумм Якоби $J(\chi,\chi)$ для биквадратичного и кубического характера $\chi$ соответственно (см. предложение 8.3.1). Связь между суммами Якоби и Гаусса см. в теореме 1, п. (d), а также в предложении 8.3.3. Например, для $p \equiv 1 \pmod{4}$ имеем
$$
J(\chi,\chi)=a+bi=\frac{g(\chi)^2}{g(\chi^2)}=\frac{g(\chi)^2}{\sqrt{p}},
$$
где $\chi$ --- биквадратичный характер (поскольку $\chi^2$ --- квадратичный характер, т.е. символ Лежандра, так что $g(\chi^2)=\sqrt{p}$).
Коровьев в сообщении #879508 писал(а):
Достаточно известно (особенно в криптографии) разложение простого числа на сумму двух квадратов с применением символа Лежандра
$$P = \left[ {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3  + mx}}{P}} \right)} } \right]^2  + \left[ {\frac{1}{2}\sum\limits_{x = 0}^{P - 1} {\left( {\frac{{x^3  + nx}}{P}} \right)} } \right]^2$
где $m$ - квадратичный вычет, а $n$ - квадратичный невычет по модулю $P$
Формула Якобшталя, судя по "Высшей арифметике" Дэвенпорта.

 Профиль  
                  
 
 Re: Формула разложения простого P=4n+1 на сумму двух квадратов
Сообщение25.06.2014, 18:55 


16/08/05
1154
На Хабре была статья в тему.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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