Бүтін сандарды факторлау алгоритмі: Поллардтың rho әдісі
Pollard's rho algorithm
Бүтін сандарды жіктеу алгоритмі: Поллардтың rho әдісі – жадты аз қолданатын, сандарды тез жіктеуге арналған тиімді алгоритм. Кіші жай көбейткіштерді табуға көмектеседі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Бүкіл сандық факторлау алгоритмі
бүкіл сандық факторлау алгоритмі
Integer factorization algorithm
the integer factorization algorithm
Полардтың rho алгоритмі – бүтін сандық факторлауға арналған алгоритм. Оны 1975 жылы Джон Поллард ойлап тапты. Алгоритм аз ғана жадты пайдаланады, ал оның күтілетін жұмыс уақыты факторланатын құрама санның ең кіші жай көбейткішінің квадрат түбіріне пропорционалды.
Pollard's rho algorithm is an algorithm for integer factorization. It was invented by John Pollard in 1975. It uses only a small amount of space, and its expected running time is proportional to the square root of the smallest prime factor of the composite number being factorized.
Негізгі идеялар
Алгоритм санды факторлау үшін қолданылады, мұнда – тривиалды емес фактор. Псевдорандомдық тізбек құру үшін (мысалы, ) деп аталатын модуль бойынша полином қолданылады. Бұл полином болуы керек екенін ескеру қажет. Бастапқы мән, мысалы, 2 таңдалады, ал тізбек , , және т.б. ретімен жалғасады. Тізбек басқа тізбекпен байланысты. Бірақ ол алдын ала белгісіз болғандықтан, бұл тізбекті алгоритмде нақты есептеу мүмкін емес. Дегенмен, бұл алгоритмнің негізгі идеясы болып табылады. Мүмкін мәндердің саны шекті болғандықтан, тізбек те, mod , және тізбек те, тіпті бұл мәндер белгісіз болса да, әлдебір уақытта қайталанады. Егер тізбектердегі мәндер кездейсоқ сандар сияқты болып өзгеретін болса, туған күн парадоксы бойынша, қайталану алдындағы саны , мұнда – мүмкін мәндердің саны болады деп күтілуі мүмкін. Сондықтан, тізбек тізбектен әлдеқайда ертерек қайталанады. Егер біз сонды таба алсақ, онда , бірақ , онда сан санының еселігі болады, яғни – факторы табылды. Тізбекте қайталанатын мән пайда болғаннан кейін, тізбек циклдік болады, өйткені әрбір мән тек алдыңғы мәнге ғана тәуелді. Осы циклдік құрылым "rho алгоритмі" деген атқа ие болды, себебі мәндерін бағытталған графтың түйіндері ретінде көрсеткенде, олар грек әрпінің ρ пішініне ұқсайды. Бұл Флойдтың цикл табу алгоритмімен анықталады: екі түйін және (яғни, және ) сақталады. Әр қадамда біреуі тізбектегі келесі түйінге, ал екіншісі екі түйінге жылжиды. Содан кейін, егер ол 1-ге тең болмаса, онда тізбекте қайталану бар екені анықталады (яғни ). Бұл жұмыс істейді, өйткені егер , онда арасындағы айырмашылық міндетті түрде санының еселігі болады. Бірақ бұл әрқашан соңымен болады, нәтижесінде ең үлкен ортақ бөлгіш (GCD) санының 1-ден өзге бөлгіші болады. Бұл өзі де болуы мүмкін, егер екі тізбек бір уақытта қайталануы мүмкін болса. Мұндай (сирек) жағдайда алгоритм сәтсіз аяқталады және басқа параметрмен қайтадан іске қосылуы мүмкін.
The algorithm is used to factorize a number , where is a non trivial factor. A polynomial modulo , called (e. g., ), is used to generate a pseudorandom sequence. It is important to note that must be a polynomial. A starting value, say 2, is chosen, and the sequence continues as , , , etc. The sequence is related to another sequence Since is not known beforehand, this sequence cannot be explicitly computed in the algorithm. Yet, in it lies the core idea of the algorithm. Because the number of possible values for these sequences is finite, both the sequence, which is mod , and sequence will eventually repeat, even though these values are unknown. If the sequences were to behave like random numbers, the birthday paradox implies that the number of before a repetition occurs would be expected to be , where is the number of possible values. So the sequence will likely repeat much earlier than the sequence When one has found a such that but , the number is a multiple of , so has been found. Once a sequence has a repeated value, the sequence will cycle, because each value depends only on the one before it. This structure of eventual cycling gives rise to the name "rho algorithm", owing to similarity to the shape of the Greek letter ρ when the values , , etc. are represented as nodes in a directed graph. This is detected by Floyd's cycle finding algorithm: two nodes and (i. e., and ) are kept. In each step, one moves to the next node in the sequence and the other moves forward by two nodes. After that, it is checked whether If it is not 1, then this implies that there is a repetition in the sequence (i. e. This works because if the is the same as , the difference between and is necessarily a multiple of Although this always happens eventually, the resulting greatest common divisor (GCD) is a divisor of other than 1. This may be itself, since the two sequences might repeat at the same time. In this (uncommon) case the algorithm fails, and can be repeated with a different parameter.
Нұсқалар
1980 жылы Ричард Брент rho алгоритмінің жылдамдатылған нұсқасын жариялады. Ол Поллард сияқты негізгі идеяларды пайдаланды, бірақ циклді анықтаудың басқа тәсілін қолданды, Флойдтың цикл табу алгоритмін Бренттің осымен байланысты цикл табу әдісімен алмастырды. Бұл әдісті Поллард пен Брент одан әрі жетілдірді. Олар егер , онда кез келген оң бүтін b үшін де осыған тең екенін байқады. Атап айтқанда, әр қадамда есептеудің орнына, z-ді n модулі бойынша 100 тізбектелген шарттың көбейтіндісі ретінде анықтау жеткілікті, содан кейін 100 gcd қадамы 99 көбейту және бір gcd операциясымен алмастырылады, бұл үлкен жылдамдыққа әкеледі. Кейде бұл алгоритмнің сәтсіздікке ұшырауына себеп болуы мүмкін, мысалы, n квадрат болған жағдайда, қайталанатын көшбасшы енгізіледі. Бірақ онда бұрынғы gcd шартқа қайтып, ондағы стандартты ρ алгоритмін қолдану жеткілікті.
In 1980, Richard Brent published a faster variant of the rho algorithm. He used the same core ideas as Pollard but a different method of cycle detection, replacing Floyd's cycle finding algorithm with the related Brent's cycle finding method. A further improvement was made by Pollard and Brent. They observed that if , then also for any positive integer b. In particular, instead of computing at every step, it suffices to define z as the product of 100 consecutive terms modulo n, and then compute a single A major speed up results as 100 gcd steps are replaced with 99 multiplications modulo n and a single gcd. Occasionally it may cause the algorithm to fail by introducing a repeated factor, for instance when n is a square. But it then suffices to go back to the previous gcd term, where , and use the regular ρ algorithm from there.
Қолдану
Алгоритм кіші факторлары бар сандар үшін өте жылдам, бірақ барлық факторлары үлкен болған жағдайларда баяулайды. ρ алгоритмінің ең айқын жетістігі – 1980 жылы Ферма санының F8 = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321 түріндегі жіктелуі. ρ алгоритмі F8 үшін тиімді таңдау болды, себебі p = 1238926361552897 жай коэффициенті екінші фактордан әлдеқайда кіші. Бұл жіктелу UNIVAC 1100/42 компьютерінде 2 сағатқа созылды.
The algorithm is very fast for numbers with small factors, but slower in cases where all factors are large. The ρ algorithm's most remarkable success was the 1980 factorization of the Fermat number F8 = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321. The ρ algorithm was a good choice for F8 because the prime factor p = 1238926361552897 is much smaller than the other factor. The factorization took 2 hours on a UNIVAC 1100/42.