Eulers faktorizatsiya usuli - Eulers factorization method - Wikipedia

Eyler faktorizatsiya usuli uchun texnikadir faktoring ikki kvadratning yig'indisi sifatida ikki xil usulda yozish orqali raqam. Masalan, raqam sifatida yozilishi mumkin yoki kabi va Eyler usuli faktorizatsiya beradi .

G'alati musbat tamsaytning ikkita aniq tasviri faktorizatsiyaga olib kelishi mumkin degan fikr, birinchi navbatda, ilgari surilgan Marin Mersenne. Biroq, undan yuz yil o'tgach, Eyler tomonidan keng foydalanilmadi. Hozir uning nomi bilan ataladigan ushbu usuldan eng taniqli foydalanishi raqamni omil qilish edi , aftidan ilgari u a deb hisoblanmasa ham, eng asosiy deb hisoblangan psevdoprime har qanday asosiy dastlabki sinov orqali.

Eulerni faktorizatsiya qilish usuli, agar faktorlari bir-biriga yaqin bo'lmagan va potentsial ravishda ikkita kvadratning yig'indisi sifatida raqamlarning ko'rinishini osonlikcha topsa, sinov bo'linishidan ancha samarali bo'lgan tamsayılar uchun Fermaga qaraganda samaraliroq. Eylerning rivojlanishi oxir-oqibat raqamlarni faktoring qilishda ancha samarali bo'lishiga imkon berdi va 1910-yillarda o'n millionga yaqin yirik faktorli jadvallarni ishlab chiqishga imkon berdi.[iqtibos kerak ]. Ikkala kvadratning yig'indisi sifatida raqamlarning ko'rinishini topish uchun ishlatiladigan usullar asosan kvadratlarning farqlarini topish bilan bir xildir. Fermani faktorizatsiya qilish usuli.

Eylerni faktorizatsiya qilish usulining katta kamchiligi shundaki, uni 4-shakldagi biron bir asosiy faktor bilan butun sonni faktoring qilishda qo'llash mumkin emas.k + 3 asosiy faktorizatsiyasida toq kuchga to'g'ri keladi, chunki bunday son hech qachon ikkita kvadratning yig'indisi bo'lishi mumkin emas. Juft toq kompozit raqamlar 4-shaklk + 1 ko'pincha 4-shaklning ikkita tub sonining ko'paytmasik + 3 (masalan, 3053 = 43 × 71) va yana Eyler usuli bilan aniqlab bo'lmaydi.

Ushbu cheklangan qo'llanilishi Eylerni faktorizatsiya qilish usulini yoqtirmaydi kompyuter faktoring algoritmlar, tasodifiy tamsayıga ta'sir ko'rsatishga urinayotgan har qanday foydalanuvchi Eyler uslubi aslida ko'rib chiqilayotgan butun songa tatbiq etilishini bilishi ehtimoldan yiroq emas. Euler usulini qo'llash mumkin bo'lgan ixtisoslashtirilgan raqamlarda foydalanish uchun kompyuter algoritmlarida Eyler uslubini ishlab chiqishga urinishlar nisbatan yaqinda bo'lgan.

Nazariy asos

The Braxmagupta - Fibonachchining o'ziga xosligi ikki kvadratning ikki yig'indisi ko'paytmasi ikki kvadratning yig'indisi ekanligini bildiradi. Eyler uslubi ushbu teoremaga asoslanadi, ammo uni aksincha, berilgan deb hisoblash mumkin biz topamiz ikki kvadrat yig'indisi ko'paytmasi sifatida.

Avval buni aniqlang

va ikkala tomonni ham olish

(1)

Endi ruxsat bering va shuning uchun ba'zi bir doimiylar mavjud qoniqarli

  • ,
  • ,

  • ,
  • ,

Bularni (1) tenglamaga almashtirish beradi

Umumiy omillarni bekor qilishni bekor qilish

Endi bu haqiqatdan foydalanib va nisbatan tub sonlar juftligi, biz buni topamiz

Shunday qilib

Biz hozir buni ko'rib turibmiz va

Qo'llash Braxmagupta - Fibonachchining o'ziga xosligi biz olamiz

Har bir faktor ikki kvadratning yig'indisi bo'lgani uchun ulardan bittasida ikkala juft son bo'lishi kerak: yoki yoki . Umumiylikni yo'qotmasdan, bu juftlikni taxmin qiling hatto. Keyin faktorizatsiya bo'ladi

Ishlagan misol

Beri:

biz yuqoridagi formuladan:

a = 1000(A) av = 28k = gcd [A, C] = 4
b = 3(B) a + v = 1972h = gcd [B, D] = 34
v = 972(C) db = 232l = gcd [A, D] = 14
d = 235(D) d + b = 238m = gcd [B, C] = 116

Shunday qilib,

Adabiyotlar

  • Ore, Oyshteyn (1988). "Eylerni omillashtirish usuli". Raqamlar nazariyasi va uning tarixi. pp.59–64. ISBN  978-0-486-65620-5.
  • McKee, Jeyms (1996). "Eylerning Faktoring usulini Faktoring algoritmiga aylantirish". London Matematik Jamiyati Axborotnomasi. 4 (28): 351–355. doi:10.1112 / blms / 28.4.351.