Pollards rho algoritmi - Pollards rho algorithm

Pollardning rho algoritmi bu algoritm uchun tamsayı faktorizatsiyasi. U tomonidan ixtiro qilingan Jon Pollard 1975 yilda.[1] U faqat oz miqdordagi bo'sh joyni ishlatadi va uning kutilayotgan ishlash vaqti eng kichigi kvadrat ildiziga mutanosibdir asosiy omil ning kompozit raqam faktorizatsiya qilinmoqda.

Asosiy g'oyalar

Faraz qilaylik, sonni faktorizatsiya qilishimiz kerak , qayerda ahamiyatsiz omil. Polinom moduli , deb nomlangan (masalan, ), a hosil qilish uchun ishlatiladi yolg'on tasodifiy ketma-ketlik: Boshlang'ich qiymati, masalan, 2 tanlanadi va ketma-ketlik shunday davom etadi , , va hokazo ketma-ketlik boshqa ketma-ketlik bilan bog'liq . Beri oldindan ma'lum emas, bu ketma-ketlikni algoritmda aniq hisoblash mumkin emas. Shunga qaramay, unda algoritmning asosiy g'oyasi yotadi.

Ushbu ketma-ketliklar uchun mumkin bo'lgan qiymatlar soni cheklangan bo'lgani uchun, ikkalasi ham ketma-ketlik, bu mod va ketma-ketlik oxir-oqibat takrorlanadi, garchi ikkinchisini bilmasak ham. Ketma-ketliklar o'zlarini tasodifiy sonlar kabi tutadi deb taxmin qiling. Tufayli tug'ilgan kungi paradoks, soni takrorlashdan oldin bo'lishi kutilmoqda , qayerda mumkin bo'lgan qiymatlar soni. Shunday qilib, ketma-ketlik ehtimol ketma-ketlikdan ancha oldin takrorlanadi . Bir marta ketma-ketlik takrorlangan qiymatga ega bo'lsa, ketma-ketlik aylanadi, chunki har bir qiymat faqat oldingisiga bog'liq. So'nggi velosipedning ushbu tuzilishi "Rho algoritmi" nomini keltirib chiqaradi, chunki yunoncha belgi shakliga o'xshashligi tufayli , va boshqalar a-dagi tugunlar sifatida ifodalanadi yo'naltirilgan grafik.

Yunoncha r harfiga o'xshash tsikl diagrammasi

Bu aniqlandi Floydning tsikllarni topish algoritmi: ikkita tugun va (ya'ni, va ) saqlanadi. Har bir qadamda biri ketma-ketlikda keyingi tugunga, ikkinchisi esa ikkita tugun bilan oldinga siljiydi. Shundan so'ng, tekshiriladimi yoki yo'qmi . Agar u 1 ga teng bo'lmasa, unda takrorlash mavjudligini anglatadi ketma-ketlik (ya'ni . Bu ishlaydi, chunki agar bilan bir xil , o'rtasidagi farq va albatta ko'paytmasi . Garchi bu har doim oxir-oqibat sodir bo'lsa ham, natijada Eng katta umumiy bo'luvchi (GCD) ning bo'luvchisi tashqari 1. Bu bo'lishi mumkin o'zi, chunki ikkita ketma-ketlik bir vaqtning o'zida takrorlanishi mumkin. Bunday holda (odatiy bo'lmagan holda) algoritm ishlamay qoladi va uni boshqa parametr bilan takrorlash mumkin.

Algoritm

Algoritm uning kirishlari sifatida qabul qilinadi n, hisobga olinadigan butun son; va , in polinom x hisoblangan modul n. Asl algoritmda, , ammo hozirgi kunda undan foydalanish keng tarqalgan . Chiqish yoki ahamiyatsiz omil nyoki muvaffaqiyatsizlik. U quyidagi amallarni bajaradi:[2]

    x ← 2 y ← 2 d ← 1 esa d = 1: x ← g (x) y ← g (g (y)) d ← gcd (| x - y |, n) agar d = n: qaytish muvaffaqiyatsizligi    boshqa:        qaytish d

Bu yerda x va y ga mos keladi va asosiy g'oya haqidagi bo'limda. E'tibor bering, ushbu algoritm ham noan'anaviy omilni topa olmaydi n kompozitdir. Bunday holda, usulni 2 dan boshqacha boshlang'ich qiymati yoki boshqasidan foydalangan holda qayta urinib ko'rish mumkin .

Faktorizatsiya misoli

Ruxsat bering va .

menxyGCD (|xy|, 8051)
15261
22674741
367787197
4747414811

97 - bu ahamiyatsiz omil 8051. Boshlang'ich qiymatlari x = y = 2 97 o'rniga kofaktorni berishi mumkin (83). Buni aniq qilish uchun yuqorida bitta qo'shimcha takrorlash ko'rsatilgan y ga nisbatan ikki baravar tezroq harakat qiladi x. E'tibor bering, takrorlangandan keyin ham GCD 1 ga qaytishi mumkin.

Variantlar

1980 yilda, Richard Brent rho algoritmining tezroq variantini nashr etdi. U Pollard bilan bir xil asosiy g'oyalarni qo'llagan, ammo tsiklni aniqlashning boshqa usulini almashtirgan Floydning tsikllarni topish algoritmi bilan bog'liq Brent tsiklini topish usuli.[3]

Pollard va Brent tomonidan yanada takomillashtirilgan. Agar shunday bo'lsa, ular buni kuzatdilar , keyin ham har qanday musbat son uchun . Xususan, hisoblash o'rniga har qadamda buni aniqlash kifoya ketma-ket 100 mahsuloti sifatida atamalar modul , so'ngra bitta hisoblang . Katta tezlikni 100 ga etkazish gcd qadamlar 99 ta ko'paytma moduli bilan almashtiriladi va bitta gcd. Ba'zida bu takrorlanadigan omilni kiritish orqali algoritmning ishdan chiqishiga olib kelishi mumkin, masalan kvadrat. Ammo keyin avvalgisiga qaytish kifoya gcd muddat, qaerda va u erdan oddiy r algoritmidan foydalaning.

Ilova

Algoritm kichik faktorli raqamlar uchun juda tez, ammo barcha omillar katta bo'lgan hollarda sekinroq. R algoritmining eng ajoyib yutug'i -ni faktorizatsiya qilish edi Fermat raqami F8 = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321 [4]. R algoritmi yaxshi tanlov edi F8 chunki asosiy omil p = 1238926361552897 boshqa omilga qaraganda ancha kichik. Faktorizatsiya a da 2 soat davom etdi UNIVAC 1100/42.[4]

Misol n = 10403 = 101 · 103

Bu erda biz yana bitta variantni kiritamiz, bu erda faqat bitta ketma-ketlik hisoblangan va gcd tsiklni aniqlaydigan tsikl ichida hisoblab chiqilgan.

C kod namunasi

Quyidagi kod namunasi boshlang'ich qiymati bilan 10403 ning 101 omilini topadi x = 2.

# shu jumladan <stdio.h># shu jumladan <stdlib.h>int gcd(int a, int b) {    int qoldiq;    esa (b != 0) {        qoldiq = a % b;        a = b;        b = qoldiq;    }    qaytish a;}int asosiy (int arg, char *argv[]) {    int raqam = 10403, pastadir = 1, hisoblash;    int x_fixed = 2, x = 2, hajmi = 2, omil;    qil {        printf("---- tsikl% 4i ---- n", pastadir);        hisoblash = hajmi;        qil {            x = (x * x + 1) % raqam;            omil = gcd(abs(x - x_fixed), raqam);            printf("hisoblash =% 4i x =% 6i omil =% i n", hajmi - hisoblash + 1, x, omil);        } esa (--hisoblash && (omil == 1));        hajmi *= 2;        x_fikslangan = x;        pastadir = pastadir + 1;    } esa (omil == 1);    printf("omil% i n", omil);    qaytish omil == raqam ? EXIT_FAILURE : EXIT_SUCCESS;}

Yuqoridagi kod algoritmning rivojlanishini va oraliq qiymatlarni ko'rsatadi. Oxirgi chiqish satri "omil 101" bo'ladi. Kod faqat kichik test qiymatlari uchun ishlaydi, chunki x kvadrat ichida butun sonli ma'lumotlar turlarida toshma paydo bo'ladi.

Python kod namunasi

dan itertools Import hisoblashdan matematik Import gcdraqam, x = 10403, 2uchun tsikl yilda hisoblash(1):    y = x    uchun men yilda oralig'i(2 ** tsikl):        x = (x * x + 1) % raqam        omil = gcd(x - y, raqam)        agar omil > 1:            chop etish("omil", omil)            Chiqish()

Natijalar

Keyingi jadvalda uchinchi va to'rtinchi ustunlar faktor qilmoqchi bo'lgan shaxsga ma'lum bo'lmagan maxfiy ma'lumotlarni o'z ichiga oladi pq = 10403. Ular algoritm qanday ishlashini ko'rsatish uchun kiritilgan. Agar biz boshlasak x = 2 va algoritmga rioya qiling, biz quyidagi raqamlarni olamiz:

qadam
22220
52521
2622622
6772671263
5982693264
39032665265
34182685266
156341855857
3531341897858
5168341817859
37243418888510
9783418698511
98123418158512
59833418248513
99703418728514
2369970347215
36829970467216
20169970977217
70879970177218
102899970887219
25949970697220
84999970157221
49739970247222
27999970727223

101-sonli takroriy modul 97-qadam bo'lib, 17-bosqichda sodir bo'ladi. 23-bosqichgacha takrorlash aniqlanmaydi . Bu sabab bo'ladi bolmoq , va omil topiladi.

Murakkablik

Agar yolg'on tasodifiy raqam bo'lsa Pollard r algoritmida yuzaga kelgan haqiqiy tasodifiy son edi, natijada muvaffaqiyatga yarim vaqt ichida, Tug'ilgan kun paradoksi yilda takrorlash. Xuddi shu tahlil haqiqiy rho algoritmiga ham tegishli deb ishoniladi, ammo bu evristik da'vo va algoritmni qat'iy tahlil qilish ochiq bo'lib qolmoqda.[5]

Shuningdek qarang

Adabiyotlar

  1. ^ Pollard, J. M. (1975). "Monte-Karloda faktorizatsiya qilish usuli". BIT Raqamli matematika. 15 (3): 331–334. doi:10.1007 / bf01933667.
  2. ^ Kormen, Tomas H.; Leyzerson, Charlz E.; Rivest, Ronald L. & Shteyn, Klifford (2009). "31.9-bo'lim: Butun sonni faktorizatsiya qilish". Algoritmlarga kirish (uchinchi tahr.). Kembrij, MA: MIT Press. 975-980 betlar. ISBN  978-0-262-03384-8. (bu bo'limda faqat Pollardning rho algoritmi muhokama qilinadi).
  3. ^ Brent, Richard P. (1980). "Monte-Karloda ishlab chiqarishni takomillashtirilgan algoritmi". BIT. 20: 176–184. doi:10.1007 / BF01933190.
  4. ^ a b Brent, R.P.; Pollard, J. M. (1981). "Sakkizinchi Fermat raqamining faktorizatsiyasi". Hisoblash matematikasi. 36 (154): 627–630. doi:10.2307/2007666.
  5. ^ Galbraith, Stiven D. (2012). "14.2.5 Pollard rho-ni qattiq tahlil qilish tomon". Ochiq kalit kriptografiyasining matematikasi. Kembrij universiteti matbuoti. 272-273 betlar. ISBN  9781107013926..

Qo'shimcha o'qish

Tashqi havolalar