Анхны тоон алгоритм

M. Munkhbagana

• 2024-12-14

Анхны тооны ойлголт нь эртний Грекийн математикчдаас эхлэлтэй. Тэр дундаа Эртний математикч Евклид (Euclid) анхны тоог хязгааргүй олон байдгийг баталсан бөгөөд энэ нь “Евклидийн теорем” хэмээн нэрлэгдсэн. Анхны тоог илүү нарийвчлан судлах ажил XVII зуунаас эхлэн хурдацтай хөгжиж, Лейбниц, Эйлер зэрэг суут хүмүүс чухал хувь нэмэр оруулсан байдаг ба энэхүү нийтлэл нь анхны тоог хэрхэн олох аргуудын талаар өгүүлнэ.

Анхны тооны судалгааны үүслийн онцлох мөчүүд:

1. Евклидийн теорем: Анхны тоонууд хязгааргүй олон гэдгийг баталсан.
2. Эратосфенийн арга: Анхны тоог олох аргачлалыг анх зохиосон.
3. Риманы таамаглал (1859): Анхны тооны тархалттай холбоотой хамгийн чухал нээлтүүдийн нэг.

Анхны тооны талаарх мэдлэгийн өргөжилт нь орчин үеийн математикийн салбаруудад, ялангуяа криптограф болон алгоритмын хөгжүүлэлтэд ихээхэн нөлөөлсөн. Дээр дурдсанчлан анхны тоог хязгааргүй гэж үздэг ба одоогоор хамгийн сүүлд нээгдсэн хамгийн том анхны тоо нь 2018 оны 12-р сарын 7-нд олдсон бөгөөд энэ нь 2^{82,589,933 − 1} хэлбэрийн Мерсенний анхны тоо юм. Энэхүү тоо нь 24,862,048 оронтой.

Анхны тоо шалгах аргууд

Анхны тоог тодорхойлох хэд хэдэн арга бий. Доор анхны тоог олох үндсэн аргуудыг онолын хувьд тайлбарлав.

1. Энгийн хуваагч шалгах арга (Trial Division)

Энгийн хуваагч шалгах арга нь анхны тоог олох хамгийн хялбар арга юм. Энэ арга нь тоог 2-оос эхлэн өөрийнх нь квадрат язгуур хүртэлх бүх тоонд хуваагдах эсэхийг шалгадаг. Хэрэв тухайн завсарт нэг ч тоонд хуваагдахгүй бол тухайн тоог анхны тоо гэж үзнэ.

2. Эратосфенийн арга (Sieve of Eratosthenes)

Эратосфенийн арга нь нэг хязгаар хүртэлх бүх тооны анхны тоонуудыг олох хамгийн үр дүнтэй аргуудын нэг юм. Энэ арга нь дарааллын тоонуудыг шалгаж, тухайн тооноос их үржвэрүүдийг хасах зарчмаар ажилладаг.

3. Миллер-Рабиний арга (Miller-Rabin Test)

Миллер-Рабиний шалгах арга нь магадлалын үндэстэй бөгөөд том тоонуудыг шалгахад тохиромжтой. Энэ арга нь криптографт ашиглагдах ба тоог олон удаа шалгах замаар анхны тоо байх магадлалыг тодорхойлдог.

Анхны тоо шалгах алгоритм

Анхны тоон алгоритмуудын хамгийн түгээмэл арга болох энгийн шалгах арга буюу trial division-г тайлбарлая. Энэхүү арга нь тухайн тоог 2-с эхлэн өөрийнх нь квадрат язгуур хүртэлх бүх тоонд хуваагдах эсэхийг шалгадаг. Хэрэв нэг ч тоонд хуваагдахгүй бол тухайн тоо анхны тоо гэж үзнэ.

Алгоритм:

1. Тоог 2-той тэнцүү эсэхийг шалгана. Хэрэв тэнцүү бол анхны тоо.
2. Тоо нь 2-т хуваагдаж байвал анхны тоо биш.
3. Тоог 3, 4, 5, 6, …, √n хүртэлх бүх тоонд хуваагдах эсэхийг шалга.
4. Хэрэв нэг-ч тоонд хуваагддаггүй бол тухайн тоо анхны тоо.

Жишээ: 29 тоог анхны эсэхийг шалгая.

1. 29 тоог 2-той тэнцүү эсэхийг шалгана.
   • 29 ≠ 2 тул шалгалтыг үргэлжлүүлнэ.
2. 29 тоо нь 2-т хуваагдаж байгааг шалгана.
   • 29 % 2 = 1 (үлдэгдэлтэй) → Тиймээс 29 нь 2-т хуваагдахгүй.
3. 3, 4, 5, …, √29 хүртэлх бүх тоонд хуваагдах эсэхийг шалгана.
   • √29 ≈ 5.38 тул 3, 4, 5 хүртэл шалгана:
     • 29 % 3 = 2 (үлдэгдэлтэй) → 3-т хуваагдахгүй.
     • 29 % 4 = 1 (үлдэгдэлтэй) → 4-т хуваагдахгүй.
     • 29 % 5 = 4 (үлдэгдэлтэй) → 5-т хуваагдахгүй.
4. 29 нь дээрх бүх тоонд хуваагдсангүй.
   • Тиймээс 29 нь анхны тоо.

Анхны тооны хэрэглээ

Анхны тоонуудыг дараах салбаруудад өргөн ашигладаг:

1. Криптограф: RSA болон эллиптик муруйн (ECC) криптограф нь анхны тоон дээр үндэслэдэг. Жишээ нь, шифрлэлтийн түлхүүр үүсгэх.
2. Математик судалгаа: Тооны хуваагч олох, анхны тооны тархалтыг судлах зэрэгт.
3. Шинжлэх ухаан: Тооцоолол, өгөгдлийн шахалт, хиймэл оюун ухаан.

Анхны тоонууд нь математик болон мэдээллийн технологийн салбарт онцгой чухал байр суурь эзэлдэг ба криптограф, өгөгдөл шахалт,тоон дүн шинжилгээ зэрэг олон салбарт үндэс суурь болж өгдөг. Анхны тоог илрүүлэх арга нь эрт дээр үеэс судлагдаж ирсэн бөгөөд энэ чиглэлд янз бүрийн алгоритмууд одоог хүртэл тасралтгүй хөгжүүлэгдсээр байна.