Эйлерийн теорем

Чөлөөт нэвтэрхий толь — Википедиагаас
Харайх: Удирдах, Хайлт

Тооны онолд Эйлерийн теорем (Ферма-Эйлерийн теорем гэх нь ч бий) нь хэрвээ n болон a нь харилцан анхны, эерэг бүхэл тоонууд, φ(n) нь Эйлерийн функц байвал

a^{\varphi (n)} \equiv 1 \pmod{n}

болно гэдгийг баталдаг. Үүнийг анх 1736 онд Леонард Эйлер тодорхойлж, баталжээ[1].

Эйлерийн теоремын урвуу нь бас биелнэ: Хэрвээ дээрх нөхцөл биелж байвал а болон n нь харилцан анхны байх ёстой. Энэхүү теором нь Фермагийн бага теоремын ерөнхий нэгтгэл бөгөөд улам өргөжүүлсэн Кармайклын теорем гэж бий.

Уг теоремыг ашиглан олон зэрэгт бүхий тоог модуль n-ээр тун хялбархан бууруулдаг. Жишээ нь: 7222 тооны сүүлийн цифрийг олох буюу 7222 (mod 10)-г олох хэрэгтэй гэж үзье. 7 болон 10 нь харилцан анхны тоонууд бөгөөд φ(10) = 4. Тэгэхээр Эйлерийн теорем ёсоор 74 ≡ 1 (mod 10) бөгөөд бид 7222 ≡ 74×55 + 2 ≡ (74)55×72 ≡ 155×72 ≡ 49 ≡ 9 (mod 10) гэсэн үр дүнд хүрч байна. Ерөнхийдөө энэ нь a-гийн зэрэгтийн модуль n (а болон n харилцан анхны үед)-ийн утгыг багасгаж байгаа бөгөөд бидэнд: Хэрвээxy (mod φ(n)) бол axay (mod n) байх ямар нэгэн модуль φ(n) шаардлагатай.

Эйлерийн теорем нь RSA нууцлалын системийн үндсийг бүрдүүлдэг: энэхүү систем дэх нууцлал болон тайлал нь хамтдаа ямар нэгэн эерэг бүхэл тооk-гийн хувьд анхны утгыг kφ(n)+1 зэрэг дэвшүүлсэнтэй тэнцүү хэмжээний утгатай байдаг. Ийнхүү Эйлерийн теорем нь тухайн тайлагдсан үр дүн нь эх хувилбартайгаа ижил гэдгийг илэрхийлж байдаг.

Баталгаа[засварлах]

1. Эйлерийн теоремыг бүлгийн онолын ойлголтуудад тулгуурлан батлах боломжтой[2]:

n-тэй харилцан анхны, (mod n)-ийн үлдэгдлүүдийн анги нь үржих үйлдлийн хувьд бүлэг үүсгэнэ. Лагранжийн теорем ёсоор төгсгөлөг бүлгийн дурын дэд бүлэг уг бүлгийн үйлдлийн хувьд битүү байдаг, манай тохиолдолд φ(n) нь тийм болно. Хэрэв a нь n-тэй харилцан анхны дурын тоо бол a нь мөнхүү үлдэгдлүүдийн ангид харьяалагдах тул түүний зэргүүд болох a, a2, ..., ak ≡ 1 (mod n) нь дэд бүлгийг үүсгэнэ. Лагранжийн теорем ёсоор k нь φ(n)-д хуваагдах ёстой, өөрөөр хэлбэл kM = φ(n) байх бүхэл тоо M олдох ёстой. Ийнхүү


a^{\varphi(n)} = 
a^{kM} = 
(a^{k})^M \equiv 
1^M = 
1 \pmod{n}
болж теорем батлагдлаа.

Хэрэглээ[засварлах]

RSA RSA_(алгоритм) алгоритм нь эйлерийн томёог ашигладаг хамгийн том жишээ болж чадна. Энэ алгоритм нь нууцлалтайгаар өгөгдөл дамжуулахад тохиромжтой бөгөөд аюулгүй байдлын хувьд найдвартай ба түлхүүр солилцоход хялбар алгоритм юм. RSA алгоритм нь гурван алхамаас бүрдэнэ.Үүнд: 1. Түлхүүрүүдийг үүсгэх 2. Шифрлэх 3. Тайлах

Түлхүүр үүсгэх. Эхлээд санамсаргүй 2 ширхэг p,q гэсэн анхны тоо сонгон авна жишээ нь p=11, q=3. N тоо нь дээрх 2 тооны үржвэр байна жишээ нь n = pq = 11*3 = 33 phi тоо нь p болон q тооноос нэг нэгийг хассаны үржвэр жишээ нь phi = (p-1)(q-1) = 10*2 = 20 E буюу нийтийн түлхүүрээ сонгон авна жишээ нь e=3 D буюу хувийн түлхүүрийг e*d-г phi тоонд хуваагаад гарсан үлдэгдэл нь 1 тэй тэнцүү байх тийм d тоог олно ed ≡ 1 (mod phi) d=7 гэж олдож байна.

Шалгаж үзье: ed-1 = 3*7 - 1 = 20 Public key = (n, e) = (33, 3) Private key = (n, d) = (33, 7) гэж түлхүүрүүд олдож байна.

Шифрлэх. Шифр хийхдээ m буюу message нь m = 7 гэж үзвэл , c = m^e mod n => 343 mod 33 => 13. Cipher буюу шифрлэгдсэн тоо C=13 болно.

Тайлах. Шифр тайлахдаа m' = c^d mod n => 137 mod 33 => 62748517 mod 33 => 7. Оролтын message нь m=7 гарж зөв тайлагдаж байна.

Эшлэл, зүүлт[засварлах]

  1. Вайшштайн, Эрик В., "Euler's Totient Theorem" (MathWorld).
  2. Ireland & Rosen, corr. 1 to prop 3.3.2