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

Тооны онолд Эйлерийн теорем нь хэрвээ n болон a нь харилцан анхны, эерэг бүхэл тоонууд, байвал

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

байна. Үүнийг анх 1736 онд Леонард Эйлер тодорхойлж, баталжээ. Уг теоремыг ашиглан олон зэрэгт бүхий тоог модуль n-ээр тун хялбархан бууруулдаг. Жишээ нь: 7²²² тооны сүүлийн цифрийг олох буюу 7²²² (mod 10)-г олох хэрэгтэй гэж үзье. 7 болон 10 нь харилцан анхны тоонууд бөгөөд φ(10) = 4.(7-ын нэг зэрэг нь 7, 7-ын хоёр зэргийн төгсгөлийн цифр бүр

нь 9, 7-ын гурван зэргийн төгсгөлийн цифр нь 3, 7-ын дөрвөн зэргийн төгсгөлийн цифр нь 1 байдаг, 7-ын дараагийн зэргүүдээс эхэлэн сүүлийн цифр нь 7,9,3,1 давтагддаг учраас ) Тэгэхээр Эйлерийн теорем ёсоор 74 ≡ 1 (mod 10) бөгөөд бид 7222 ≡ 74×55 + 2 ≡ (74)55×72 ≡ 155×72 ≡ 49 ≡ 9 (mod 10) болно.

Баталгаа

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

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

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

Хэрэглээ

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