Джон Диксонның сандарды жіктеу әдісі – бүтін сандарды жіктеуге арналған алгоритм. Бұл әдіс фактор базалық тәсілдің негізі болып табылады, нақты дәлелдерге негізделген.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Сандар теориясында Диксонның факторлау әдісі (сонымен қатар Диксонның кездейсоқ квадраттар әдісі немесе Диксон алгоритмі) – жалпы мақсаттағы бүтін сандарды факторлау алгоритмі; ол факторлық база әдісінің негізгі үлгісі болып табылады. Басқа факторлық база әдістерінен өзгешелігі, оның жұмыс істеу уақытының шегі қатаң дәлелмен келеді, ол полиномның мәндерінің тегістік қасиеттері туралы болжамдарға тәуелді емес. Алгоритмді Карлтон университетінің математигі Джон Д. Диксон жасады және ол 1981 жылы жарияланды.
In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run time bound comes with a rigorous proof that does not rely on conjectures about the smoothness properties of the values taken by a polynomial. The algorithm was designed by John D. Dixon, a mathematician at Carleton University, and was published in 1981.
Негізгі идея
Диксон әдісі факторлауға арналған N бүтін санының модулі бойынша квадраттардың конгруэнттігін табуға негізделген. Ферма факторлау әдісі кездейсоқ немесе псевдокездейсоқ x мәндерін таңдап, x² mod N бүтін саны толық квадрат (тұтас сандардағы) болып шығуына үміттенеді:
Dixon's method is based on finding a congruence of squares modulo the integer N which is intended to factor. Fermat's factorization method finds such a congruence by selecting random or pseudo random x values and hoping that the integer x2 mod N is a perfect square (in the integers):
Мысалы, егер (292-ден бастап, √N-ден үлкен алғашқы саннан санау), 505² mod 84923 = 256, ал 256 – 16-ның квадраты. Евклид алгоритмін қолданып, 505 – 16 және N-нің ең үлкен ортақ бөлгішін есептегенде 163 шығады, бұл N-нің бөлгіші.
For example, if , (by starting at 292, the first number greater than and counting up) the 5052 mod 84923 is 256, the square of 16. So Computing the greatest common divisor of 505 − 16 and N using Euclid's algorithm gives 163, which is a factor of N.
Іс жүзінде, кездейсоқ x мәндерін таңдау квадраттардың конгруэнттігін табу үшін тым көп уақыт алады, себебі N-ден кіші тек √N квадрат бар.
In practice, selecting random x values will take an impractically long time to find a congruence of squares, since there are only squares less than N.
Диксон әдісі «толық санның квадраты» деген шартты «тек кішкентай жай бөлгіштері бар» деген әлдеқайда әлсіз шартпен алмастырады; мысалы, 84923-тен кіші 292 квадрат бар; 84923-тен кіші 662 сан бар, олардың жай бөлгіштері тек 2, 3, 5 немесе 7-ге тең; ал 4767-нің жай бөлгіштерінің барлығы 30-дан кем. (Мұндай сандар белгілі бір шек B-ға қатысты B-жұп деп аталады.) Егер квадраттары кішкентай жай сандардың белгілі бір жиынтығына жіктелетін көптеген сандар болса, 2 модулі бойынша матрицадағы сызықтық алгебра, квадраттары кішкентай жай сандардың дәрежесі жұп болатын сандардың ішкі жиынтығын береді, яғни квадраттары N модулі бойынша (басқа) бір санның квадратына тең болатын сандардың ішкі жиынтығын.
Dixon's method replaces the condition "is the square of an integer" with the much weaker one "has only small prime factors"; for example, there are 292 squares smaller than 84923; 662 numbers smaller than 84923 whose prime factors are only 2,3,5 or 7; and 4767 whose prime factors are all less than 30. (Such numbers are called B smooth with respect to some bound B.) If there are many numbers whose squares can be factorized as for a fixed set of small primes, linear algebra modulo 2 on the matrix will give a subset of the whose squares combine to a product of small primes to an even power — that is, a subset of the whose squares multiply to the square of a (hopefully different) number mod N.