“The RSA Cryptosystem against Fermat’s Last Theorem”

 

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

M.I. Vakhterov, editor

 

“The RSA Cryptosystem against Fermat’s Last Theorem”

(Proof The Strong Theorem for The Fermat’s Last Theorem)

 

About problem to see [P. Ribenboim, 1].

My result:

The Theorem

 If

e – prime; e > 2;  x, y, z – integers & gcd: (x, y)=(y, z)=(x, z)=1 &

1)    (φ(x), φ(y), φ(z), e) = 1, {Euler’s totient  φ, to see [2]}{gcd =1}

2)    (φ(x), φ(y), φ(z), e) ≠ 1 &
(≡ 1 (mod x) & (x,e) =1) OR
(≡ 1 (mod y) & (y,e) =1) OR
(≡ 1 (mod z) & (z,e) =1).

 

It means that Fermat's Last Theorem (FLT) is fair and + ≠ .

 

e – prime  →  φ(e) = e – 1, φ(e) +1 = e.

Euler’s totient  φ(q) of a positive integer q is defined to be the number of positive integers less than or equal to n. For example,  φ(9) since the six numbers 1, 2, 4, 5, 7 and 8 are coprime to 9.

 ≡ 1 mod (q), for all a a coprime to q. The totient function also plays a key role in the definition of the RSA encryption system.

 

Proof.

( — Begin —
—  The Simple Arithmetic restrictions , [1] — )

(1)                     +  +  ≡ 0 mod x,
 +  +  ≡ 0 mod y,
 +  +  ≡ 0 mod z.

If  ∃ q :  gcd(e, q) = 1 & gcd(x, y, z, q) = 1

  ∃ (b,d): ed = bφ(q) +1, +  +  ≡ 0 mod q, [6].

(2)     +  +  =  +  +

(3)     +  +  ≡  x + y + z ≡ 0 mod (e)

(4)    >  +  = –   x + y > – z

(4)   → (5): x ≢ y mod z;  x ≢ –z mod y;  y≢ –z mod x.

{x ≡ y (mod z) or x≡ –z (mod y) or y≡ –z (mod x)}  +≠ .

( — End —  The Simple Arithmetic restrictions — )

 ( — Begin —
— Algorithm The RSA Cryptosystem & Euler’s Theorem,to see [3], [4] — )

 (R1) if (φ(x),e) = 1   encrypt key (e, mod x)

z ≢ y → (encrypt) →  ≢  (mod x) +≠ .

(R2) if (φ(y),e) = 1   encrypt key (e, mod y)

z ≢ x → (encrypt) →  ≢  (mod y) +≠ .

(R3) if (φ(z),e) = 1   encrypt key (e, mod z)

x ≢ y →  ≢  (mod z) +≠ .

 (R4) THE RESULT 1: if (φ(x), φ(y), φ(z), e) = 1 +≠ .

( — End —  Algorithm RSA Cryptosystem & Euler’s Theorem — )

( — Begin —
— Barlow’s result,  to see [1] — )

(B1) (for ):

=, , ,

(B2) (for : Case 2: (y,e) = e))

=, , ,

(B3) (for : Case 1: (y,e) = 1))

=, , ,

(B4) (for ):

 = , ,  .

(B5) (=1, (=1, (=1.

(— End — Barlow’s result — )

(— Begin —
The proof for (φ(x), φ(y), φ(z), e) = e, The  Imitation Legandre [1],[5] — )

(— Begin — (φ(), e) = e — )

(M1) (B4): x + y =    x ≡ –y mod .

(М2) (B4)

/) =( 

 ). Then

(М3) +/(x + y) =

 =  ≡

   (mod ).

(М4)  ≡  (mod ).

{Euler’s Theorem. If (a, ) = 1, then  ≡ 1 (mod ).}

(М5)  ≡ ≡ 1 ≡  mod +≠ .

(if  the second condition of the theorem fairly!)

(— Еnd — (φ(), e) = e — )

(— Begin — (φ(), e) = 1 & (φ(), e) = e — )

(L1)  ) = .

(— Begin — (y, e) = 1 — )

(L2) (B1, B3, B4 & L1)   = .

(L3) {(φ(), e) = e & (φ(), e) = 1} (φ(), e) = e.

(L3) 2z ≡  ≡ 0 mod,

(L4)  ≡  mod ,

(L5)  ≡    mod,

(L6)  ≡ 1 mod, it is impossible

   ≢0 mod,

(L7.1 example) The trivial example for prime Sophie Germain:

e: φ() = 2e

(L7.2 example)  ≡ ≡ 1 mod ,

(L7.3 example) ≡  1 mod ,

(L7.4 example) 1 + 1+ ≡  1 mod ,

(L7.5 example) 2≡  -1 mod ,

(L7.6 example) ≡  1 mod (),

(L7.6 example) ≡  1 mod (), it is impossible

(— Begin— 
Another proof for this part:
Case 1: (y, e) = 1 & (φ(), e) = e —)

It may be possible:

If  ≡ 0 mod , (φ(), e) = e

Then may be  Barlow’s  relations of the “second order”: :
 = –,  = – и  = –.

And (M1-M5), but for - (φ(), e) = e to make proof.

        (— End another proof for this part —)

 (— End — (y, e) = 1 —)

(— Begin — Case 2: (y, e) = e — )

(L8) (B1, B2, B4 & L1)   = .

(L9) ≡ - mod , {(L9)  }

(L10) ≡  mod ,

(L11) 1 ≡  mod ,

(L12) (ne -1,e) = 1  →

→ 1 ≢  mod  →

→ ≢0 mod .

(— End — Case 2: (y, e) = e — )

(— End — (φ(), e) = 1 & (φ(), e) = e — )

 (— End — proof for (φ(x), φ(y), φ(z), e) = e —)

Final Result:

if (φ(x), φ(y), φ(z), e) ≠ 1 and (the 2-nd condition of the theorem fairly)

  +≠ , (M5, L12)

if (φ(x), φ(y), φ(z), e) = 1  +≠ (R4)

+≠ .

References

1. P. Ribenboim, Fermat's Last Theorem for Amateurs, Springer-Verlag, New York, NY, 1999. pp. xiv+407, ISBN 0-387-98508-5.

2.  Euler's_theorem [Vikipedia - http://en.wikipedia.org].  //  http://en.wikipedia.org/wiki/Euler's_theorem (Data 28.03.2010).

3. RSA [Vikipedia - http://en.wikipedia.org].  // http://en.wikipedia.org/wiki/RSA (Data 07.04.2010).

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

5. Larry Riddle, Sophie Germain and Fermat's Last Theorem [Agnes Scott College - http://www.agnesscott.edu]. // http://www.agnesscott.edu/Lriddle/WOMEN/germain-FLT/SGandFLT.htm (Data 07.04.2010).

6.  S.M.Vakhterov, Generalisation of a Vendt’s criterion (trivial case) by means of  Euler’s theorem for any integers // – 2010. – №3(09). – Vol 1. – p. 119. – ISSN 2072-0831.
(E-verison: http://fermat.2000.ru/fermats/vakhterov_vendt_criterion.htm)

 

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

M.I. Vakhterov, editor

 

Contact:

 

http:// www.2000.ru/fermats/rsa_short_proof_fermat_last_theorem_english_vakhterov15-04-2010.htm

 

 

Last Modified: April, 29, 2010