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

Қадамлар 2дан k–1 гача
Бу қадам ва 𝑘 − 1 қадамгача 1- қадам каби бўлади.. Бу қадам муҳим эмас. Агар биз уни амалга оширсак ва натижа олмасак, у бизга наф бермайди. Агар бу қадам натижаси (-1) бўлса, демак Ферма тестидан ўтади, лекин олдинги қадам натижвси сифатида олинмаса, квадрат илдиз тестидан ўта олмайди, Агар араён қадам охиригача тўхтамаса,биз 𝑛 ни мураккаб сон деб эълон қиламиз.

Тест Миллера-Рабина требует от 0 до k–1..
Алгоритм 12.2 Рабин Миллер тести учун псевдокодни кўрсатади..




Ҳар сафар Миллер-Рабин тести ҳар бир рақам учун ўтказилганда, "унчалик катта бўлмаган" натижани олиш эҳтимоли 1/4 ни ташкил қилади. Агар 𝑚 синовдан ўтган ўлса, тестнинг туб бўлмаслик бермаслик эҳтимоли (1/4) 𝑚..
ҳолда k – 1 = 0 ва биз фақат инитализация қадамини бажаришимиз керакҳолос:

T = 2¹³ mod 27 = 11 mod 27. Лекин алгоритм сифатида бирор қадам ҳам иш бажармади,

ечимни ишлаб чиқамиз “мураккаб сон”.

Хулоса:

Мен ушбу мустаыил ишимни бажариш мобайнида туб сонлар, сонларни тубликка текшириш тyрисида жуда кyп маoлумот билиб олдим ва yз билимимни янада мустахкамлаб олдим. Яна шуни хам такидлашим керакки туб сонлар каерларда ва асосан нима максадларда ишлатилишини ва бу сонларнинг мен билганданда янада куп функсиялари борлиги мени жуда хайратга солди.


Фойдаланиладиган асосий дарсликлар ва ўқув
кўлланмалар рўйхати

1. ФУНДАМЭНТАЛС ОФ CРЙПТОЛОГЙ , ПУБЛИШЭРС, Ъенк C.А. ван Тилборг. КЛУWЭР АCАДЭМИC

2. Фороузан Б.А Криптография и безопасность сетей: Учебное
пособие/фороузан Б.А.; перюсюанглюпод ред А.Н. Берлинаю- Мю:Унивеситет
Информационных Технологий: БИНОМ. Лаборатория знаний, 2010.-784с
3. W. Сталлингс, Cрйптограпъй анд Нетwорк Сеcуритй Принcиплес анд Праcтиcес Фоуртъ Эдитион, Пеарсон Эдуcатион, Прентиcе Ъалл, 2010
4. Акбаров Д., Хасанов П., ХасановХ., Ахмедова О. Криптографиянинг
математик асослари. Ўқув қўлланма. – Тошкент, 2010.