Мавзу: Сонларни тубликка текшириш алгоритмлари. Ферма ва Рабин Миллер тести. Режа

Рабин-Миллер тести
Туб сонларни аниқлайдиган Рабин Миллер тести Ферма ва Квадрат илдиз тестларининг комбинациясидан иборат. Бу кучли псевдотасодифий сонларни топишнинг элегант усулидир (кучли эҳтимоллик билан туб сон). Бу тестда биз тоқ сон 𝑚 ни ва 2 нинг даражасини топиш учун сифатида 𝑛 − 1ни ёзиб оламиз .

Фермат тестида, а сосда, у қуйида кўрсатилгандек ёзилиши мумкин.

Фермага асосланган сонни тубликка текшириш тести

Бошқача қилиб айтганда, биз бир қадамда ан-1 (мод н) ни ҳисоблашнинг ўрнига к + 1 босқичда бажарамиз. Ушбу дастурнинг афзаллиги нимада? Афзаллиги шундаки, квадрат илдиз синовини ҳар қадамда бажариш мумкин. Агар квадрат илдиз шубҳали натижаларни кўрсатса, биз тўхтатамиз ва н композит сонни эълон қиламиз. Ҳар бир қадамда, Фермат тести ва квадрат илдиз синови, агар у қониқарли бўлса, қўшни барча жуфтликлар бўйича қониқ

Инициализация
Асосни танлаймиз ва T = am ни танлаймиз, в который m = (n – 1) / 2^k. a. Агар 𝑇 натижа +1 ёки -1 га тенг бўлса, 𝑛 ни кучли псевдотубсон деб эълон қиламиз ва жараённи тўхтатамиз. Биз 𝑛 сонини Ферма ва квадрат илдиз тестидан ўтди дея айтишимиз мумкин.
b. Агар T сони бошқа натижага тенг бўлса, биз 𝑛 сонин туб сон ёки мураккаб сон эканлигига ишонч ҳосил қила олмаймиз. Демак, жараён кейинги қадамда давом этади.
1 Қадам
Т сонини квадратга кўтарамиз. a. Агар натижа +1 бўлса, биз аниқ биламизки, Фермат тести ўтган, чунки Т кейинги
синовлар учун 1 бўлиб қолади. Аммо квадрат илдиз синови муваффақиятсиз тугади. Ушбу босқичда Т 1 бўлганлиги ва олдинги босқичда (аввалги босқичда тўхтамаганимиз сабаби) бошқача маънога эга бўлганлиги сабабли н мураккаб объект деб эълон қилинади ва жараён тўхтайди. b. Агар натижа (-1)га тенг бўлса, 𝑛 чекли ҳисобда Ферма тестидан ўтишини биламиз. Биламизки, у квадрат илдиз синовидан ҳам ўтади, чунки бу қадамда 𝑇 натижа (-1)га тенг бўлади ва кейинга қадамда 1 бўлади. Биз 𝑛 ни кучли псевдотасодифий сон деб эълон қиламиз ва жараённи тўхтатамиз. c. Агар Т яна қандайдир натижани берса, туб сон бўлади деб ишонч ҳосил қила олмаймиз ва жараён кейинги қадамда давом этади.