ikinci dereceden elek - Quadratic sieve

İkinci dereceden elek algoritması ( QS ) bir tamsayı çarpanlara ayırma algoritmasıdır ve pratikte bilinen en hızlı ikinci yöntemdir ( genel sayı alanı elekten sonra ). 100 ondalık basamağın altındaki tamsayılar için hala en hızlısıdır ve sayı alanı süzgecinden çok daha basittir. Genel amaçlı bir çarpanlara ayırma algoritmasıdır, yani çalışma süresinin özel yapı veya özelliklere değil, yalnızca çarpanlara ayrılacak tamsayının boyutuna bağlı olduğu anlamına gelir . 1981'de Carl Pomerance tarafından Schroeppel'in lineer eleğine bir iyileştirme olarak icat edildi .

Temel amaç

Algoritma , modulo n karelerinin (faktörleştirilecek tam sayı) uyumunu kurmaya çalışır , bu da genellikle n'nin çarpanlara ayrılmasına yol açar . Algoritma iki aşamada çalışır: karelerin uyumuna yol açabilecek bilgileri topladığı veri toplama aşaması; ve topladığı tüm verileri bir matrise koyduğu ve bir kareler uyumu elde etmek için çözdüğü veri işleme aşaması . Veri toplama aşaması birçok işlemciye kolayca paralel hale getirilebilir , ancak veri işleme aşaması büyük miktarda bellek gerektirir ve birçok düğüm üzerinde veya işleme düğümlerinin her birinin tüm matrisi depolamak için yeterli belleği yoksa verimli bir şekilde paralelleştirilmesi zordur. Blok Wiedemann algoritması matrisi tutan her edebilen bir kaç sistemler durumunda kullanılabilir.

Karelerin uyumunu bulmanın naif yaklaşımı, rastgele bir sayı seçmek, karesini almak, n'ye bölmek ve negatif olmayan en küçük kalanın tam kare olmasını ummaktır . Örneğin, . Bu yaklaşım, büyük n için yalnızca nadiren bir kareler uyumu bulur , ancak bir tane bulduğunda, çoğu zaman değil, uygunluk önemsizdir ve çarpanlara ayırma tamamlanır. Bu kabaca Fermat'ın çarpanlara ayırma yönteminin temelidir . ${\displaystyle 80^{2}\equiv 441=21^{2}{\pmod {5959}}}$

İkinci dereceden elek, Dixon'ın çarpanlara ayırma yönteminin bir modifikasyonudur .

İkinci dereceden elek için gereken genel çalışma süresi (bir n tamsayısını çarpanlara ayırmak için )

${\displaystyle e^{(1+o(1)){\sqrt {\ln n\ln \ln n}}}=L_{n}\sol[1/2,1\sağ]}$

içinde L-gösterimde .

e sabiti , doğal logaritmanın tabanıdır.

Yaklaşım

n tamsayısını çarpanlara ayırmak için , Fermat'ın yöntemi a , n ^1/2 <a<n-1 tek bir sayının aranmasını gerektirir , öyle ki a ² bölü n'nin kalanı bir kare olur. Ama bunlar bir bulmak çok zor. İkinci dereceden elek geri kalan işlem oluşur , bir ² / n bazıları için a , o halde ürün bir kare bunların bir alt grubunu bulmak. Bu, karelerin bir uyumunu verecektir.

Örneğin, 1649 sayısını çarpanlarına ayırmayı düşünün . Elimizde: . Tam sayıların hiçbiri kare değildir, ancak ürün bir karedir. biz de vardı ${\displaystyle 41^{2}\equiv 32,42^{2}\equiv 115,43^{2}\equiv 200{\pmod {1649}}}$${\görüntüleme stili 32.115.200}$${\displaystyle 32\cdot 200=80^{2}}$

${\displaystyle 32\cdot 200\equiv 41^{2}\cdot 43^{2}=(41\cdot 43)^{2}\equiv 114^{2}{\pmod {1649}}}$

beri . Böylece karelerin uyumunu veren gözlem${\displaystyle 41\cdot 43\eşdeğer 114{\pmod {1649}}}$${\displaystyle 32\cdot 200=80^{2}}$

${\displaystyle 114^{2}\eşdeğer 80^{2}{\pmod {1649}}.}$

Bu nedenle bazı tamsayılar için . O zaman faktör yapabiliriz ${\displaystyle 114^{2}-80^{2}=(114+80)\cdot (114-80)=194\cdot 34=k\cdot 1649}$${\görüntüleme stili k}$

${\displaystyle 1649=\gcd(194,1649)\cdot \gcd(34,1649)=97\cdot 17}$

En büyük ortak böleni hesaplamak için Öklid algoritmasını kullanmak .

Böylece problem şuna indirgenmiştir: Verilen bir tamsayı kümesi, çarpımı kare olan bir alt küme bulun. By aritmetiğin temel teoremi , herhangi bir pozitif tamsayı asal güçlerin ürünü olarak benzersiz yazılabilir. Bunu vektör formatında yapıyoruz; örneğin, 504'ün asal-güç çarpanlarına ayırması 2 ³ 3 ² 5 ⁰ 7 ^1'dir , bu nedenle üs vektörü (3,2,0,1) ile temsil edilir. İki tamsayıyı çarpmak, üs vektörlerini toplamaya karşılık gelir. Üs vektörü her koordinatta çift olduğunda bir sayı bir karedir. Örneğin, (3,2,0,1) + (1,0,0,1) = (4,2,0,2) vektörleri, yani (504)(14) bir karedir. Bir kare aramak için sadece vektörlerdeki sayıların paritesinin bilinmesi gerekir , bu yüzden bu vektörleri hesaplamak yeterlidir mod 2: (1,0,0,1) + (1,0,0,1) = (0 ,0,0,0). O halde (0,1) vektörlerinden oluşan bir set verildiğinde, sıfır vektör mod 2'ye ekleyen bir altküme bulmamız gerekiyor .

Bu bir lineer cebir problemidir, çünkü halka 2. dereceden Galois alanı olarak kabul edilebilir , yani modulo 2'yi hesaplarken sıfır olmayan tüm sayılara (sadece bir tane vardır, yani 1) bölebiliriz. Bu bir teoremdir. Her vektörden daha fazla vektör girişi olan lineer cebir , lineer bir bağımlılık her zaman mevcuttur. Gauss eliminasyonu ile bulunabilir . Bununla birlikte, mod n birçok rasgele sayının karesini almak, çok fazla sayıda farklı asal faktör ve çok uzun vektörler ve çok büyük bir matris üretir. Hile numaraları için özel olarak bakmaktır bir şekilde bir ² mod n sadece küçük asal çarpanları (bunlar vardır pürüzsüz sayılar ). Bulmak daha zordur, ancak yalnızca düzgün sayılar kullanmak vektörleri ve matrisleri daha küçük ve daha izlenebilir tutar. İkinci dereceden elek , algoritmanın adını aldığı, daha sonra tartışılacak olan eleme adı verilen bir teknik kullanarak düzgün sayıları arar . ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$

algoritma

Özetlemek gerekirse, temel ikinci dereceden elek algoritması şu ana adımlara sahiptir:

1. Bir pürüzsüzlük sınırı seçin B . Sayı π ( B ), asal sayıların sayısını gösteren daha B , vektör uzunluğunu ve gerektiğinde vektörlerin sayısını hem de kontrol eder.
2. (Π bulmak için elekten kullanım B + 1 numara) bir _i şekilde b _ı (= bir _i ² mod N ) 'dir B Pürüzsüz.
3. Faktör B _i ve üstel vektörler oluşturmak her biri için 2 mod.
4. Sıfır vektörüne eklenen bu vektörlerin bir alt kümesini bulmak için lineer cebir kullanın. Karşılık gelen a _i'yi birlikte çarpın ve sonucu mod n'ye a adını verin ; benzer şekilde, b _i ile çarpın, bu da bir B -düz kare b ^{2 verir} .
5. Şimdi elimizde iki karekök ( a ² mod n ) elde ettiğimiz a ² = b ² mod n eşitliği kaldı , bunlardan biri b ² tamsayılarının karekökünü yani b , diğeri ise a hesaplandı. 4. adımda
6. Artık istenen kimliğe sahibiz: . n'nin GCD'sini a ve b farkı (veya toplamı) ile hesaplayın . Bu, önemsiz bir faktör ( n veya 1) olmasına rağmen bir faktör üretir . Faktör önemsizse, farklı bir doğrusal bağımlılık veya farklı bir a ile tekrar deneyin .${\displaystyle (a+b)(ab)\eşdeğer 0{\pmod {n}}}$

Bu makalenin geri kalanında bu temel algoritmanın ayrıntıları ve uzantıları açıklanmaktadır.

Algoritmanın sözde kodu

algorithm Quadratic sieve is
    Choose smoothness bound ${\displaystyle B}$
    let ${\displaystyle t=\pi (B)}$

    for ${\displaystyle i\in {1,...,t+1}}$ do
        Choose ${\displaystyle x\in \{0,\pm 1,\pm 2,...\}}$
        ${\displaystyle a_{i}=x+\lfloor {\sqrt {n}}\rfloor }$
        ${\displaystyle b_{i}=a_{i}^{2}-n}$ (where ${\displaystyle b_{i}=\prod _{j=1}^{t}p_{j}^{e_{i,j}}}$)
        while (check-p_t-smooth(b_i) = false) do
            Let ${\displaystyle v_{i}=(v_{i,1},v_{i,2},...,v_{i,t})=(e_{i,1}{\bmod {2}},e_{i,2}{\bmod {2}},...,e_{i,t}{\bmod {2}})}$
            Find ${\displaystyle T\subseteq \{1,2,...,t+1\}:\sum _{i\in T}v_{i}=0\in \mathbb {Z} _{2}}$
            let ${\displaystyle x=\prod _{i\in T}a_{i}{\bmod {n}}}$
            let ${\displaystyle y=\prod _{j=1}^{t}p_{j}^{\sum _{i\in t}e_{i,j}}{\bmod {n}}}$
            if ${\displaystyle x\not \equiv -y{\bmod {n}}}$ and ${\displaystyle x\not \equiv y}$ then
                return to main loop.
            else if ${\displaystyle x\equiv -y{\bmod {n}}}$:
                return gcd(x - y, n) , gcd(x + y, n)

QS, uygunluk bulmayı nasıl optimize eder?

İkinci dereceden elek girişimler tam sayı çiftleri bulmak x ve y (x) ( y (x) bir fonksiyonu olan x çok daha zayıf koşulu) x ² ≡ y ² (mod n ). Faktör tabanı olarak adlandırılan bir dizi asal sayı seçer ve x'i , y(x) = x ² mod n'nin en küçük mutlak kalanının faktör tabanı üzerinde tamamen çarpanlara ayrılacağı şekilde bulmaya çalışır . Bu tür y değerlerinin faktör tabanına göre düzgün olduğu söylenir .

Faktör tabanına bölünen bir y(x) değerinin x değeriyle birlikte çarpanlara ayrılmasına ilişki denir . İkinci dereceden elek, x'i n'nin kareköküne yaklaştırarak bağıntı bulma sürecini hızlandırır . Bu, y(x)'in daha küçük olmasını ve dolayısıyla pürüzsüz olma şansının daha yüksek olmasını sağlar.

${\displaystyle y(x)=\left(\left\lceil {\sqrt {n}}\right\rceil +x\right)^{2}-n{\hbox{ (burada }}x{\hbox{ küçük bir tamsayıdır)}}}$

${\displaystyle y(x)\yaklaşık 2x\sol\lceil {\sqrt {n}}\sağ\rceil}$

Bu, y'nin 2 x [ √ n ] mertebesinde olduğu anlamına gelir . Bununla birlikte, y'nin x çarpı n'nin karekökü ile doğrusal olarak büyüdüğünü de ima eder .

Düzgünlük şansını arttırmanın bir başka yolu da basitçe faktör tabanının boyutunu arttırmaktır. Ancak doğrusal bir bağımlılığın varlığını sağlamak için faktör tabanındaki asal sayısından daha fazla en az bir düzgün ilişki bulunması gerekir.

Kısmi ilişkiler ve döngüler

Bazı ilişkiler için y(x) düzgün olmasa bile, eğer iki y faktör tabanı dışında aynı asal(lar)ın ürünleriyse, bu kısmi ilişkilerden ikisini tam bir tane oluşturmak için birleştirmek mümkün olabilir . [Bunun faktör tabanını genişletmekle eşdeğer olduğuna dikkat edin.] Örneğin, faktör tabanı {2, 3, 5, 7} ve n = 91 ise, kısmi ilişkiler vardır:

${\displaystyle {21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}}}$

${\displaystyle {29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}}}$

Bunları birlikte çarpın:

${\displaystyle {(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11^{2}{\pmod {91}}}}$

ve her iki tarafı da (11 ⁻¹ ) ² modulo 91 ile çarpın. 11 ⁻¹ modulo 91, 58'dir, yani:

${\displaystyle (58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}$

${\displaystyle 14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}$

tam bir ilişki üretir. Böyle bir tam ilişkiye (kısmi ilişkilerin birleştirilmesiyle elde edilir) çevrim denir . Bazen, iki kısmi ilişkiden bir döngü oluşturmak, doğrudan karelerin uyumuna yol açar, ancak nadiren.

Eleme ile düzgünlüğü kontrol etme

Y s'nin düzgünlüğünü kontrol etmenin birkaç yolu vardır . En belirgin olanı, deneme bölümüdür , ancak bu, veri toplama aşamasının çalışma süresini artırır. Bir miktar kabul gören başka bir yöntem de eliptik eğri yöntemidir (ECM). Pratikte tipik olarak eleme adı verilen bir süreç kullanılır. Eğer f (x) polinomu olduğunu Elimizdeki ${\displaystyle f(x)=x^{2}-n}$

${\displaystyle f(x)=x^{2}-n}$

${\displaystyle f(x+kp)=(x+kp)^{2}-n}$

${\displaystyle f(x+kp)=x^{2}+2xkp+(kp)^{2}-n}$

${\displaystyle f(x+kp)=f(x)+2xkp+(kp)^{2}\equiv f(x){\pmod {p}}}$

Böylece çözme f (x) ≡ 0 (mod p için) x numaralarının bütün dizisi, y olan Y = F (x) = bölünemeyen bunların hepsi, p . Bu, Shanks-Tonelli algoritması gibi verimli algoritmaların mevcut olduğu bir karekök modulo asal bulmaktır . (İkinci dereceden elek adını buradan alır: y , x cinsinden ikinci dereceden bir polinomdur ve eleme işlemi Eratosthenes Kalburu gibi çalışır .)

Elek, büyük bir A [] bayt dizisindeki her girişi sıfıra ayarlayarak başlar . Her p için , α ve β iki kök elde etmek için mod p ikinci dereceden denklemi çözün  ve ardından y ( x ) = 0 mod p ... olan her girişe log( p )'ye bir yaklaşım ekleyin ... yani, A [ kp  +  α ] ve A [ kp  +  β ]. Faktör tabanlı bir asalın küçük kuvvetleriyle bölünebilen sayıları tanımak için p'nin küçük güçleri modulo ikinci dereceden denklemini çözmek de gereklidir .

Faktör tabanının sonunda, kabaca log( x ² -n ) eşiğinin üzerinde bir değer içeren herhangi bir A[] , faktör bazında bölünen bir y ( x ) değerine karşılık gelecektir . Asal bölmek tam olarak ilgili bilgiler y ( x ) kesildi, ancak yalnızca küçük faktörler vardır ve küçük asal, bu tür deneme bölünmesi sadece küçük faktörler, sahip olduğu bilinen bir dizi faktoring çok iyi algoritma bulunmaktadır SQUFOF , Pollard genellikle bazı kombinasyonlarda kullanılan rho ve ECM.

Çalışan birçok y ( x ) değeri vardır, bu nedenle sondaki çarpanlara ayırma işleminin tamamen güvenilir olması gerekmez; genellikle süreçler, örneğin girdilerin %5'inde hatalı davranır ve az miktarda ekstra eleme gerektirir.

Temel elek örneği

Bu örnek, logaritma optimizasyonları veya asal güçler olmadan standart ikinci dereceden elek gösterecektir. Sayı çarpanlarına Let N = 15347, bu nedenle karekökü tavan N yana 124. olan , N : küçük, bazik polinom yeterlidir y ( x ) = ( x + 124) ² - 15347.

Veri toplama

Bu yana , N küçük, sadece 4 asal gereklidir. İlk 4 asal s 15347 kare kök mod sahip olduğu p 2, 17, 23 ve 29 olan (diğer bir deyişle, 15347 a, kuadratik kalıntı , bu asal her modulo). Bu primerler eleme için temel olacaktır.

Şimdi elekimizi oluşturuyoruz ve Y(X)'in ilk 0 ≤ X < 100'ünü elemeyi seçerek, temelde her bir prime için eleme işlemine başlıyoruz: ${\görüntüleme stili V_{X}}$${\displaystyle Y(X)=(X+\lceil {\sqrt {N}}\rceil )^{2}-N=(X+124)^{2}-15347}$

${\displaystyle {\begin{aligned}V&={\begin{bmatrix}Y(0)&Y(1)&Y(2)&Y(3)&Y(4)&Y(5)&\cdots &Y(99)\end {bmatrix}}\\&={\begin{bmatrix}29&278&529&782&1037&1294&\cdots &34382\end{bmatrix}}\end{hizalı}}}$

Bir sonraki adım elek gerçekleştirmektir. Faktör tabanımızdaki her p için denklemi çözün ${\görüntüleme stili \lbrace 2,17,23,29\rbrace }$

${\displaystyle Y(X)\equiv (X+\lceil {\sqrt {N}}\rceil )^{2}-N\equiv 0{\pmod {p}}}$

p ile bölünebilen V dizisindeki girdileri bulmak için .

Çözümü elde etmek için çözmek için . ${\görüntüleme stili p=2}$${\displaystyle (X+124)^{2}-15347\equiv 0{\pmod {2}}}$${\displaystyle X\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}}$

Böylece, X=1'den başlayarak ve 2 ile artırılarak, her giriş 2'ye bölünebilir olacaktır. Bu girişlerin her birini 2'ye bölmek sonuç verir

${\displaystyle V={\begin{bmatrix}29&139&529&391&1037&647&\cdots &17191\end{bmatrix}}}$

Benzer bir şekilde kalan asal için p de denklem çözülür. Her p > 2 için, 2 modüler karekök olması nedeniyle 2 lineer denklem olacağına dikkat edin. ${\displaystyle \lbrace 17,23,29\rbrace }$${\displaystyle X\eşdeğer {\sqrt {15347}}-124{\pmod {p}}}$

${\displaystyle {\begin{aligned}X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 3{\pmod {17}}\\&&\equiv 9-124&\equiv 4{\pmod {17}}\\X&\equiv {\sqrt {15347}}-124&\equiv 11-124&\equiv 2{\pmod {23}}\\&&\equiv 12-124&\equiv 3{\pmod {23} }\\X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 0{\pmod {29}}\\&&\equiv 21-124&\equiv 13{\pmod {29}}\\ \end{hizalanmış}}}$

Her bir denklem ile sonuçlanır göre olan bölünebilir p de X = bir ve her bir p ötesinde değeri verir. Bölme V ile p de bir , bir + s , bir + 2 s , bir +3 s bazında her bir asal için, vb benzersiz asal (ilk güçler) ürünleridir düz numaraları bulur. ${\displaystyle X\eşdeğer bir{\pmod {p}}}$${\görüntüleme stili V_{x}}$

${\displaystyle V={\başlangıç{bmatrix}1&139&23&1&61&647&\cdots &17191\end{bmatrix}}}$

1'e eşit olan herhangi bir V girişi düzgün bir sayıya karşılık gelir. Bu yana , ve eşit bir, bu karşılık için: ${\görüntüleme stili V_{0}}$${\görüntüleme stili V_{3}}$${\görüntüleme stili V_{71}}$

X + 124	Y	faktörler
124	29	2 0 • 17 0 • 23 0 • 29 1
127	782	2 1 • 17 1 • 23 1 • 29 0
195	22678	2 1 • 17 1 • 23 1 • 29 1

matris işleme

Y özelliği ile düzgün sayılar Y bulunduğundan , algoritmanın geri kalanı, Dixon'ın çarpanlara ayırma yönteminin diğer herhangi bir varyasyonuna eşdeğer olarak takip eder . ${\displaystyle Y\eşdeğer Z^{2}{\pmod {N}}}$

Denklemlerin bir alt kümesinin çarpımının üslerini yazma

${\displaystyle {\begin{aligned}29&=2^{0}\cdot 17^{0}\cdot 23^{0}\cdot 29^{1}\\782&=2^{1}\cdot 17^ {1}\cdot 23^{1}\cdot 29^{0}\\22678&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{1}\\\ bitiş{hizalı}}}$

matris verimi olarak: ${\displaystyle {\pmod {2}}}$

${\displaystyle S\cdot {\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&1&1&1\end{bmatrix}}\equiv {\begin{bmatrix}0&0&0&0\end{bmatrix}}{\pmod {2}}}$

Denklemin bir çözümü sol sıfır uzayı tarafından verilir , basitçe

${\displaystyle S={\başlangıç{bmatrix}1&1&1\son{bmatrix}}}$

Böylece tüm 3 denklemin çarpımı bir kare (mod N) verir.

${\displaystyle 29\cdot 782\cdot 22678=22678^{2}}$

ve

${\displaystyle 124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2}}$

Böylece algoritma bulundu

${\displaystyle 22678^{2}\equiv 3070860^{2}{\pmod {15347}}}$

Sonucun test edilmesi, 15347'lik önemsiz bir faktör olan GCD(3070860 - 22678, 15347) = 103'ü verir, diğeri 149'dur.

Bu gösteri aynı zamanda ikinci dereceden elek sadece n büyük olduğunda uygun olduğunu göstermeye hizmet etmelidir . 15347 kadar küçük bir sayı için bu algoritma aşırıya kaçıyor. Deneme bölümü veya Pollard rho , çok daha az hesaplamalı bir faktör bulabilirdi.

Çoklu polinomlar

Pratikte, y için birçok farklı polinom kullanılır , çünkü sadece bir polinom tipik olarak faktör tabanı üzerinde düzgün olan yeterli ( x , y ) çiftleri sağlamayacaktır. Kullanılan polinomlar, modulo n kareleri olması gerektiğinden özel bir forma sahip olmalıdır . Polinomların tümü orijinal y ( x ) = x ² − n ile benzer bir forma sahip olmalıdır :

${\displaystyle y(x)=(Ax+B)^{2}-n\qquad A,B\in \mathbb {Z} }$

A'nın katı olduğunu varsayarsak , y(x) polinomu olarak yazılabilir . O zaman A bir kare ise, sadece faktör dikkate alınmalıdır. ${\ Displaystyle B^{2}-n}$${\ Displaystyle B^{2}-n=AC}$${\displaystyle y(x)=A\cdot (Ax^{2}+2Bx+C)}$${\ Displaystyle (Ax^{2}+2Bx+C)}$

Bu yaklaşım (MPQS, Çoklu Polinom Kuadratik Elek olarak adlandırılır) paralelleştirme için idealdir , çünkü çarpanlara ayırmada yer alan her işlemciye n , faktör tabanı ve bir polinomlar topluluğu verilebilir ve merkezi işlemci ile iletişim kurmasına gerek kalmaz. polinomları bitene kadar.

Büyük asal sayılar

Bir büyük asal

, Daha kısa bir sürede tüm faktörler bölünmesi sonra, sayı (kofaktörü) geri kalan kısmı daha kısa bir sürede ise ² , bu kofaktör asal olmalıdır. Aslında, ilişkiler listesini kofaktöre göre sıralayarak faktör tabanına eklenebilir. y(a) = 7*11*23*137 ve y(b) = 3*5*7*137 ise, o zaman y(a)y(b) = 3*5*11*23 * 7 ² * 137 ² . Bu, üzerinde tam bir çarpanlara ayırmanın gerçekleştirildiği eleme dizisindeki girişlerin eşiğini azaltarak çalışır.

Daha büyük asal sayılar

Eşiği daha da azaltmak ve y(x) değerlerini nispeten büyük asal sayıların bile çarpımlarına ayırmak için etkili bir süreç kullanmak - ECM bunun için mükemmeldir - faktör bazında faktörlerin çoğuyla ilişkiler bulabilir, ancak iki veya hatta üç büyük asal sayı. Döngü bulma daha sonra birkaç asal değeri paylaşan bir dizi ilişkiyi tek bir ilişkide birleştirmeye izin verir.

Gerçekçi örnekten parametreler

Çoklu polinom ve büyük asal optimizasyonlar dahil olmak üzere gerçek bir uygulamada gerçekçi bir örnek için tipik parametre seçimlerini göstermek için, msieve aracı 267 bitlik bir yarı asal üzerinde çalıştırılarak aşağıdaki parametreleri üretti:

• Deneme faktoring sınırı: 27 bit
• Elek aralığı (polinom başına): 393216 (12 blok 32768 boyutunda)
• Düzgünlük sınırı: 1300967 (50294 asal)
• Polinom A katsayıları için faktör sayısı : 10 ( yukarıdaki Çoklu polinomlara bakın )
• Büyük asal sınır: 128795733 (26 bit) ( yukarıdaki Büyük asal sayılara bakın )
• Pürüzsüz değerler bulundu: 25952 doğrudan eleyerek, 24462 sayıları büyük asal sayılarla birleştirerek
• Son matris boyutu: 50294 × 50414, filtrelenerek 35750 × 35862'ye düşürüldü
• Bulunan önemsiz bağımlılıklar: 15
• Toplam süre (1.6 GHz UltraSPARC III'te): 35 dk 39 saniye
• Kullanılan maksimum bellek: 8 MB

Faktoring kayıtları

Sayı alanı eleğinin (NFS) keşfine kadar , QS asimptotik olarak en hızlı bilinen genel amaçlı faktoring algoritmasıydı. Şimdi, Lenstra eliptik eğri çarpanlarına ayırma , QS ile aynı asimptotik çalışma süresine sahiptir ( n'nin tam olarak eşit boyutta iki asal faktöre sahip olduğu durumda ), ancak pratikte, QS, çoklu kesinlik yerine tek kesinlikli işlemleri kullandığı için daha hızlıdır. eliptik eğri yöntemi tarafından kullanılan işlemler.

2 Nisan 1994'te RSA-129'un çarpanlara ayrılması QS kullanılarak tamamlandı. Biri 64, diğeri 65 olmak üzere iki büyük asal sayının çarpımı olan 129 basamaklı bir sayıydı. Bu çarpanlara ayırmanın çarpan tabanı 524339 asal sayı içeriyordu. Veri toplama aşaması , İnternet üzerinden dağıtılmış bir şekilde yapılan 5000 MIPS yılını aldı . Toplanan verilerin toplamı 2 GB'dir . Bellcore'un (şimdi Telcordia Technologies ) MasPar (büyük ölçüde paralel) süper bilgisayarında veri işleme aşaması 45 saat sürdü . Bu, 10 Nisan 1996'da tamamlanan RSA-130'u çarpanlara ayırmak için NFS kullanılana kadar, genel amaçlı bir algoritma tarafından yayınlanan en büyük çarpanlara ayırma işlemiydi. O zamandan beri çarpanlara ayrılan tüm RSA sayıları NFS kullanılarak çarpanlara ayrıldı.

Mevcut QS çarpanlara ayırma kaydı, Patrick Konsor tarafından Haziran 2020'de 6 gün boyunca yaklaşık 6.000 çekirdek saati kullanılarak çarpanlarına ayrılan 140 basamaklı (463 bit) RSA-140'tır.

Uygulamalar

• PPMPQS ve PPSIQS
• mpq'ler
• SIMPQS , William Hart tarafından yazılmış, kendi kendini başlatan çoklu polinom ikinci dereceden eleklerin hızlı bir uygulamasıdır. Büyük asal değişken için destek sağlar ve lineer cebir aşaması için Jason Papadopoulos'un blok Lanczos kodunu kullanır. SIMPQS'e SageMath bilgisayar cebir paketindeki qsieve komutu olarak erişilebilir veya kaynak biçiminde indirilebilir. SIMPQS, Athlon ve Opteron makinelerinde kullanım için optimize edilmiştir, ancak en yaygın 32 ve 64 bit mimarilerde çalışır. Tamamen C ile yazılmıştır.
• Dario Alpern tarafından, belirli koşullar karşılandığında ikinci dereceden elek kullanan bir faktoring uygulaması .
• PARI / GP bilgisayar cebir paketi büyük asal varyantı uygulayan kendini başlatılıyor çoklu polinom kuadratik elek bir uygulamayı içermektedir. Thomas Papanikolaou ve Xavier Roblot tarafından LiDIA projesi için yazılmış bir elekten uyarlanmıştır. Kendi kendini başlatma şeması, Thomas Sosnowski'nin tezinden bir fikre dayanmaktadır.
• MAGMA bilgisayar cebir paketinde ikinci dereceden eleğin bir çeşidi mevcuttur . Arjen Lenstra'nın "e-posta ile faktoring" programında kullandığı 1995 tarihli bir uygulamasına dayanmaktadır.
• msieve , Jason Papadopoulos tarafından yazılmış, tek ve çift büyük asal sayıları destekleyen çoklu polinom ikinci dereceden elek uygulamasının bir uygulaması. Kaynak kodu ve bir Windows ikili dosyası mevcuttur.
• YAFU Ben Buhrow tarafından yazılmış, daha hızlı, en modern için msieve benzer ancak işlemciler . Jason Papadopoulos'un blok Lanczos kodunu kullanır. Windows ve Linux için kaynak kodu ve ikili dosyalar mevcuttur.
• Ariel , didaktik amaçlar için ikinci dereceden eleğin basit bir Java uygulaması.
• Java-matematik-kütüphane muhtemelen Java ile yazılmış en hızlı ikinci dereceden elek (PSIQS 4.0 halefi) içeriyor.
• Java QS , temel QS uygulamasını içeren açık kaynaklı bir Java projesidir. 4 Şubat 2016'da İlya Gazman tarafından yayınlandı

Ayrıca bakınız

• Lenstra eliptik eğri çarpanlarına ayırma
• asallık testi

Referanslar

• Samuel S. Wagstaff, Jr. (2013). Faktoringin Keyfi . Providence, RI: Amerikan Matematik Derneği. s. 195-202. ISBN'si 978-1-4704-1048-3.

Diğer dış bağlantılar

• Referans kağıt "Kuadratik Elek Faktoring Algoritması" Eric Landquist tarafından