Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Санды көбейтіндіге жіктеу
Decomposition of a number into a product
Сандар теориясында бүтін санды факторлау – оң бүтін санды бүтін сандардың көбейтіндісіне жіктеу. 1-ден үлкен кез келген оң бүтін сан екі немесе одан көп бүтін сан көбейткіштерінің көбейтіндісі болып табылады, мұндай жағдайда ол құрама сан деп аталады, ал егер олай болмаса, онда ол жай сан деп аталады. Мысалы, 15 – құрама сан, себебі 15 = 3 · 5, ал 7 – жай сан, өйткені оны осылай жіктеуге болмайды. Егер көбейткіштердің бірі құрама болса, оны кіші көбейткіштердің көбейтіндісі түрінде жазуға болады, мысалы, 60 = 3 · 20 = 3 · (5 · 4). Бұл процесті барлық көбейткіштер жай сан болғанға дейін жалғастыру жай санға жіктеу деп аталады; нәтижесі жай санға жіктеу теоремасы бойынша көбейткіштердің ретіне қарамастан бірегей болады. Шағын бүтін санды n-ді санау арқылы немесе қалам мен қағазды қолданып жіктеу үшін ең қарапайым әдіс – сынамалы бөлу: санды 2, 3, 5 және т.б. жай сандарға бөлінетінін тексеру, n-нің квадрат түбіріне дейін. Үлкен сандар үшін, әсіресе компьютерді пайдаланғанда, түрлі күрделі факторлау алгоритмдері тиімдірек. Жай санға жіктеу алгоритмі әдетте әрбір көбейткіш табылған сайын оның жай сан екенін тексеруді қамтиды. Сандар жеткілікті үлкен болғанда, тиімді кванттық емес бүтін санды факторлау алгоритмі белгісіз. Алайда, мұндай алгоритмнің жоқ екені дәлелденген жоқ. Бұл мәселенің қиындығы криптографияда қолданылатын RSA ашық кілт шифрлауы және RSA цифрлық қолтаңбасы сияқты алгоритмдер үшін маңызды. Математика мен компьютерлік ғылымның көптеген салалары, соның ішінде эллипстік қисықтар, алгебралық сандар теориясы және кванттық есептеулер осы мәселеге тартылды. Берілген ұзындығы бар сандардың бәрі де бірдей қиындықпен факторланбайды. Бұл мәселелердің ең қиын мысалдары (қазіргі таңдағы белгілі әдістер үшін) – екі жай санның көбейтіндісі болып табылатын жартылай жай сандар. Егер екеуі де үлкен болса, мысалы, екі мың биттен асатын ұзындығы бар, кездейсоқ таңдалған және шамамен бірдей мөлшерде (бірақ, мысалы, Ферма факторлау әдісімен тиімді факторлаудан аулақ болу үшін тым жақын емес), тіпті ең жылдам компьютерлердегі ең жылдам факторлау алгоритмі іздеуді практикалық емес ететіндей уақытты қажет етеді; яғни, факторланатын бүтін санның цифрларының саны артқан сайын, кез келген компьютерде факторлауды орындау үшін қажетті операциялардың саны күрт өседі. Көптеген криптографиялық протоколдар үлкен құрама сандарды немесе осымен байланысты мәселені (мысалы, RSA мәселесін) факторлаудың қиындығына негізделген. Кез келген бүтін санды тиімді факторлайтын алгоритм RSA негізделген ашық кілт криптографиясын қауіпсіз етеді.
In number theory, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, 15 is a composite number because 1=15 = 3 · 5, but 7 is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example 1=60 = 3 · 20 = 3 · (5 · 4). Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem. To factorize a small integer n using mental or pen and paper arithmetic, the simplest method is trial division: checking if the number is divisible by prime numbers 2, 3, 5, and so on, up to the square root of n. For larger numbers, especially when using a computer, various more sophisticated factorization algorithms are more efficient. A prime factorization algorithm typically involves testing whether each factor is prime each time a factor is found. When the numbers are sufficiently large, no efficient non quantum integer factorization algorithm is known. However, it has not been proven that such an algorithm does not exist. The presumed difficulty of this problem is important for the algorithms used in cryptography such as RSA public key encryption and the RSA digital signature. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing. Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime numbers. When they are both large, for instance more than two thousand bits long, randomly chosen, and about the same size (but not too close, for example, to avoid efficient factorization by Fermat's factorization method), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical; that is, as the number of digits of the integer being factored increases, the number of operations required to perform the factorization on any computer increases drastically. Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem—for example, the RSA problem. An algorithm that efficiently factors an arbitrary integer would render RSA based public key cryptography insecure.
Бастапқы ыдырау
Арифметиканың негізгі теоремасы бойынша, әрбір оң бүтін санның бірегей жай көбейткіштерге жіктелуі бар. (Дәстүр бойынша 1 – бос көбейтінді.) Сан жай ма екенін тексеру, мысалы, AKS жайлық тесті арқылы, полиномиалдық уақытта жүзеге асырылуы мүмкін. Дегенмен, егер сан жай болмаса, полиномиалдық уақыттық тесттер оның көбейткіштерін қалай алуға болатыны туралы ешқандай түсінік бермейді. Бүтін сандарды жіктеудің жалпы алгоритмі болған жағдайда, кез келген бүтін санды осы алгоритмді қайталап қолдану арқылы оның жай көбейткіштеріне жіктеуге болады. Бірақ, ерекше мақсаттағы жіктеу алгоритмдерімен жағдай күрделірек, олардың артықшылықтары жіктеу барысында алынған көбейткіштер үшін толыққанды пайдаланылмауы мүмкін. Мысалы, егер n = 171 × p × q болса, мұнда p < q өте үлкен жай сандар болса, жай тексеру әдісі 3 және 19 көбейткіштерін жылдам анықтайды, бірақ келесі көбейткішті табу үшін p бөліске қажет болады. Керісінше, мысалы, егер n 13729, 1372933 және 18848997161 жай сандарының көбейтіндісі болса, онда 1 = 13729 × 1372933 = 18848997157, Ферманың жіктеу әдісі бірден мынаны береді және осылайша көбейткіштер 1 = a − b = 18848997157 және 1 = a + b = 18848997161 табылады. Бұлар жай және жай болмаған сандар екені анық болғанымен, Ферма әдісі жай болмаған санды жіктеуге көбірек уақыт жұмсайды, себебі a үшін бастапқы мән 1372933-тен 10 есеге үлкен.
By the fundamental theorem of arithmetic, every positive integer has a unique prime factorization. (By convention, 1 is the empty product.) Testing whether the integer is prime can be done in polynomial time, for example, by the AKS primality test. If composite, however, the polynomial time tests give no insight into how to obtain the factors. Given a general algorithm for integer factorization, any integer can be factored into its constituent prime factors by repeated application of this algorithm. The situation is more complicated with special purpose factorization algorithms, whose benefits may not be realized as well or even at all with the factors produced during decomposition. For example, if 1=n = 171 × p × q where p < q are very large primes, trial division will quickly produce the factors 3 and 19 but will take p divisions to find the next factor. As a contrasting example, if n is the product of the primes 13729, 1372933, and 18848997161, where 1=13729 × 1372933 = 18848997157, Fermat's factorization method will begin with which immediately yields and hence the factors 1=a − b = 18848997157 and 1=a + b = 18848997161. While these are easily recognized as composite and prime respectively, Fermat's method will take much longer to factor the composite number because the starting value of for a is a factor of 10 from 1372933.
Қазіргі заманғы техниканың жай-күйі
b бит сандарының ішінде, қолданыстағы алгоритмдерді пайдаланып факторлау ең қиын болып табылатындары – факторлары шамамен бірдей мөлшердегі жартылай жай сандар. Сондықтан, олар криптографиялық қолданыстарда қолданылатын бүтін сандар болып табылады. 2019 жылы Фабрис Будот, Пьеррик Гаудри, Ауроре Гильевич, Надя Хенингер, Эммануэль Томе және Пол Циммерман 240 таңбалы (795 бит) санды (RSA 240) шамамен 900 ядро жылдық есептеу қуатын қолдана отырып, факторлады. Зерттеушілер 1024 биттік RSA модулін факторлауға шамамен 500 есе көп уақыт кетеді деп есептеді. Осы сияқты ең үлкен жартылай жай сан – RSA 250, ол 829 биттік және 250 ондық таңбадан тұрады, ол 2020 жылдың ақпан айында факторланды. Жалпы есептеу уақыты 2.1 ГГц жиілігіндегі Intel Xeon Gold 6130 процессорларын пайдалана отырып, шамамен 2700 ядро жылды құрады. Барлық соңғы факторлау рекордтары сияқты, бұл факторлау да жүздеген машиналарда жұмыс істейтін жалпы сандық егіздің жоғары сапалы оңтайландырылған нұсқасымен аяқталды.
Among the b bit numbers, the most difficult to factor in practice using existing algorithms are those semiprimes whose factors are of similar size. For this reason, these are the integers used in cryptographic applications. In 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored a 240 digit (795 bit) number (RSA 240) utilizing approximately 900 core years of computing power. The researchers estimated that a 1024 bit RSA modulus would take about 500 times as long. The largest such semiprime yet factored was RSA 250, an 829 bit number with 250 decimal digits, in February 2020. The total computation time was roughly 2700 core years of computing using Intel Xeon Gold 6130 at 2.1 GHz. Like all recent factorization records, this factorization was completed with a highly optimized implementation of the general number field sieve run on hundreds of machines.
Уақыт күрделілігі
Қандай да бір алгоритм бүтін сандардың барлығын полиномиалдық уақытта, яғни b бит саны n-ді уақытпен көбейте алатыны жарияланбаған. Мұндай алгоритмдердің болуы немесе болмауы дәлелденбеген, бірақ олардың жоқ екені күдіктенуде. Барлық оң ε үшін O((1 + ε)^b) жылдамдығынан артық алгоритмдер жарияланды, яғни экспоненциалды емес. 2022 жылға дейін теориялық асимптотикалық жұмыс істеу уақыты бойынша ең жақсы алгоритм – жалпы сандық өріс ілгіші (GNFS), ол алғаш рет 1993 жылы жарияланған және b бит саны n үшін келесі уақытта жұмыс істейді:
No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a b bit number n in time [[Big O notation for some constant k. Neither the existence nor non existence of such algorithms has been proved, but it is generally suspected that they do not exist. There are published algorithms that are faster than O((1 + ε)^(b)) for all positive ε, that is, sub exponential. as of 2022, the algorithm with best theoretical asymptotic running time is the general number field sieve (GNFS), first published in 1993, running on a b bit number n in time:
Қазіргі компьютерлер үшін GNFS үлкен n үшін (400 биттен асатын) ең жақсы жарияланған алгоритм болып табылады. Дегенмен, кванттық компьютер үшін Питер Шор 1994 жылы оны полиномиалдық уақытта шешетін алгоритмді тапты. Шор алгоритмі b биттік кіріс үшін O(b^3) уақыт және O(b) жад алады. 2001 жылы Шор алгоритмі алғаш рет жеті кубит беретін молекулаларға NMR техникаларын қолдану арқылы іске асырылды. P, NP және co NP сияқты күрделілік сыныптары туралы сөз қозғалғанда, мәселе шешім проблемасы ретінде қойылған болуы керек. Ол NP және co NP кластарына жатады, яғни «иә» және «жоқ» жауаптары полиномиалдық уақытта тексеріле алады. «Иә» жауабы d ≤ k болатын көбейткіштерді көрсету арқылы расталады. «Жоқ» жауабы n-нің k-дан үлкен әртүрлі жай сандарға көбейткіштерге жіктелуін көрсету арқылы расталады; олардың жайлығын AKS жайлық тестісі арқылы тексеруге болады, содан кейін оларды көбейту арқылы n алуға болады. Арифметиканың негізгі теоремасы тек бір ғана өсу ретімен жай сандар тізбегінің қабылданатынын кепілдейді, бұл мәселенің UP және co UP кластарына жататынын көрсетеді. Шор алгоритмінің арқасында ол BQP класына да жатады. Мәселенің P, NP-толық және co NP-толық күрделілік сыныптарының сыртында екені күдіктенуде. Сондықтан ол NP аралық күрделілік класына үміткер. Керісінше, «n – құрама сан ба?» (немесе эквивалентті: «n – жай сан ба?») деген шешім проблемасы n-нің көбейткіштерін анықтау мәселесінен әлдеқайда оңай болып көрінеді. Құрама/жай мәселесі AKS жайлық тестісімен полиномиалдық уақытта (n сандарының b саны) шешіледі. Сонымен қатар, егер қателік мүмкіндігін өте аз деңгейге дейін қабылдауға дайын болса, жайлықты өте жылдам тексеруге мүмкіндік беретін бірнеше ықтималдық алгоритмдер бар. Жайлықты тексерудің қарапайымдығы RSA алгоритмінің маңызды бөлігі болып табылады, өйткені оны бастау үшін үлкен жай сандарды табу қажет.
For current computers, GNFS is the best published algorithm for large n (more than about 400 bits). For a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time. Shor's algorithm takes only O(b^(3)) time and O(b) space on b bit number inputs. In 2001, Shor's algorithm was implemented for the first time, by using NMR techniques on molecules that provide seven qubits. In order to talk about complexity classes such as P, NP, and co NP, the problem has to be stated as a decision problem. It is known to be in both NP and co NP, meaning that both "yes" and "no" answers can be verified in polynomial time. An answer of "yes" can be certified by exhibiting a factorization with d ≤ k. An answer of "no" can be certified by exhibiting the factorization of n into distinct primes, all larger than k; one can verify their primality using the AKS primality test, and then multiply them to obtain n. The fundamental theorem of arithmetic guarantees that there is only one possible string of increasing primes that will be accepted, which shows that the problem is in both UP and co UP. It is known to be in BQP because of Shor's algorithm. The problem is suspected to be outside all three of the complexity classes P, NP complete, and co NP complete. It is therefore a candidate for the NP intermediate complexity class. In contrast, the decision problem "Is n a composite number?" (or equivalently: "Is n a prime number?") appears to be much easier than the problem of specifying factors of n. The composite/prime problem can be solved in polynomial time (in the number b of digits of n) with the AKS primality test. In addition, there are several probabilistic algorithms that can test primality very quickly in practice if one is willing to accept a vanishingly small possibility of error. The ease of primality testing is a crucial part of the RSA algorithm, as it is necessary to find large prime numbers to start with.
Жалпы мақсаттағы
Жалпы мақсаттағы факторлау алгоритмі, сонымен қатар 2-санатты, екінші санатты немесе Крайтчик отбасы алгоритмі деп аталатын, Сейсен мен Ленстраның алгоритмі, олар бұл алгоритмді тек дәлелденбеген жалпыланған Риманн гипотезасы негізінде ғана дәлелдеді.
A general purpose factoring algorithm, also known as a Category 2, Second Category, or Kraitchik family algorithm, Seysen, and Lenstra, which they proved only assuming the unproved generalized Riemann hypothesis.