Сандық теориядағы квадрат конгруенциясы – бүтін сандарды жіктеу алгоритмдерінде қолданылатын маңызды құрал. Фактор базасын құру, қатынастарды табу, матрицалық өңдеу әдістері қарастырылады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Сандар теориясында квадраттардың конгруэнтісі – бүтін сандарды есепке бөлу алгоритмдерінде кеңінен қолданылатын конгруэнт.
In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms.
Факторлық базаны пайдалану
Диксонның факторлау әдісімен бастамасы берілген және жалғасқан бөлшектерді факторлау, квадраттық сырға және жалпы сандық өріс сырға арқылы жетілдірілген техника – факторлық базаны қолдана отырып, квадраттардың сәйкестігін құру болып табылады. Бір жұпты тікелей іздеудің орнына, біз y-тің тек кіші жай сандарға бөлінетін (тегіс сандар) көптеген «қатынастарды» табамыз және оң жақта квадрат алу үшін олардың кейбіреулерін көбейтеміз. y-тің барлық факторлары кіретін кіші жай сандар жиынтығы факторлық база деп аталады. Әрбір қатары бір y-ті сипаттайтын, әрбір бағаны факторлық базадағы бір жай санға сәйкес келетін және жазбасы y-дегі сол фактордың қайсы санымен кездесетінінің жұп немесе тақ екенін көрсететін Буль матрицасын құрастырамыз. Біздің мақсатымыз – барлық нөлдерден тұратын қатар алу үшін қатарларды қосу. Бұл y мәндерінің жиынтығын көбейту арқылы, оның барлық факторлары жұп санда кездесетін, яғни квадрат санды алуға сәйкес келеді. Сәйкес x мәндерін көбейту арқылы квадраттардың сәйкестігін аламыз. Бұл – сызықтық теңдеулердің классикалық жүйесі және қатарлар саны бағандар санынан асып кеткенде, Гаусс жою әдісін қолдану арқылы тиімді шешуге болады. Әрбір қосымша қатар, егер бірінші шешім тривиальды сәйкестік берсе, қосымша шешім ұсынады. Бұл техниканың үлкен артықшылығы – қатынастарды іздеудің өте оңай параллельделуі; x-тің әртүрлі диапазондарын іздеу және нәтижедегі y-ті факторлауға тырысу үшін көптеген компьютерлерді жұмысқа қоюға болады. Тек табылған қатынастарды ғана орталық компьютерге хабарлау керек, және оны жасауға асығудың қажеті жоқ. Іздеуші компьютерлерге тіпті сенудің қажеті де жоқ; хабарланған қатынасты минимальды күш-жігермен тексеруге болады. Бұл техниканың көптеген түрлері бар. Мысалы, y факторлары факторлық базада толық болатын қатынастарға қоса, «үлкен жай сан» түрі «жартылай қатынастарды» да жинайды, онда y факторлары бір үлкен фактордан басқа толық болады. Екінші жартылай қатынасты сол үлкен фактормен біріншісімен көбейту арқылы «толық қатынас» алуға болады.
A technique pioneered by Dixon's factorization method and improved by continued fraction factorization, the quadratic sieve, and the general number field sieve, is to construct a congruence of squares using a factor base. Instead of looking for one pair directly, we find many "relations" where the y have only small prime factors (they are smooth numbers), and multiply some of them together to get a square on the right hand side. The set of small primes which all the y factor into is called the factor base. Construct a Boolean matrix where each row describes one y, each column corresponds to one prime in the factor base, and the entry is the parity (even or odd) of the number of times that factor occurs in y. Our goal is to choose rows to add together to make an all zero row. This corresponds to a set of y values to multiply together to produce a product whose factors all appear an even number of times, i. e. a square number. Multiplying together the corresponding x values will produce a congruence of squares. This is a classic system of linear equations problem, and can be efficiently solved using Gaussian elimination as soon as the number of rows exceeds the number of columns. Each additional row provides an additional solution, in case the first solution produces a trivial congruence. A great advantage of this technique is that the search for relations is embarrassingly parallel; a large number of computers can be set to work searching different ranges of x values and trying to factor the resultant ys. Only the found relations need to be reported to a central computer, and there is no particular hurry to do so. The searching computers do not even have to be trusted; a reported relation can be verified with minimal effort. There are numerous elaborations on this technique. For example, in addition to relations where y factors completely in the factor base, the "large prime" variant also collects "partial relations" where y factors completely except for one larger factor. A second partial relation with the same larger factor can be multiplied by the first to produce a "complete relation".