Бүтін сандарды жіктеу алгоритмі: Эллиптикалық қисықтар әдісі

Кіріспе

Бүтін сандарды факторлау алгоритмі

Ленстра эллиптік қисық факторлауы немесе эллиптік қисық факторлау әдісі (ECM) – эллиптік қисықтарды пайдаланатын, бүтін сандарды факторлаудың жылдам, субэкспоненциалды уақытпен жұмыс істейтін алгоритмі. Жалпы мақсаттағы факторлау үшін ECM үшінші жылдам факторлау әдісі болып табылады. Екінші жылдам – көп полиномды квадраттық иіргіш, ал ең жылдам – жалпы сандық өріс иіргіші. Ленстра эллиптік қисық факторлауы Хендрик Ленстраның құрметіне аталған. Іс жүзінде ECM арнайы мақсаттағы факторлау алгоритмі деп есептеледі, себебі ол кіші факторларды табуға ең қолайлы. Қазіргі таңдағыда, бұл 50-60 цифрдан аспайтын бөлгіштер үшін ең жақсы алгоритм болып табылады, өйткені оның жұмыс уақытын факторланатын санның (n) мөлшері емес, ең кіші көбейтіндінің (p) мөлшері анықтайды. ECM жиі көптеген факторлары бар өте үлкен бүтін саннан кіші факторларды жою үшін қолданылады; егер қалған бүтін сан әлі де жай сан болмаса, онда оның тек үлкен факторлары болады және олар жалпы мақсаттағы әдістерді қолдану арқылы факторланады. ЭКМ қолданылып табылған ең үлкен фактор 83 ондық цифрдан тұрады және ол 2013 жылдың 7 қыркүйегінде Р. Проппермен анықталды. Тестіленіп жатқан қисықтардың санын арттыру фактор табу ықтималдығын арттырады, бірақ бұл қисықтардың санының өсуімен сызықтық байланыста болмайды.

Түсіндірме

Егер p және q н-нің екі жай бөлгіші болса, онда 1=y^(2) = x^(3) + 1=ax + b (mod n) теңдеуі 1=modulo p және 1=modulo q теңдеуін білдіреді. Бұл екі кіші эллипстік қисық енді қосылғанда нақты топтар болады. Егер бұл топтарда Np және Nq элементтері болса, онда бастапқы қисықтағы кез келген P нүктесі үшін Лагранж теоремасы бойынша 1=k > 0 ең кіші оң сан, яғни модуль p бойынша қисықта k Np-ді бөледі; сондай-ақ, модуль q бойынша қисық үшін де ұқсас тұжырым дұрыс. Эллипстік қисық кездейсоқ таңдалғанда, Np және Nq тиісінше 1=p + 1 және 1=q + 1-ге жақын кездейсоқ сандар болады (төменде қараңыз). Сондықтан Np және Nq-ның жай факторларының көпшілігі бірдей болмайды және eP есептеу кезінде біз модуль p бойынша ∞ 1=болатын, бірақ модуль q бойынша 1=болмайтын немесе керісінше, кейбір kP кездесетініміз мүмкін. Бұл жағдайда kP бастапқы қисықта жоқ, ал есептеулерде біз 1=gcd(v,p) = p немесе 1=gcd(v,q) = q, бірақ екеуі де емес болатын v-ні табамыз. Яғни, 1=gcd(v, n) n-нің тривиальды емес бөлгішін береді. ECM негізінен ескі 1=p − 1 алгоритмін жақсарту болып табылады. 1=p − 1 алгоритмі 1=p − 1 b-нің кіші мәндері үшін b-нің күштерін тегістететін p-нің жай бөлгіштерін іздейді. Кез келген e үшін, 1=p − 1-дің еселігі және p-ге жай сандар үшін Ферманың кішкентай теоремасы бойынша 1=a^(e) ≡ 1 (mod n). Содан кейін 1=[[ең үлкен ортақ бөлгіш n-нің бөлгішін табуға мүмкіндік береді. Алайда, алгоритм 1=p − 1 үлкен жай факторларға ие болғанда, мысалы, күшті жай сандарды қамтитын сандар үшін сәтсіздікке ұшырайды. ECM бұл кедергіні Zp шекті өрісіндегі кездейсоқ эллипстік қисықтың тобын қарастыру арқылы айналып өтеді, әрқашан 1=p − 1 реті бар Zp-нің көбейтуші тобын қарастырудың орнына. Хассе теоремасы бойынша Zp-ге дейінгі эллипстік қисықтың тобының реті (көп жағдайда) аралығында өзгереді және кейбір эллипстік қисықтар үшін тегіс болуы мүмкін. Хассе аралығында тегіс топтық рет табылатынына дәлел болмаса да, эвристикалық ықтималдық әдістерін, Canfield–Erdős–Pomerance теоремасын тиісті параметрлерді оңтайландыру арқылы және L белгісін қолдану арқылы біз тегіс топтық рет табу үшін қисықтарды сынап көруге болады. Бұл эвристикалық бағалау практикада өте сенімді.

If p and q are two prime divisors of n, then 1=y^(2) = x^(3) + 1=ax + b (mod n) implies the same equation also 1=modulo p and 1=modulo q. These two smaller elliptic curves with the addition are now genuine groups. If these groups have Np and Nq elements, respectively, then for any point P on the original curve, by Lagrange's theorem, 1=k > 0 is minimal such that on the curve modulo p implies that k divides Np; moreover, The analogous statement holds for the curve modulo q. When the elliptic curve is chosen randomly, then Np and Nq are random numbers close to 1=p + 1 and 1=q + 1, respectively (see below). Hence it is unlikely that most of the prime factors of Np and Nq are the same, and it is quite likely that while computing eP, we will encounter some kP that is ∞ 1=modulo p but not 1=modulo q, or vice versa. When this is the case, kP does not exist on the original curve, and in the computations we found some v with either 1=gcd(v,p) = p or 1=gcd(v, q) = q, but not both. That is, 1=gcd(v, n) gave a non trivial factor 1=of n.

ECM is at its core an improvement of the older 1=p − 1 algorithm. The 1=p − 1 algorithm finds prime factors p such that 1=p − 1 is b powersmooth for small values of b. For any e, a multiple of 1=p − 1, and any a relatively prime to p, by Fermat's little theorem we have 1=a^(e) ≡ 1 ([[modular arithmetic. Then 1=[[greatest common divisor is likely to produce a factor of n. However, the algorithm fails when 1=p 1 has large prime factors, as is the case for numbers containing strong primes, for example. ECM gets around this obstacle by considering the group of a random elliptic curve over the finite field Zp, rather than considering the multiplicative group of Zp which always has order 1=p − 1. The order of the group of an elliptic curve over Zp varies (quite randomly) between and by Hasse's theorem, and is likely to be smooth for some elliptic curves. Although there is no proof that a smooth group order will be found in the Hasse interval, by using heuristic probabilistic methods, the Canfield–Erdős–Pomerance theorem with suitably optimized parameter choices, and the L notation, we can expect to try curves before getting a smooth group order. This heuristic estimate is very reliable in practice.

Пайдалану үлгісі

Келесі мысал кейбір егжей-тегжейлі мәліметтермен қоса алынған. Біз 1=n = 455839. 1=y^(2) = x^(3) + 5x – 5 деген эллиптік қисықты таңдап алайық, онда 1=P = (1, 1) нүктесі бар, содан кейін 1=(10!)P дегенді есептейік. А=(x, y) нүктесіндегі тангенс сызығының еңістігі 1=s = (3x^(2) + 5)/(2y) (mod n). s-ті пайдаланып 2A-ны есептейміз. Егер s мәні a/b түрінде болса, онда b > 1 және gcd(a,b) = 1, біз b модульдік керісін табуымыз керек. Егер ол болмаса, gcd(n,b) - n-нің тривиальды емес көбейткіші. Алдымен 2P-ді есептейміз. Бізде 1=s(P) = s(1,1) = 4, сондықтан координаттары бар және 1== 4(1 – 14) – 1 = –53, барлық сандар 1=(mod n). Осы 2P шын мәнінде қисықтағыны тексереміз: 1=(–53)^2 = 2809 = 143 + 5·14 – 5. Содан кейін 3(2P) деп есептейміз. Бізде 1=s(2P) = s(14, 53) = –593/106 (mod n) бар. Евклид алгоритмін қолдану: 1=455839 = 4300·106 + 39, содан кейін 1=106 = 2·39 + 28, содан кейін 1=39 = 28 + 11, содан кейін 1=28 = 2·11 + 6, содан кейін 1=11 = 6 + 5, содан кейін 1=6 = 5 + 1. Демек 1=gcd(455839, 106) = 1, және кері қарай жұмыс істеу (кеңейтілген Евклид алгоритмінің нұсқасы): 1=1 = 6 – 5 = 2·6 – 11 = 2·28 – 5·11 = 7·28 – 5·39 = 7·106 – 19·39 = 81707·106 – 19·455839. Демек 1=106−1 = 81707 (mod 455839), ал 1=–593/106 = –133317 (mod 455839). Осы s берілген жағдайда, біз 2(2P) координаттарын жоғарыда көрсетілгендей есептейміз: 1=4P = (259851, 116255). Бұл шын мәнінде қисықтағы нүкте екенін тексеру үшін: 1=y^(2) = 54514 = x^(3) + 5x – 5 (mod 455839). Осыдан кейін біз есептей аламыз. Біз 4!P-ді және т.б. есептей аламыз, бірақ 8!P 1=599 (mod 455839) инвертациясын қажет етеді. Евклид алгоритмі 455839 599-ға бөлінетінін береді, және біз 1=факторлау 455839 = 599·761 деп таптық. Бұл жұмыс істеген себебі, 1=(mod 599) қисығының 1=640 = 27·5 нүктесі бар, ал 1=(mod 761) - 1=777 = 3·7·37 нүктесі бар. Сонымен қатар, 640 және 777 - 1=kP = ∞ 1=(mod 599) және 1=(mod 761) қисықтағы ең кіші оң бүтін сандар. Сегізден бастап! 640-тың еселі, бірақ 777-нің еселі емес, 1=8!P = ∞ 1=(mod 599) қисығында, бірақ 1=(mod 761) қисығында емес, сондықтан қайталанған қосу осында бұзылып, факторландыруды береді.

The following example is from , with some details added. We want to factor 1=n = 455839. Let's choose the elliptic curve 1=y^(2) = x^(3) + 5x – 5, with the point 1=P = (1, 1) on it, and let's try to compute 1=(10!)P. The slope of the tangent line at some point A=(x, y) is 1=s = (3x^(2) + 5)/(2y) (mod n). Using s we can compute 2A. If the value of s is of the form a/b where b > 1 and gcd(a,b) = 1, we have to find the modular inverse of b. If it does not exist, gcd(n,b) is a non trivial factor of n.

First we compute 2P. We have 1=s(P) = s(1,1) = 4, so the coordinates of are and 1== 4(1 – 14) – 1 = –53, all numbers understood 1=(mod n). Just to check that this 2P is indeed on the curve: 1=(–53)2 = 2809 = 143 + 5·14 – 5. Then we compute 3(2P). We have 1=s(2P) = s(14, 53) = –593/106 (mod n). Using the Euclidean algorithm: 1=455839 = 4300·106 + 39, then 1=106 = 2·39 + 28, then 1=39 = 28 + 11, then 1=28 = 2·11 + 6, then 1=11 = 6 + 5, then 1=6 = 5 + 1. Hence 1=gcd(455839, 106) = 1, and working backwards (a version of the extended Euclidean algorithm): 1=1 = 6 – 5 = 2·6 – 11 = 2·28 – 5·11 1== 7·28 – 5·39 = 7·106 – 19·39 = 81707·106 – 19·455839. Hence 1=106−1 = 81707 (mod 455839), and 1=–593/106 = –133317 (mod 455839). Given this s, we can compute the coordinates of 2(2P), just as we did above: 1=4P = (259851, 116255). Just to check that this is indeed a point on the curve: 1=y^(2) = 54514 = x^(3) + 5x – 5 (mod 455839). After this, we can compute
We can similarly compute 4!P, and so on, but 8!P requires inverting 1=599 (mod 455839). The Euclidean algorithm gives that 455839 is divisible by 599, and we have found a 1=factorization 455839 = 599·761. The reason that this worked is that the curve 1=(mod 599) has 1=640 = 27·5 points, while 1=(mod 761) it has 1=777 = 3·7·37 points. Moreover, 640 and 777 are the smallest positive integers k such that 1=kP = ∞ on the curve 1=(mod 599) and 1=(mod 761), respectively. Since 8! is a multiple of 640 but not a multiple of 777, we have 1=8!P = ∞ on the curve 1=(mod 599), but not on the curve 1=(mod 761), hence the repeated addition broke down here, yielding the factorization.

2-кезең

Жоғарыда келтірілген мәтін эллиптік қисықтың факторлауының бірінші кезеңі туралы. Онда p-нің нейтралды элементі болатын жай бөлгіш табуға үміттенеміз, яғни -ның ішіндегі нейтралды элементі болады. Екінші кезеңде q-ның кішкентай жай реті бар жай бөлгіш табуға үміттенеміз, яғни -ның ішінде кішкентай жай реті болады. Бұл реттің мен аралығында болуын күтеміз, мұнда бірінші кезеңде анықталады, ал екінші кезеңнің жаңа параметрі болып табылады. -ның кішкентай ретін тексеру үшін, әрбір жай сан l үшін -ны n модулі бойынша есептеуге болады.

GMP-ECM және EECM-MPFQ

Бұрмаланған Эдвардс эллипстік қисықтары және басқа да техникалар Бернштейн және авторлар тобы қолданды. Егер жеткілікті кубиті бар және классикалық компьютерде EECM-ді іске асыру жылдамдығымен салыстырылатын кванттық компьютер болса, онда ол Гровер алгоритмін пайдаланып, стандартты EECM-ге қарағанда табылған жай сандардың ұзындығын шамамен екі есеге арттырады.