Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish Faktorlash muammosini bartaraf etuvchi algoritmlar.
Faktorlash muammosi deb nimaga aytiladi
Pollard usuli nimaga asoslanadi.
LAVOBLAR
Faktorlash sonini tub koʼpaytuvchilarga ajratish jarayoni. Masalan, . Faktorlash murakkab hisoblashga ega vazifa sanaladi. Kriptografiyada RSA shifrlash algoritmida, elleptik egri chiziqlarda va kvant kriptografiyasida qoʼllaniladi. Faktorlash murakkablik darajasiga koʼra ikki turga ajratiladi: Eksponent va subeksponent. Eksponent algoritmlar yoki ni hisoblash murakkabligiga asoslanadi. Bu yerda, faktorlanadigan sonini 1 dan gacha ketma-ket boʼlish talab etiladi. Odatda tub sonlar jadvali olinadi va katta sonlarni ( gacha) tekshirish amalga oshiriladi. Juda katta sonlarda qoʼllanilishi hisoblash tezligini pasayishiga olib keladi. Yuqorida keltirilgan Boʼluvchilarni tahmin qilish usuli, Ferma, Pollard, Lenstr, Leman va boshqa shu kabi usullarni keltirish mumkin va ular asosida faktorlash muammosini yechish mumkin.
Pollard usuli. Ushbu usul Ro-algoritm yoki –algoritm nomlari bilan ham keng tarqalgan. Faktorlash muammosini yechishda takrorlanuvchi funksiya ketma-ketligidagi sikllarga va tugʼilgan kun paradoksiga asoslanadi. U ikki sonning koʼpaytmasidan tashkil topgan sonlarning faktorlash muammosini yechishda samarali. Uning murakkabligi orqali baholanadi – algoritm sonlardan iborat ketma-ketlikni tashkil etadi va qaysidir sonidan boshlab siklni hosil qiladi. Hosil boʼlgan sikl koʼrinishida boʼlganligi uchun – algoritm deb nomlanadi.
2.1-rasm. –algoritm ko’rinishi
Misol. 8051 sonini –algoritm asosida faktorlash muammosini yechish.
asosida
, ,
|
i
|
|
|
|
1.
|
5
|
26
|
1
|
2.
|
26
|
7474
|
1
|
3.
|
677
|
871
|
97
|
asosida
, ,
|
I
|
|
|
|
1.
|
7
|
52
|
1
|
2.
|
52
|
1442
|
1
|
3.
|
2707
|
778
|
1
|
4.
|
1442
|
3932
|
83
|
Demak, va sonlari 8051 sonining umumiy bo’luvchilari;-Algoritm ni hisoblaydi, agar uning qiymati tub son bo’lmasa, hisoblash davom etadi.
Subeksponent algoritmlar belgili murakkablikka asoslangan.
.
Bu yerda, – fatorlash talab etiladigan son, va – konstanta. Misol sifatida Dikson algoritmini keltirish mumkin. Ushbu algoritm tenglikdan va sonlarini hisoblashga qaratilgan. Bu yerda, .
Pollard usuli. Ushbu usul Ro-algoritm yoki –algoritm nomlari bilan ham keng tarqalgan. Faktorlash muammosini yechishda takrorlanuvchi funksiya ketma-ketligidagi sikllarga va tugʼilgan kun paradoksiga asoslanadi. U ikki sonning koʼpaytmasidan tashkil topgan sonlarning faktorlash muammosini yechishda samarali. Uning murakkabligi orqali baholanadi – algoritm sonlardan iborat ketma-ketlikni tashkil etadi va qaysidir sonidan boshlab siklni hosil qiladi. Hosil boʼlgan sikl koʼrinishida boʼlganligi uchun – algoritm deb nomlanadi.
2.1-rasm. –algoritm ko’rinishi
Misol. 8051 sonini –algoritm asosida faktorlash muammosini yechish.
asosida
, ,
|
i
|
|
|
|
1.
|
5
|
26
|
1
|
2.
|
26
|
7474
|
1
|
3.
|
677
|
871
|
97
|
asosida
, ,
|
I
|
|
|
|
1.
|
7
|
52
|
1
|
2.
|
52
|
1442
|
1
|
3.
|
2707
|
778
|
1
|
4.
|
1442
|
3932
|
83
|
Demak, va sonlari 8051 sonining umumiy bo’luvchilari;-Algoritm ni hisoblaydi, agar uning qiymati tub son bo’lmasa, hisoblash davom etadi.
Subeksponent algoritmlar belgili murakkablikka asoslangan.
.
Bu yerda, – fatorlash talab etiladigan son, va – konstanta. Misol sifatida Dikson algoritmini keltirish mumkin. Ushbu algoritm tenglikdan va sonlarini hisoblashga qaratilgan. Bu yerda, .
Do'stlaringiz bilan baham: |