Ферматтарды факторизация әдісі - Fermats factorization method - Wikipedia

Ферма Келіңіздер факторизация әдіс, атындағы Пьер де Ферма, ан бейнелеуіне негізделген тақ бүтін ретінде екі квадраттың айырымы:

Бұл айырмашылық алгебралық сияқты факторлы ; егер факторлардың ешқайсысы біреуіне тең болмаса, бұл дұрыс факторизация болып табылады N.

Әр тақ санда осындай көрініс бар. Шынында да, егер факторизациясы болып табылады N, содан кейін

Бастап N тақ болса, онда в және г. тақтары да тақ, сондықтан бұл жартылар бүтін сандар болады. (Төрттің еселігі де квадраттардың айырмасы: рұқсат етілсін в және г. тең болу.)

Қарапайым формада Ферма әдісі сынақтық бөлімнен гөрі баяу болуы мүмкін (ең нашар жағдайда). Осыған қарамастан, сынақ бөлімі мен Ферматің үйлесімі екеуіне қарағанда тиімдірек.

Негізгі әдіс

Әр түрлі мәндерді қолдануға тырысады адеп үміттенемін , шаршы.

FermatFactor (N): // N тақ болуы керек    a ← төбесі (sqrt (N)) b2 ← a * a - N дейін қайталаңыз b2 болып табылады шаршы:        a ← a + 1 b2 ← a * a - N      // баламалы: // b2 ← b2 + 2 * a + 1     // a ← a + 1 қайту a - sqrt (b2) // немесе a + sqrt (b2)

Мысалы, факторға , бірінші әрекет а - квадрат түбірі 5959 келесі бүтін санға дейін дөңгелектеледі, яғни 78. Содан кейін, . 125 квадрат емес болғандықтан, мәнін арттыру арқылы екінші әрекет жасалады а 1. Екінші әрекет те сәтсіздікке ұшырайды, өйткені 282 қайтадан квадрат емес.

Тырысу:123
а787980
б2125282441
б11.1816.7921

Үшінші сынақ 441 квадраттың керемет квадратын шығарады. , , және факторлары 5959 болып табылады және .

N-де екіден көп жай факторлар бар делік. Бұл процедура алдымен факторизацияны ең кіші мәндермен табады а және б. Бұл, ең кіші коэффициенті of квадрат түбірі N, солай largest тамырдың ең үлкен факторыN. Егер рәсім табылса , бұл осыны көрсетеді N қарапайым.

Үшін , рұқсат етіңіз в ең кіші ішкі фактор болуы. , сондықтан қадамдар саны шамамен .

Егер N қарапайым (сондықтан ), біреу керек қадамдар. Бұл бірінші кезектілікті дәлелдеудің жаман тәсілі. Бірақ егер N оның квадрат түбіріне жақын факторы бар, әдіс тез жұмыс істейді. Дәлірек айтқанда, егер в қарағанда аз ерекшеленеді бастап , әдіс тек бір қадамды қажет етеді; бұл өлшеміне тәуелсіз N.[дәйексөз қажет ]

Ферма және сынақ бөлімі

Жай санды көбейтуге тырысыңыз N = 2345678917, сонымен қатар есептеу б және аб бүкіл бойында. Жоғары көтерілу , біз кесте жасай аламыз:

а48,43348,43448,43548,436
б276,572173,439270,308367,179
б276.7416.5519.9605.9
аб48,156.348,017.547,915.147,830.1

Іс жүзінде, осы соңғы қатарға дейін алаңдамас еді, дейін б бүтін сан. Бірақ егер солай болса N жоғары ішкі фактор болды , Ферма әдісі оны тапқан болар еді.

Сынақ бөлімі әдетте 48 432-ге дейін тырысады; бірақ тек төрт Ферма қадамынан кейін факторды табу немесе бастапқы дәрежені дәлелдеу үшін бізге 47830 дейін бөлу керек.

Мұның бәрі аралас факторинг әдісін ұсынады. Шектеуді таңдаңыз ; арасындағы факторларға Ферма әдісін қолданыңыз және . Бұл сынақтың бөлінуіне шек келтіреді, яғни . Жоғарыда келтірілген мысалда сынақ бөлуінің шегі 47830. ақылға қонымды таңдау болуы мүмкін 28937 шекарасын бере отырып.

Осыған байланысты Ферма әдісі азаятын нәтиже береді. Осы уақытқа дейін біреу тоқтайтын еді:

а60,00160,002
б21,254,441,0841,254,561,087
б35,418.135,419.8
аб24,582.924,582.2

Елеуді жақсарту

Кестені қарастырған кезде , мәндерінің ешқайсысы жоқ екенін тез білуге ​​болады шаршылар:

а48,43348,43448,43548,436
б276,572173,439270,308367,179
б276.7416.5519.9605.9

Барлық квадрат түбірлерін есептеу қажет емес , тіпті барлық мәндерді зерттемеңіз а. Квадраттар әрқашан 0, 1, 4, 5, 9, 16-ға сәйкес келеді модуль 20. Әрбір өскен сайын мәндер қайталанады а 10. Осы мысалда N 17 mod 20, сондықтан 17 mod 20-ны алып тастаңыз (немесе 3 қосыңыз), осы мәндер үшін 3, 4, 7, 8, 12 және 19 модулін 20 шығарады. Осы тізімнен тек төртеуі ғана квадрат бола алатыны анық. Осылайша, 1 мод 20 болуы керек, бұл дегеніміз а 1, 9, 11 немесе 19 мод 20; ол а шығарады 4 мод 20-мен аяқталады, егер төртбұрыш болса, б 2 немесе 8 режимінде аяқталады 10.

Мұны кез-келген модульмен орындауға болады. Осыны пайдалану ,

модуль 16:Квадраттар0, 1, 4 немесе 9
N mod 16 болып табылады5
сондықтан болуы мүмкін9
және а болуы тиіс3 немесе 5 немесе 11 немесе 13 модулі 16
модуль 9:Квадраттар0, 1, 4 немесе 7
N mod 9 болып табылады7
сондықтан болуы мүмкін7
және а болуы тиіс4 немесе 5 модуль 9

Әдетте, әр модуль үшін әр түрлі дәрежедегі қуат таңдалады.

Тізбегі берілген а-мәндер (басталу, аяқталу және қадам) және модуль келесідей жүре алады:

FermatSieve (N, астарт, аенд, астеп, модуль) a ← астарт істеу модуль рет: b2 ← a * a - N егер b2 - төртбұрышты, модульді модуль: FermatSieve (N, a, aend, astep * modulus, NextModulus) endif        а ← а + астеп энддо

Бірақ рекурсия аз болғанда тоқтатылады а-мәндер қалады; яғни (aend-astart) / astep аз болған кезде. Сонымен қатар, өйткені а 's қадамының өлшемі тұрақты, b2 қосымшаларын қатарымен есептеуге болады.

Бөлу алгоритмін аффиналық трансформация ретінде қолдану арқылы одан әрі модульдік жетілдіруге болады, яғни , , , кез келген бүтін сақинаның үстінде қайда . Алгебраның аз мөлшерінен кейін мынандай қорытынды жасауға болады және мұндағы s мен t бөлгіштерді негізге көбейту кезінде қандай әсер ететінін анықтаумен бірдей .[дәйексөз қажет ]

Мультипликаторды жақсарту

Ферма әдісі квадрат түбірге жақын фактор болған кезде жақсы жұмыс істейді N.

Егер екі фактордың шамамен қатынасы болса () белгілі, содан кейін рационалды сан сол мәнге жақын таңдауға болады. Мысалы, егер , содан кейін бөлгіш жұбының кішісі үшін жақсы баға. , және факторлар шамамен тең: Ферма, қолданылады Жоқ, оларды тез табады. Содан кейін және . (Егер болмаса в бөледі сен немесе г. бөледі v.) Осы тәсілді одан әрі жалпылау деп болжайды , бұл дегеніміз .

Әдетте, егер коэффициент белгілі болмаса, әр түрлі мәндерді байқап көруге болады және олардың әрқайсысының нәтижелерін анықтауға тырысыңыз Жоқ. Р.Леман мұның жүйелі әдісін ойлап тапты, осылайша Ферманың плюс сынақтық бөлінісі N факторына әсер ете алады уақыт.[1]

Басқа жақсартулар

Ферма факторизациясы әдісінің негізгі идеялары төртбұрышты елек және жалпы сандық елеуіш, факторингтің ең танымал алгоритмдері жартылай кезеңдер, бұл «ең жаман жағдай». Квадраттық електің Ферманың факторизациялау әдісін жетілдіретін негізгі жетілдіруі мынада: бұл жай квадратты квадрат табудың орнына , ол осы реттілік элементтерінің ішкі жиынын табады, оның өнім шаршы болып табылады және ол мұны өте тиімді түрде жасайды. Соңғы нәтиже бірдей: квадраттық режимнің айырмашылығы n егер бұл ерекше емес болса, факторға қолдануға болады n.

Сондай-ақ қараңыз

Ескертулер

  1. ^ Леман, Р.Шерман (1974). «Ірі сандарды факторинг» (PDF). Есептеу математикасы. 28 (126): 637–646. дои:10.2307/2005940.

Әдебиеттер тізімі

Сыртқы сілтемелер