2014 dxdy logo

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

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


Правила форума


Дополнение к основным правилам форума:
Любые попытки доказательства сначала должны быть явно выписаны для случая n=3



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Атака на теорему Ферма с помощью криптocистeмы RSА
Сообщение05.05.2010, 16:00 


15/12/05
754
sceptic в сообщении #315801 писал(а):
перейдите на общепринятое обозначение $(mod\verb вместо вашего $mod\verb.


Трудно, но до утра переведу... Извините, это у меня первый опыт. Сегодня ещё Ваши критические замечания "подвигли" к интересному упрощению доказательства, для случая НОД$(\psi(x), \psi(y), \psi(z), e) = e$, без соотношений Барлоу. Так что вечером ждёт идею перепроверка пока собственными силами...

 Профиль  
                  
 
 Re: Атака на теорему Ферма с помощью криптocистeмы RSА
Сообщение06.05.2010, 11:53 


15/12/05
754
sceptic,

ananova в сообщении #315879 писал(а):
Трудно, но до утра переведу...


Сегодня нашёл время перевести в pdf новую редакцию по Вашим советам. Число N сложно повсюду использовать, т.к. передача ему значений от разных переменных уравнения может кого-нибудь запутать, также как и новые обозначения вычетов. Попробовал найти компромисс. А html - подождёт до выходных, т.к. наверняка кое-что придётся поправлять, добавлять.

 Профиль  
                  
 
 Re: Атака на теорему Ферма с помощью криптocистeмы RSА
Сообщение07.05.2010, 17:07 


15/12/05
754
sceptic,

Учитывая, что я довольно долго рассматривал случай $N > x+y$, и косвенно затрагивал в статьях (см. http://www.2000.ru/fermats/vakhterov_vendt_criterion.htm) и тут на странице 119 http://www.nkras.ru/articles/2010/91/sod912010.pdf, но Вы его затронули в своих письмах, посчитал, что может быть кому-то будет интересно понять о чём идёт речь. В связи с чем, привожу выдержку из пока ещё не опубликованной статьи.

И так, вот пример-пособие для заинтересованных:

1) Пусть $x^e +y^e = z^e$ имеет решение, где $e$ - простое число больше 2.

Пусть $N$ такое, что выполняются условия: НОД ($N,xyz$)=1, функция Эйлера числа $N$ - $\psi (N)$ взаимно проста с $e$.

$N$ легко подбирается для любой тройки $x,y,z$, также, как и нечётное число $d$, $de$=1 + $\psi (N)$.

Согласно теоремы Эйлера $a^{\psi (N)+1} \equiv a^{ed} \equiv  a \mod N$ , когда НОД $(a,N)=1$.

2) $(x^e +y^e)^d = z^{ed} $

3) $(x^e +y^e)^d \equiv z^{ed} \mod N$

4) $x^{ed} +y^{ed} + d(x^e+y^e=z^e)h(x^e,y^e) \equiv z^{ed} \mod N$

Здесь $h(x^e,y^e)$ - многочлен, кратный $x^ey^e$.

Согласно теоремы Эйлера :
$x^{ed}  \equiv x \mod N$
$y^{ed}  \equiv y \mod N$
$z^{ed}  \equiv z \mod N$

5) $x+y + d(x^e+y^e=z^e)h(x^e,y^e) \equiv z \mod N$

Хочу обратить Ваше внимание на то, что левая часть сравнения кратна ($x+y$), а правая нет, при $N$ взаимно простом, как с $x+y$, так и с $z$ (по предусловию).

А трактовать это можно так: $z^e \equiv z \mod N $. По-моему, вывод очевиден.

 Профиль  
                  
 
 Re: Атака на теорему Ферма с помощью криптocистeмы RSА
Сообщение07.05.2010, 18:22 


15/12/05
754
ananova в сообщении #316647 писал(а):
А трактовать это можно так: $z^e \equiv z \mod N $. По-моему, вывод очевиден.


Предвидя вопросы, уточняю, - моя трактовка $z^e \equiv z \mod N $ - основывается только на том, что $z^e$, кратно ($x+y$) и известном соотношении Барлоу:$ (x+y)z_2^e =z^e$, но в данном случае, я притянул её за уши, чтобы было о чём поспорить.

Действительно, для соотношений Барлоу нас ждут не менее интересные выводы:

1) $(x+y)^dz_2^{ed} =z^{ed}$
2) $(x+y)^dz_2^{ed} \equiv z^{ed} \mod N$
3) $(x+y)^dz_2 \equiv z \mod N$

 Профиль  
                  
 
 Re: Атака на теорему Ферма с помощью криптocистeмы RSА
Сообщение08.05.2010, 15:21 


15/12/05
754
ananova в сообщении #316647 писал(а):
5) $x+y + d(x^e+y^e=z^e)h(x^e,y^e) \equiv z \mod N$

Хочу обратить Ваше внимание на то, что левая часть сравнения кратна ($x+y$), а правая нет, при $N$ взаимно простом, как с $x+y$, так и с $z$ (по предусловию).


Жду комментариев.

 Профиль  
                  
 
 Re: Атака на теорему Ферма с помощью криптocистeмы RSА
Сообщение08.05.2010, 18:12 


22/02/09

285
Свердловская обл.
ananova в сообщении #316666 писал(а):
Действительно, для соотношений Барлоу нас ждут не менее интересные выводы:

Выводов нет.Все в пределах правил математики.Что можно извлечь из предложенных сравнений?. Если принять $x+y=c^e$ ,то можно сказать,что $c^{d-1}-1$ делится на $N$.

 Профиль  
                  
 
 Re: Атака на теорему Ферма с помощью криптocистeмы RSА
Сообщение08.05.2010, 19:37 


15/12/05
754
Гаджимурат в сообщении #316944 писал(а):
Выводов нет.Все в пределах правил математики.Что можно извлечь из предложенных сравнений?. Если принять $x+y=c^e$ ,то можно сказать,что $c^{d-1}-1$ делится на $N$.


Поправка: $c^{ed-1}-1$ делится на $N$.
Действительно мало интересно, но это понятно, т.к. здесь не было изначально заложено противоречие в уравнение. А вот в 5) оно изначально заложено. Вроде тоже, в пределах правил математики:

5) $x+y + d(x^e+y^e=z^e)h(x^e,y^e) \equiv z \mod N$

6) Согласно Барлоу: $(x+y)=z_1^e$ и $z_1z_2=z$

7) $z_1^e +d(z_1^ez_2^e)h(x^e,y^e) \equiv z_1z_2  \mod N$

8) $z_1^{e-1} +dz_1^{e-1}z_2^eh(x^e,y^e) \equiv z_2  \mod N$

9) $z_1^{e-1}(1 +dz_2^eh(x^e,y^e)) \equiv z_2  \mod N$

Можно продолжить так:
$z_2^{ed-1} \equiv 1 \mod N$ ($ed$-1 взаимнопросто с $e$).

 Профиль  
                  
 
 Re: Атака на теорему Ферма с помощью криптocистeмы RSА
Сообщение13.05.2010, 12:41 


24/05/05
278
МО
ananova в сообщении #316647 писал(а):
$N$ легко подбирается для любой тройки $x,y,z$, также, как и нечётное число $d$, $de$=1 + $\psi (N)$.

Слишком сильно сказано. Более точно: ...нечётное число $d$, $de=1+k\psi (N)$ для некоторого натурального $k$.

ananova в сообщении #316647 писал(а):
4) $x^{ed} +y^{ed} + d(x^e+y^e=z^e)h(x^e,y^e) \equiv z^{ed} \mod N$
Здесь $h(x^e,y^e)$ - многочлен, кратный $x^ey^e$.

Неточность. При раскрытии бинома $(A+B)^d$ множитель $d$ выносится из суммы внутренних слагаемых не всегда (при простом $d$ - да). Рассмотрите, например, бином $(A+B)^6$. Впрочем, сей вынос Вы и не используете.

ananova в сообщении #316647 писал(а):
5) $x+y + d(x^e+y^e=z^e)h(x^e,y^e) \equiv z \mod N$

Аналогично.

ananova в сообщении #316647 писал(а):
Хочу обратить Ваше внимание на то, что левая часть сравнения кратна ($x+y$), а правая нет, при $N$ взаимно простом, как с $x+y$, так и с $z$ (по предусловию).

А трактовать это можно так: $z^e \equiv z \mod N $. По-моему, вывод очевиден.

Мне не очевиден. По-подробнее, пожалуйста.

 Профиль  
                  
 
 Re: Атака на теорему Ферма с помощью криптocистeмы RSА
Сообщение13.05.2010, 15:14 


15/12/05
754
sceptic в сообщении #318884 писал(а):
Неточность. При раскрытии бинома $(A+B)^d$ множитель $d$ выносится из суммы внутренних слагаемых не всегда (при простом $d$ - да).

Вы правы.
sceptic в сообщении #318884 писал(а):
Мне не очевиден. По-подробнее, пожалуйста.

Мне тоже не очевиден. Более того, может быть ошибочен. Это просто игра фантазии, с одной целью - чтобы кто-то быстро указал на ошибку и мы быстро "проехали" подобное предположение.

 Профиль  
                  
 
 Re: Атака на теорему Ферма с помощью криптocистeмы RSА
Сообщение07.06.2010, 09:21 


15/12/05
754
Хотел бы с опозданием отблагодарить публично за полезные замечания и новые перепроверки выводов sceptic, полученные мной в личной переписке.

(Оффтоп)

и Хочу ознакомить всех любителей ВТФ с новыми "революционными" результатами по этой теме (революционными - в том плане, что легко проверяемыми :D ). Если не найду ошибку, то в ближайшую субботу, - т.е. на праздник Дня России, постараюсь найти время набрать текстик . Если найду ошибку, то принесу извинения за баломутство и познакомлю со своими заблуждениями, которые иногда бывают весьма поучительны и интересны :? . Что тут сказать, как в том анекдоте - Созывайте Академию, беру билет на поезд - еду в Москву c доказательством теоремы Ферма :D

 Профиль  
                  
 
 Re: Атака на теорему Ферма с помощью криптocистeмы RSА
Сообщение07.06.2010, 10:25 


15/12/05
754

(Оффтоп)

Ошибку так же быстро нашёл как и "доказательство" ;) Так что не судьба...

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

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



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

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


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

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