Pollards p - 1 algoritm - Pollards p − 1 algorithm - Wikipedia

Pollardniki p - 1 algoritm a raqamlar nazariyasi tamsayı faktorizatsiyasi algoritm tomonidan ixtiro qilingan Jon Pollard 1974 yilda. Bu maxsus maqsadli algoritm, ya'ni u faqat mos keladi butun sonlar omillarning o'ziga xos turlari bilan; bu eng oddiy misol algebraik-guruhli faktorizatsiya algoritmi.

U topadigan omillar bu omildan oldingi son, p - 1, bo'ladi qudratli; multiplikativ guruhda ishlash orqali muhim kuzatuv modul kompozit raqam N, biz ham modulli multiplikativ guruhlarda ishlaymiz N 'omillar.

Ushbu algoritmning mavjudligi tushunchasiga olib keladi xavfsiz sonlar, buning uchun asosiy bo'lish p - 1 ikki marta a Sofi Jermeyn eng yaxshi q va shu bilan minimal darajada silliq. Ba'zan bu tub sonlar "kriptografik maqsadlar uchun xavfsiz" deb talqin etiladi, ammo ular shunday bo'lishi mumkin xavfli - kriptografiya bo'yicha joriy tavsiyalarda kuchli sonlar (masalan. ANSI X9.31 ), bu zarur, ammo etarli emas bu p - 1 kamida bitta katta asosiy omilga ega. Eng katta asosiy sonlar kuchli; agar kriptografik maqsadlarda ishlatiladigan asosiy kuchsiz bo'lib chiqsa, bu voqea sodir bo'lgan voqeadan ko'ra ko'proq yovuzlik orqali bo'lishi mumkin tasodifiy son hosil qilish. Ushbu terminologiya ko'rib chiqilgan eskirgan kriptografiya sohasi bo'yicha: ECM xavfsiz sonlarni zararsiz oddiy sonlar singari osonlikcha ajratadi, shuning uchun kattalik muhim omil hisoblanadi.[1]

Asosiy tushunchalar

Ruxsat bering n asosiy faktor bilan birlashgan butun son bo'ling p. By Fermaning kichik teoremasi, biz buni butun tamsayılar uchun bilamiz a coprime to p va barcha musbat sonlar uchun K:

Agar raqam bo'lsa x 1 ga mos keladi modul omil n, keyin gcd (x − 1, n) bu omilga bo'linadi.

G'oya, eksponentni katta ko'plik qilishdir p - 1 ni juda ko'p sonli asosiy omillarga ega bo'lgan raqamga aylantirish orqali; Umuman olganda, biz barcha asosiy kuchlarning mahsulotini ba'zi bir chegaradan kamroq qabul qilamiz B. Tasodifiy bilan boshlang xva uni bir necha marta o'zgartiring kabi w o'sha asosiy kuchlar orqali ishlaydi. Har bir bosqichda tekshiring yoki agar xohlasangiz, oxirida bir marta tekshiring gcd (x − 1, n) 1 ga teng emas.

Bir nechta omillar

Ehtimol, barcha asosiy omillar uchun p ning n, p - 1 kichik tub sonlarga bo'linadi, bu vaqtda Pollard p - 1 algoritm sizga beradi n yana.

Algoritm va ishlash vaqti

Asosiy algoritmni quyidagicha yozish mumkin:

Kirish: n: kompozit raqam
Chiqish: nodavlat omil n yoki muvaffaqiyatsizlik
  1. chegaralangan silliqlikni tanlang B
  2. aniqlang (eslatma: aniq baholash M kerak bo'lmasligi mumkin)
  3. tasodifiy tanlash a coprime to n (eslatma: biz aslida tuzatishimiz mumkin a, masalan. agar n g'alati, keyin biz har doim tanlay olamiz a = 2, bu erda tasodifiy tanlov shart emas)
  4. hisoblash g = gcd (aM − 1, n) (eslatma: ko'rsatkichni modul qilish mumkinn)
  5. agar 1 < g < n keyin qaytib keling g
  6. agar g = 1 keyin kattaroqni tanlang B va 2-bosqichga o'ting yoki qaytib keling muvaffaqiyatsizlik
  7. agar g = n keyin kichikroq tanlang B va 2-bosqichga o'ting yoki qaytib keling muvaffaqiyatsizlik

Agar g = 1 6-qadamda, bu asosiy omillar yo'qligini ko'rsatadi p buning uchun p-1 bu B-powerersmooth. Agar g = n 7-bosqichda, bu odatda barcha omillar bo'lganligini ko'rsatadi B-powerersmooth, lekin kamdan-kam hollarda bu buni ko'rsatishi mumkin a kichik buyurtma moduli bor edin. Aytgancha, qachon maksimal asosiy omillar p-1 har bir asosiy omil uchun p ning n ba'zi bir kamdan-kam hollarda bir xil bo'ladi, bu algoritm muvaffaqiyatsiz bo'ladi.

Ushbu algoritmning ishlash muddati O (B × log B × log2 n); ning katta qiymatlari B uni sekinroq bajaring, lekin omilni keltirib chiqarishi ehtimoli ko'proq.

Misol

Agar raqamni faktor qilmoqchi bo'lsak n = 299.

  1. Biz tanlaymiz B = 5.
  2. Shunday qilib M = 22 × 31 × 51.
  3. Biz tanlaymiz a = 2.
  4. g = gcd (aM − 1, n) = 13.
  5. 1 <13 <299 dan boshlab, 13 ni qaytaring.
  6. 299/13 = 23 asosiy hisoblanadi, shuning uchun u to'liq hisobga olinadi: 299 = 13 × 23.

Qanday tanlash kerak B?

Algoritm ortib borganligi sababli, u doimo chegara ortib borishi bilan ishlaydi.

Buni taxmin qiling p - 1, qaerda p ning eng kichik asosiy omili n, dan kam kattalikdagi tasodifiy son sifatida modellashtirish mumkinn. Dikson teoremasi bo'yicha, bunday sonning eng katta omilining (p − 1)1 / ε taxminan εε; shuning uchun taxminan 3 ga teng ehtimollik mavjud−3 = 1/27 bu a B ning qiymati n1/6 faktorizatsiyani keltirib chiqaradi.

Amalda, elliptik egri usuli Pollarddan tezroq p - omillar umuman katta bo'lgandan keyin 1 usul; yugurish p - 1 ta usul B = 232 barcha 64-bitli omillarning chorak qismini va 96-bitli omillarning 1/27 qismini topadi.

Ikki bosqichli variant

Ba'zida asosiy algoritmning bir varianti ishlatiladi; buni talab qilish o'rniga p - 1da uning barcha omillari kamroq B, biz uning omillaridan faqat bittasidan boshqasiga qaraganda kamroq bo'lishini talab qilamiz B1, qolgan omil esa ba'zilaridan kamroq B2B1. Yangi hisoblash o'rniga, asosiy algoritm bilan bir xil bo'lgan birinchi bosqichni tugatgandan so'ng

uchun B2 va tekshirish gcd (aM ' − 1, n), biz hisoblaymiz

qayerda H = aM va yo'qligini tekshiring gcd (Q, n) nodavlat omilini ishlab chiqaradi n. Oldingi kabi, ko'rsatkichlarni modul qilish mumkinn.

Ruxsat bering {q1, q2,…} Oralig'ida ketma-ket asosiy sonlar bo'lishi kerak (B1, B2] va dn = qn − qn−1 ketma-ket tub sonlar orasidagi farq. Odatda B1 > 2, dn juft sonlar. Asosiy sonlarning taqsimlanishi shundaydir dn barchasi nisbatan kichik bo'ladi. Taklif qilinmoqda dnln2 B2. Demak, ning qiymatlari H2, H4, H6,… (Modn) jadvalda saqlanishi mumkin va Hqn dan hisoblash Hqn−1Hdn, eksponentatlarga bo'lgan ehtiyojni tejash.

Amaliyotlar

Shuningdek qarang

Adabiyotlar

  • Pollard, J. M. (1974). "Faktorizatsiya va primalitni sinash teoremalari". Kembrij falsafiy jamiyati materiallari. 76 (3): 521–528. Bibcode:1974PCPS ... 76..521P. doi:10.1017 / S0305004100049252.
  • Montgomeri, P. L.; Silverman, R. D. (1990). "FFT kengaytmasi P - 1 faktoring algoritmi ". Hisoblash matematikasi. 54 (190): 839–854. Bibcode:1990MaCom..54..839M. doi:10.1090 / S0025-5718-1990-1011444-3.
  • Semyuel S. Vagstaff, kichik (2013). Faktoring quvonchi. Providence, RI: Amerika Matematik Jamiyati. 138–141 betlar. ISBN  978-1-4704-1048-3.