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

Чөлөөт нэвтэрхий толь — Википедиагаас
Jump to navigation Jump to search


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

Тооны ухаанд Euler's theorem (Fermat-Euler theorem эсвэл Euler's totient theorem гэх нь ч бий) нь хэрвээ n болон a нь боломжит бүхэл тоогоор өгөгдсөн φ(n) нь Euler's totient функц байвал болно гэдгийг баталдаг. Үүнийг анх 1736 онд Leonhard Euler туршин баталжээ. Euler's Theorem-д нэгэн урвуу хамаарал байдаг: Хэрвээ дээр дурдсан конгруэнт чанар (Харьцуулах боломж) нь үнэн байвал а болон n коприм (coprime) байх ёстой. Энэхүү теором нь Ферматийн жижиг теоромуудын ерөнхий нэгтгэл бөгөөд энэхүү теоремийг Кармикел (Carmichael)-ийн теоремоор баталдаг. Уг теором нь их хэмжээний утга агуулсан модуль N-ийг хялбараар бууруулахад ашиглагдах боломжтой. Жишээ нь: 7222 (modul 10)-ийн 10тын бутархайд байрлуулах нэг цифр хайж байгаа гэж авч үзье л дээ. Анхааруулахад 7 болон 10 коприм ба φ(10) = 4. Тэгэхээр Euler's theorem-ийн үр дүн нь 74 ≡ 1 (mod 10) бөгөөд бид 7222 ≡ 74×55 + 2 ≡ (74)55×72 ≡ 155×72 ≡ 49 ≡ 9 (mod 10) гэсэн үр дүнд хүрч байна. Ерөнхийдөө энэ нь модуль n (а болон n коприм үед)-ийн утгыг багасгаж байгаа бөгөөд бидэнд if x ≡ y (mod φ(n)), then ax ≡ ay (mod n)-ийн зэрэг дэвшүүлэгчид ашиглагдах ямар нэгэн modulo φ(n) шаардлагатай. Euler's theorem нь RSA нууцлалын системийн үндсэн форм төдийгүй нууцлал болон тайлал нь зарим боломжит бүхэл тоо болох К-д жинхэнэ эх сурвалж kφ(n)+1-р зэрэг дэвшүүлж байгаа энэхүү системд хагацашгүй нийлбэр болдог. Тиймээс Euler's theorem нь тухайн тайлагдсан үр дүн нь эх хувилбартайгаа ижил гэдгийг илэрхийлж байдаг. RSA RSA нь нууц бичээс тайлалтанд зориулсан нийтийн түлхүүр бөгөөд их хэмжээний бүхэл тоог үржүүлэхэд тулгарах хүндрэлийг бууруулахад зориулагдсан. RSA-г 1977 онд Ron Rivest, Adi Shamir болон Leonard Adleman нар туршин нэвтрүүлсэн. Английн математикч Clifford Cocks 1973 онд эквивалент(адил тэнцүү) системийг бүтээсэн бөгөөд энэ нь 1997 он хүртэл ашиглагдаж байжээ. Баталгаа 1. Euler's theorem нь группуудын онолуудаас бий болсон үзэл баримтлалаас үндэслэгдэн батлагдсан байх боломжтой. Үүний нэг болох Lagrange's theorem нь φ(n) тохиолдолд нийт групп болон түүнээс хуваагдаж гарсан хуваагдал групп ба аливаа дэд бүлгийн дарааллыг баталж байдаг. Хэрвээ а нь классын үлдэгдлийн аль нэгд хамаагдах ямарваа нэгэн коприм тоо байвал үүний утга болох a, a2, ..., ak ≡ 1 (mod n) нь дэд бүлэг болдог. Lagrange's theorem нь К φ(n)-ийн хуваагдал байх ёстой бөгөөд бүхэл утга болом М нь kM = φ(n)-ээс их байх ёстой гэдгийг хэлж өгдөг. Томъёолбол:


ба цуцлах дүрмийг ашиглан өгөгдсөн Euler's theorem-ийг цуцалж болно. Томъёолбол: