4-amaliy ish

Misol 2. 𝑝 = 19 ni Solovey-Shtrassen algoritmi bilan tublikka sinaymiz:
𝑘 = 1, 2 ≤ 𝑎 ≤ 𝑝 − 1 oraliqdan tasodifiy 𝑎 = 11 tanlaymiz.
𝐸𝐾𝑈𝐵(а, р) = 𝐸𝐾𝑈𝐵 (11,19) = 1.

Demak, 𝑎^(𝑝−1)/2 ≡
^𝑎 𝑚𝑜𝑑 𝑝 shartni bajarilishini tekshiramiz.

)

(
𝑝

• 
  
  )
  
  (
  𝑠 = ^𝑎 = ( ⁵ )
  

_{= 1, 𝑎}(𝑝−1)/2 _{= 5}(19−1)/2 _{(𝑚𝑜𝑑 19) = 1}

𝑝 19

Taqqoslasak, 𝑎^(𝑝−1)/2 =
^𝑎 ekanligi kelib chiqadi.

)

(
𝑝

Bundan quyidagicha xulosaga kelish mumkin: 19 son 1 − 2⁻² ehtimollik bilan tub son bо‘ladi.

Rаbin-Miller testi

Rаbin-Miller testi kuchli psevdotub konsepsiyasigа аsoslаngаn ehtimolli tublikkа tekshiruvchi testlаridаndir.
Rabin – Millerning katta sonlarni tublikka sinash testi hozirgi kunda nosimmetrik kriptotizimlarda modul hosil qilishda keng qо‘llaniladi. Bu algoritm kuchli psevdotub sonlarni sinash algoritmi sifatida tan olingan. У 𝑛 − 1 ни, яъни модулни битта камайтирилган қийматини 2^𝑠 ∗ 𝑟 кўринишда ифодалашга асосланган. Бунда 𝑠 ─ 𝑛 − 1 ни иккига бўлинишлар сони, 𝑟 – тоқ сон.
“𝑛 - soni tubmi-?” degan savolga, “tub” yoki “murakkab” degan javob olishga qaratilgan bо‘ladi.
Ushbu test quyidagi ketma-ketlikda amalga oshiriladi:

• 
  𝑛 − 1 = 2^𝑠 ∗ 𝑟 kо‘rinishda yozib olinadi, bunda 𝑟 - toq son;
  
• 
  2 ≤ 𝑎 ≤ 𝑛 − 1 2 ≤ 𝑎 ≤ 𝑛 − 1 shartni qanoatlantiruvchi а son tasodifiy tanlanadi;
  
• 
  𝑦 = 𝑎^𝑟𝑚𝑜𝑑 𝑛 hisoblanadi;
  
• 
  Agar (у = 1 𝑦𝑜𝑘𝑖 𝑢 = 𝑛 − 1) bo‘lsa, u holda keyingi iterasiyaga o‘tish;
  
• 
  𝑎²𝑡^𝑟 ≡ −1 (𝑚𝑜𝑑 𝑛) hisoblanadi;
  
• 
  𝑡 < 𝑠 𝑚𝑎𝑟𝑡𝑎, 𝑦 = 𝑦²𝑚𝑜𝑑 𝑛;
  
• 
  Agar (у = 1) bо‘lsa, u holda “murakkab son” qaytariladi;
  
• 
  Agar ⁽𝑦 ≠ 𝑛 − 1⁾ bо‘lsa, u holda “murakkab son” qaytariladi;
  
• 
  Aks holda “Tub son” qaytariladi.