УДК 511.522.2

 

С. М. Вахтеров
МГТУ им. Н.Э.Баумана

г. Москва, Россия

 

АТАКА НА ВЕЛИКУЮ ТЕОРЕМУ ФЕРМА

(для n=3, с комментариями и примерами для любителей)

 

Данная атака не является полным доказательством ВТФ для показателя степени n=3. Тем не менее, она усиливает результаты, ранее полученные другими исследователями, также является слегка упрощенным изложением работ,  размещённых на сайте: http://fermat.2000.ru .

 

Данное доказательство ВТФ [1] для уравнения Ферма:

 = 0,

подразумевает две части (по свойствам функции Эйлера):

1)     (φ(x), φ(y), φ(z), 3) = 1,

2)     (φ(x), φ(y), φ(z), 3) = 3.

 

Здесь и далее именно так (скобками) будет обозначаться наибольший общий делитель - Greatest Common Divisor.

Эти условия  явно не связанны со Случаем 1 (когда одна из переменных уравнения не кратна 3) и Случаем 2 ВТФ (когда кратна).

Функция Эйлера φ(n),  где n — натуральное число, равна количеству натуральных чисел, не больших n и взаимно простых с ним.  Например,  φ(9) имеет шесть таких чисел: 1, 2, 4, 5, 7 и 8 взаимно простых 9.

 ≡ 1 mod (q), для всех a взаимно простых с q.

Функция Эйлера играет ключевую роль в криптосистеме RSA.

Почему необходимо использовать в доказательстве функцию Эйлера, а не обычное представление простых чисел, например 2kp+1?

Во-первых, любое из чисел может быть составным, а значит его каноническое представление может иметь сложный вид: . Таким образом, в доказательстве очень сложно дать возможные представления чисел в приемлемом, для чтения виде.

Во-вторых, функция Эйлера не так уж и сложна, чтобы освоиться с её видом и логикой подсчёта значений.

Рассмотрим такой гипотетический пример:  = 0

φ(x = 19 =2*3*3+1) = 18;
φ(y = 18 =2*3*3) = (3-1)3 =6;
φ(z = 31 =2*3*5+1) = 30.

Как видно, все значения функции Эйлера кратны 3. Этот пример будем использовать для иллюстрации работы 2-ой части доказательства.

Первую часть доказательства, когда (φ(x), φ(y), φ(z), 3) = 1, начнём со следующего примера:  = 0

φ(z=29=4*7+1)= 28, т.е. не кратно 3.

         На самом деле, 1-ая часть доказательства достаточно тривиальна, поэтому общей формулировки строго доказательства в этой статье не потребуется. Просто продемонстрируем на примере логику доказательства, изложенную в другой статье – «Криптосистема RSA против ВТФ» [5].

Так как (φ(z=29), n=3) =1, то возможно создание “ключа”, для шифрования с помощью криптосистемы RSA, из пары чисел: (3, mod 29).

Первое сообщение “для шифрования” будет x =19, второе  y = 18. Оба сообщения взаимно просты с z = 29, поэтому криптограммы получатся разные у этих сообщений:

 mod z, т.е.  mod 29, или  mod 29.

Это справедливо для любых арифметически допустимых значений чисел основного уравнения.

Как видно, в примере  не выполняется ключевое условие существования решения:  mod z и теорема Ферма (для всех подобных примеров) справедлива, т.е. основное уравнение ++ = 0  не имеет решений. (Более детальное доказательство опубликовано на сайте: http://fermat.2000.ru.)

Перейдём ко 2-й части доказательства .

Теорема. Уравнение ++ = 0 не имеет решений, если выполняются условия:

НОД(φ(x), φ(y), φ(z), 3) = 3. Все целые числа x, y, z, имеют значения функции Эйлера, кратные 3.

1)    Невозможно хоть одно из сравнений:
≡ 1 mod (x), если (x,3)=1;
≡ 1 mod (y), если (y,3)=1;
≡ 1 mod (z), если (z,3)=1.

Примеры чисел, которые “мешают” полному доказательству ВТФ, предложенным способом:

≡ 1 mod (61);

Для простых чисел вида 2k3 +1 выполняется ≡ 1 mod (2k3 +1), когда k =10, 11, 12, 15, 17.

Доказательство

Все переменные в основном уравнении ВТФ  ++ = 0 (1) равноправны.  (x, y)=1, (y, z)=1, (x, z) = 1 (2). 

Для получения дальнейших результатов, определимся, что y кратно 3. В доказательстве используются соотношения Барлоу для случая 2 ВТФ [1].

Согласно соотношений Барлоу следует существование таких целых чисел: , , , , , , что:

множители :
y + z = (3),  (4), т.о.  x = – (5),

множители , НОД (y, 3) = 3 (Случай 2 ВТФ):

x + z = (6),   3 (7),

т.о. y = -  (8), при n=0 – Случай 1 ВТФ.

множители :

 =  (9),  (10), т.о.  z=- (11).

Для доказательства используем делители числа z. Если выполняются определенные условия в теореме, с таким же успехом, доказательство проводится с помощью делителей числа x.

Подслучай (φ(), 3) = 3.

Так как по условию (φ(z), 3) = 3, а z=-, сначала рассмотрим случай  (φ(), 3) = 3 (12), затем возможность случая (φ(), 3) =1 (13). Если в обоих случаях основное уравнение Ферма не имеет решений, то справедливость теоремы подтверждается.

(9) ⇒ x ≡ - y  mod  (14),

 / (y + z) =  (15),  поэтому:

  mod  (16). Тогда:

+/(x+y)=+ x (-y)+≡
≡ 3≡3 mod  (17).

Пусть функция Эйлера числа  равна 2k3. В таком случае, возводим в степень φ()/3= 2k левую и правую часть сравнения, чтобы получить значение показателя степени равным значению функции Эйлера числа .

Возводим в степень 2k левую и правую часть сравнения:

 ≡   mod  (18),

 ≡ ≡ 1 ≡  mod  (19).

Несложно проверить, что это условие эквивалентно условию:
1 ≡  ≡  mod (20).

 И это невозможно, т.к. это условие заложено в условие нашей теоремы. Данное условие было “подсмотрено” в доказательстве теоремы Лежандра.

Тем самым, доказан подслучай - НОД(φ(), 3) = 3.

Подслучай (φ(), 3) =1

Так как (φ(), 3) =1, а по предусловию (φ(z), 3) = 3, то следует, что (φ(), 3) = 3, т.е. φ() = 2k3 (21).

Cгруппируем переменные следующим образом:

 (y+z) + (x+z) – (x+y) = 2z (22).

Для этого уравнения, согласно соотношений Барлоу для Случая 1 и Случая 2 ВТФ [1], выводятся следующие уравнения:

Случай 1 ВТФ: НОД(y, 3) = 1 и НОД(φ(), 3) = 3 (23):

 = 2z = -  (24),

2z ≡  ≡ 0 mod () (25),

 ≡  mod () (26),

 ≡ mod () (27), что невозможно по условию теоремы.

Рассмотрим тривиальный пример на основе простых чисел Софи Жермен. Число 3 – является числом Софи Жермен, т.к. 3*2+1=7 – тоже простое число. Рассмотрим, φ() = 2*3. На самом деле, мы можем выбрать любой вариант представления числа, но вариант с числом Софи Жермен, является наиболее наглядным, с точки зрения, истории доказательства теоремы. Тогда:

 ≡  1 mod (=7) (28),

≡  1 mod (=7) (29),

≡  1 mod (7) (30),

≡  -1 mod (7) (31),  возведем в квадрат левую и правую часть, чтобы получить в показателе значение функции Эйлера числа 2*3+1:

≡  1 mod (7) (32),

≡ 1 mod (7), что невозможно.

Случай 2 ВТФ: НОД(y, 3) = 3 и НОД(φ(), 3) = 3 (36):

 = 2z = -  (37),

≡ - mod  (38),

Возведём левую и правую часть сравнения в степень φ()/3:

≡  mod  (39),

1 ≡  mod  (40).

Однако, n3 -1 не делится на 3, поэтому 1 ≢  mod ,

≢0 mod  (41).

Рассмотрим ещё один вариант доказательства этого случая, через модуль .

 = 2z = -  (42),

2z ≡  ≡ 0 mod () (43).

Если данное сравнение справедливо, то должно быть справедливым и сравнение:

2z ≡  ≡ 0 mod () (44), справедливость для которого рассмотрена ранее. Т.е. сравнение

  ≡ 0 mod () (45) справедливо тогда и только тогда, когда справедливо сравнение:

 ≡ 0 mod () (46). Однако, как нами доказано, оно не имеет решения, при выполнении условий теоремы.

Т.о., при заданных условиях, теорема справедлива.

Усилить теорему можно, доказав, что ВТФ справедлива и для случая, без выполнения условия 2 теоремы.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ

 

1. P. Ribenboim, Fermat's last theorem for amateurs, Springer-Verlag, New York, NY, 1999.

2. The RSA Cryptosystem against Last Fermat’s Theorem [2000.ru - http://www.2000.ru/fermats/2000ru_vsm_rsa1a_01_04_2010.htm]. // http:// www.2000.ru (Data 28.03.2010).

3. RSA [Vikipedia - http://en.wikipedia.org].  – Режим доступа: http://en.wikipedia.org/wiki/RSA (дата обращения 07.01.2010).

4.  Euler's_theorem [Vikipedia - http://en.wikipedia.org].  – Режим доступа:  http://en.wikipedia.org/wiki/Euler's_theorem (дата обращения 28.03.2010).

5.  Криптосистема RSA против ВТФ  [fermat.2000.ru - //
http:// fermat.2000.ru http://www.fermat.2000.ru/fermats/2000ru_vsm_rsa1a_01_04_2010.htm

 (дата обращения - Data 07.06.2010).

 

S.M. Vakhterov,  student, Moscow State Technical University n.a. N.E. Bauman

M.I. Vakhterov, editor

 

Contact:

 

http:// www.2000.ru/fermats/proof_fermat_n3_last_theorem_rus_vakhterov.htm

 

Last Modified: June, 13, 2010