Функция Эйлeра однoгo из чисел кpатна степени p - ВTФ веpна

[ananova]

Данная тема является продолжением темы: Кpиптoсистeма RSA пpотив ВTФ:
topic31850.html

Для завершения доказательства ВТФ необходимо проверить теорему:

Теорема. Пусть $x, y, z$ - целые числа, $p$ - проcтое нечетное числo. Если хoть oднo из чиcел $x, y, z$ имеет функцию Эйлера ($\psi$) кратную $p$, то уравнение $x^p+y^p+z^p =0$ не имeeт решений в целых чиcлах.

Доказательство. Предположим $x^p+y^p+z^p =0$ имеет решение и одно из чисел, например $z$, имеет функцию Эйлеpа $\psi(z)=2kp$.

По предположению $x^p+y^p+z^p =0$ имеет решение, тогда следующее уравнение тоже имеет решение$(x^p+y^p+z^p)^{2k}=0$ и сравнение $(x^p+y^p+z^p)^{2k} \equiv 0 \mod (z)$ соответствует предположению.

Т.к. $x, y, z$ - взаимно прoстые, то сoглаcно тeорeмы Эйлеpа:

$x^{p(2k)} \equiv x^{\psi (z)} \equiv 1 \mod (z)$ и $y^{p(2k)} \equiv y^{\psi (z)} \equiv 1 \mod (z)$, $x^{\psi (z)}+ y^{\psi (z)} \equiv 2 \mod (z)$.

После преобразований $(x^p+y^p+z^p)^{2k} $получается следующее сравнение:
$(x^p+y^p+z^p)^{2k} \equiv x^{\psi (z)} + y^{\psi (z)} \equiv 2 \mod (z)$, которое противоречит предположению: $(x^p+y^p+z^p)^{2k} \equiv 0 \mod (z)$.
Теорема доказана.

[venco]

ananova в сообщении #307687 писал(а):

$(x^p+y^p+z^p)^{2k} \equiv x^{\psi (z)} + y^{\psi (z)} \mod (z)$

Почему?

[age]

ananova
А если ни oднo из чиcел $x, y, z$ не имеет функцию Эйлера ($\psi$) кратную $p$?

[venco]

age в сообщении #307759 писал(а):

ananova
А если ни oднo из чиcел $x, y, z$ не имеет функцию Эйлера ($\psi$) кратную $p$?

Как уже доказано, одно из чисел должно делиться на $p^2$. Соответственно, его функция Эйлера будет кратна $p$.

[age]

Ну да, получается, что ananova доказал Случай 2.

[venco]

age в сообщении #307776 писал(а):

Ну да, получается, что ananova доказал Случай 2.

Правильнее: сказал, что доказал. ;)

[age]

Правда, не пойму, зачем нужно было менять простое число $p$ на функцию Эйлера? С $p$, по-моему, гораздо понятнее.

[ananova]

age
venco
Благодарен, что Вы уделили время (поскольку все молчат, и не только на этом форуме), а Ваше мнение для меня очень важно. Перепроверьте, пожалуйста, ещё раз всё что я написал.

Что касается функции Эйлера, то она используется в RSA и вокруг неё "всё вертится", а именно если она не кратна $p$, то вариантов нет - любое возведение в степень $p$ будет давать разные результаты для разных чисел. Её нельзя заменить просто на $p$, т.к. любое число может быть составным, а значит его структуру определяют несколько простых чисел, которые и опредляют результат функции Эйлера. Более сложный случай, когда функция Эйлера кратна $p$.

Но вот согласно этой теореме и этот чёрт не так страшен. Осталось убедиться ещё раз в её справедливости.

Преобразование $(x^p+y^p+z^p)^{2k}$ выполнено так:

$(x^p+y^p+z^p)^{2k} \equiv (x^p+y^p)^{2k} \equiv $
$\equiv x^{2kp}+y^{2kp}+2k(x^p+y^p)g(x,y) \equiv x^{\psi (z)}+y^{\psi (z) } \mod (z)$

$2k(x^p+y^p)g(x,y) $ - хочу вот этот хвостик сам перепроверить - может он не совсем подобен, как это имеет в случае, когда показатель степени $p$...

[venco]

ananova в сообщении #307855 писал(а):

Преобразование $(x^p+y^p+z^p)^{2k}$ выполнено так:

$(x^p+y^p+z^p)^{2k} \equiv (x^p+y^p)^{2k} \equiv $
$\equiv x^{2kp}+y^{2kp}+2k(x^p+y^p)g(x,y) \equiv x^{\psi (z)}+y^{\psi (z) } \mod (z)$

Так ведь неправильно выполнено. Забыли бином Ньютона?

[ananova]

venco в сообщении #307863 писал(а):

Забыли бином Ньютона?

Ну, да! - Последнее время всё время приходилось работать только с простым показателем степени бинома, по инерции разложил и для чётного. Что тут сказать - поспешил, заявляю официально - данная теорема неверна!

-- Пт апр 09, 2010 07:14:28 --

В порядке исследования:
$(x_1^p+y_1^p+z_1^p) \equiv 0 \mod (z_1)$ , что равносильно: $x_1^p \equiv -y_1^p \mod (z)$
$x_1^{p(2k)} \equiv -y_1^{p(2k)} \mod (z_1)$
$x_1^{\psi (z_1)} \equiv -y_1^{\psi (z)} \mod (z_1)$
$1 \equiv 1 \mod (z_1)$

[ananova]

Может и здесь поможете перепроверить?

В порядке исследования на тему обобщения доказательства Лежандра, например для Случая 1 (если для Случая 1 справедливо, то будет справедливо и для Случая 2).

Используем соотношения Барлоу:
$x_1^p=y+z, y_1^p=x+z, z_1^p=x+y$

Если $\psi (z_1) \equiv 0 \mod p$, например: $\psi (z_1)=2kp$, то и $\psi (z) \equiv 0 \mod p$

$(x+z) +(y+z)-(x+y)=2z \equiv 0 \mod (x+y)$
$y_1^p + x_1^p +z_1^p=2z \equiv 0 \mod (z_1)$
$x \equiv -y \mod z_1$

$x^p/x_1^p=x_2^p=y^{p-1}-y^{p-2}z+y^{p-3}z^2-...+z^{p-1}$.
Поэтому:
$x^{p-1} \equiv y^{p-1} \equiv x_2^p \mod (z_1)$

$z^p/z_1^p=z_2^p=x^{p-1}-x^{p-2}(-y)+x^{p-3}(-y)^2-...+(-y)^{p-1}$.
$z_2^p \equiv px^{p-1} \equiv px_2^p \mod (z_1)$

Т.к. НОД($x_2, z_1$) взаимнопростые, то имеется число $g: gx_2 \equiv 1 \mod (z_1)$
Умножаем левую и правую часть сравнения на $g^p$:
$(gz_2)^p \equiv p \mod (z_1)$
Возведём левую и правую часть сравнения в степень $2k$:
$(gz_2)^{\psi (z_1)} \equiv p^{(2k)} \mod (z_1)$
$1 \equiv p^{(2k)} \mod (z_1)$
Что невозможно, т.к. $\psi (z_1) =2kp$ (см. доказательство на стр.127 Рибенбойма к теореме 1С)

[ananova]

Также прошу перепроверить- справедлив ли такой логический вывод:

Согласно соотношений Барлоу $z_1$ делит $z$. При этом $\psi (z) \equiv 0 \mod p$ и верно начальное уравнение:
$x_1^p+y_1^p+z_1^p=2z$ и сравнение: $x_1^p+y_1^p+z_1^p \equiv 0 \mod (z_1)$

Верен и конечный результат, полученный из этих предположений) : $1 \equiv p^{2k} \mod (z_1)$, то следует ли логический вывод: $\psi (z_1) \equiv 0 \mod p$?

Если следует и верен, то тогда все остальные результаты должны быть верны. Если нет, то чего не хватает в логике?

-- Пт апр 09, 2010 11:32:54 --

ananova в сообщении #307903 писал(а):

$(x+z) +(y+z)-(x+y)=2z \equiv 0 \mod (x+y)$

Правильно читать не по модулю (x+y), а по модулю z_1, при этом z_1^p=(x+y).

[ananova]

В принципе, особо не возитесь, я сам потихоньку разберусь - сообщу о результате...

[ananova]

ananova в сообщении #307903 писал(а):

Может и здесь поможете перепроверить?

В порядке исследования на тему обобщения доказательства Лежандра, например для Случая 1 (если для Случая 1 справедливо, то будет справедливо и для Случая 2).

Используем соотношения Барлоу:
$x_1^p=y+z, y_1^p=x+z, z_1^p=x+y$

Если $\psi (z_1) \equiv 0 \mod p$, например: $\psi (z_1)=2kp$, то и $\psi (z) \equiv 0 \mod p$

$(x+z) +(y+z)-(x+y)=2z \equiv 0 \mod (x+y)$
$y_1^p + x_1^p +z_1^p=2z \equiv 0 \mod (z_1)$
$x \equiv -y \mod z_1$

Если кто-то будет перепроверять, то надо учесть, что этот вариант отличается от того, что уже обсуждался здесь на форуме, - в выборе модуля. В статье "Обoбщение тeорeмы Лeжандра) используется - делитель числа $z$ - простое число вида $q_z=2kp+1$, а в этом исследовании - $z_1$. Подводный камень может быть в том, что $q_z=2kp+1$ имеет $\psi (q_z)=2kp$, а $z_1$ может иметь $\psi (z_1)$ не кратную $p$, при этом может выполняться $\psi (z_1^p)=2kp$ и $\psi (z^p) \equiv 0 \mod (p)$.
Однако, ранее доказано (что согласно алгоритма RSA), что достаточным условием для существования гипотетического решения является не $\psi (z^p) \equiv 0 \mod (p)$, а именно $z$: $\psi (z) \equiv 0 \mod (p)$. Согласно соотношений Барлоу: $z_1z_2=-z$, следовательно либо $z_1$, $либо z_2$ имееют функцию Эйлера кратную $p$.
Учитывая, что $y_1^p + x_1^p +z_1^p=2z \equiv 0 \mod (z_1)$ справедливо, при предположении, что именно $\psi (z_1)=2kp$, то других вариантов вроде как не может быть.

В общем, я сейчас в раздумьях - менять в статье доказательство через простое вида - $q_z=2kp+1$ или поменять на более сильное $\psi (z_1)=2kp$, если отстутствуют ошибки в рассуждениях и замена будет тождественной.

[venco]

ananova в сообщении #307940 писал(а):

Согласно соотношений Барлоу...

Эти соотношения верны для первого случая ВТФ.