Egész számok faktorizálása

A természetes szám faktorizálása a prímtényezők szorzatára való felbontása . Egy ilyen dekompozíció létezése és egyedisége (a tényezők sorrendjéig) az aritmetika alaptételéből következik .

Ellentétben a szám elsődlegességének felismerésének problémájával, a faktorizálás állítólag számításilag nehéz feladat. Jelenleg nem ismert, hogy létezik-e hatékony nem kvantumfaktorizációs algoritmus egész számokra. Arra azonban nincs bizonyíték, hogy polinomiális időben nincs megoldás erre a problémára.

Az általánosan használt algoritmusok (például az RSA ) középpontjában az a feltételezés áll, hogy nagy számok esetén a faktorizációs probléma számításilag nehéz . A matematika és számítástechnika számos területe talál alkalmazást e probléma megoldásában. Köztük: elliptikus görbék , algebrai számelmélet és kvantumszámítás .

Történelem

Az egész számok faktorizálásának hatékony módjainak megtalálása az ókor óta foglalkoztatja a matematikusokat, különösen a számelméleti szakembereket . Vannak olyan feltételezések, hogy Fermat az elsők között javasolta a dekompozíciós módszert , amely abból áll, hogy egy számot négyzetek különbségeként ábrázolnak , majd kiszámítással megpróbálnak találni egy nem triviális osztót . Ezzel a módszerrel gyorsabban találhatunk egy szám két osztóját, amelyek méretükben alig különböznek egymástól, mint az osztók egyszerű felsorolása [1] . $n=x^{2}-y^{2}$ $\gcd(n,xy)$ $n$

Továbbá Legendre úgy találta, hogy ezzel a megközelítéssel elegendő az összehasonlításhoz , és ehhez folyamatos törteket használt. Ezenkívül Euler és Gauss néhány módszert javasolt az összehasonlításhoz kapcsolódó számok megtalálására [1] . $x^{2}\equiv y^{2}\mod n$

Az egész számok faktorizálásának fejlesztésének egyik kulcsfontosságú mozzanata az RSA algoritmus megalkotása volt , amely megújította a tudósok érdeklődését ez irányba, mivel gyakorlati alkalmazásai voltak a titkosítás területén . Ezt az algoritmust 1977-ben három tudós , Ronald Rivest , Adi Shamir és Leonard Adleman javasolta a Massachusettsi Műszaki Intézetből, és az RSA-módszerrel a szerzők nevének kezdőbetűiről nevezték el. A nyilvános kulcsú kriptográfia elgondolásán alapul, és a rendszer megtöréséhez a számot prímtényezőkre kell bontani. Az RSA algoritmus publikálása idején ismertek olyan módszerek, amelyek lehetővé tették a legfeljebb 25-30 számjegyből álló számok faktorizálását, és továbbra is Fermat módszere volt a leghíresebb és legelterjedtebb. Az RSA módszer lehetővé teszi a számok faktorizálását[ pontosítás ] 100 vagy több tizedesjegy. Az alkotók pedig 129 tizedesjegy faktorizálásáért jelképes száz amerikai dollárt ígértek [2] .

A faktorizációs probléma népszerűségét Martin Gardner 1977 -es Scientific American publikációja is befolyásolta: „A New Encryption Algorithm That Will Take Millions Years Break”. [3] Egy ilyen nagy név kihívást jelent az egész matematikai közösség számára. A verseny eredményeként számos új és nem szabványos faktorizációs ötlet született [2] .

A 129 számjegyből álló számok felbomlásával járó epika 1994-ben ért véget, amikor egy A. Lenstra vezette csapat 1600 számítógép felhasználásával 220 nap alatt elkészítette a több mint félmillió ismeretlent tartalmazó lineáris egyenletrendszert . Ennek a rendszernek a szuperszámítógépes megoldása két napig tartott. Annak ellenére, hogy ekkor már ismerték a számmezőszita módszereket , ezt az eredményt a kvadratikus szita algoritmussal kaptuk [2] .

Faktorizációs algoritmusok

Az ilyen algoritmusok bemenete általában egy faktorizált szám, amely karakterekből áll (ha bináris formában van ábrázolva) [4] . Ebben az esetben az algoritmus megkeresi az első prímosztót, ami után szükség esetén lehetőség van az algoritmus ismételt futtatására további faktorizálás céljából. Ezenkívül, mielőtt elkezdene nagy számot faktorálni, győződjön meg arról, hogy az nem prímszám. Ehhez az egyszerűség kedvéért elegendő a számpróbát teljesíteni. Ez a probléma polinomiális időben determinisztikusan megoldható [5] . $n\in \mathbb {N}$ $N=[\log _{2}n]+1$ $n$

A faktorizációs algoritmusok összetettségüktől függően két csoportra oszthatók. Az első csoportba az exponenciális algoritmusok tartoznak, amelyek bonyolultsága exponenciálisan függ a bemeneti paraméterek hosszától (vagyis magának a számnak a hosszától bináris ábrázolásban). A második csoport a szubexponenciális algoritmusok. $N$

A polinomiális összetettségű faktorizációs algoritmus klasszikus számítógépen való létezésének kérdése a modern számelmélet egyik fontos nyitott problémája . Ugyanakkor kvantumszámítógépen lehetséges a polinomiális komplexitású faktorizálás a Shor algoritmus segítségével ( BQP osztály ) [6] .

Exponenciális algoritmusok

A lehetséges osztók felsorolása

Nehézség ill . $O({\sqrt {n}}\log ^{2}n)$ $O({\sqrt {n}}\log n)$

Az egyik legegyszerűbb és legkézenfekvőbb faktorizációs algoritmus, amely abból áll, hogy a faktorizálható számot szekvenciálisan elosztjuk természetes számokkal -tól -ig . Formálisan ebben az intervallumban elegendő csak prímszámokkal osztani, ehhez azonban ismerni kell a halmazukat. A gyakorlatban a prímszámok táblázatát állítják össze, és a kis számokat ellenőrzik (például -ig ). Nagyon nagy számok esetén az algoritmust a munka alacsony sebessége miatt nem használják [7] . $n$ $2$ $\lfloor {\sqrt {n}}\rfloor$ $2^{16}$

Algoritmus példa [8]

1. lépés: Kezdeti telepítés. Hozzárendelés (Az algoritmus végrehajtása során a változókra a következő feltételek vonatkoznak: és nincs kisebb prímtényezője, mint ) $t=0,k=0,n=N$ $t,k,n$ $n=N/p_{1}...p_{t}$ $n$ $d_{k}$

2. lépés : Ha , az algoritmus véget ér. $n=1?$ $n=1$

3. lépés : Oszd meg. Hozzárendelése (Ide , illetve a szám hányadosa és maradéka osztva a számmal . ) $q=\lfloor n/d_{k}\rfloor ,r=n\mod d_{k}.$ $q$ $r$ $n$ $d_{k}$

4. lépés: A maradék nulla? Ha , akkor folytassa a 6. lépéssel. $r\neq 0$

5. lépés: A szorzó megtalálva. Nagyítson és rendeljen hozzá . Térjen vissza a 2. lépéshez. $t$ $egy$ $p_{t}=d_{k},n=q$

6. lépés. Privát kicsit? Ha , növelje 1-gyel, és térjen vissza a 3. lépéshez. $q>d_{k}$ $k$

7. lépés. n egy prímszám. Növelje meg , rendelje hozzá és fejezze be az algoritmust. $t$ $egy$ $p_{t}=n$

Fermat-féle faktorizációs módszer

Nehézség ill . $Tovább)$ $O(exp(N))$

Az algoritmus lényege, hogy olyan számokat keressen , hogy az n faktorizálható szám a következőképpen ábrázolható legyen: . A próbaosztás módszeréhez hasonlóan a gyakorlatban általában nem alkalmazzák nagy számok faktorálására, mivel exponenciális bonyolultságú. A módszer osztási művelet nélkül, csak összeadás és kivonás műveletekkel valósul meg [9] . Ha , feltéve, hogy és olyan prímszámok, amelyek nagyságrendileg nem különböznek egymástól, akkor Fermat módszere meglehetősen gyorsan faktorizálja n-t [10] . $A$ $B$ $n=A^{2}-B^{2}=(AB)(A+B)$ $n=pq$ $p$ $q$

Példa az algoritmus módosítására [11]

1. lépés: Kezdeti telepítés. Hozzárendelés (Ennek az algoritmusnak a végrehajtása során az x, y, r értékek rendre megfelelnek az egyenletben szereplő értékeknek . A feltételnek teljesülnie kell .) $x=2\lfloor {\sqrt {N}}\rfloor +1,y=1,r=\lfloor {\sqrt {N}}\rfloor ^{2}-N.$ $2x+1,2y+1,x^{2}-y^{2}-N$ $N=uv=x^{2}-y^{2}(x={\dfrac {u+v}{2)),y={\dfrac {uv}{2)))$ $|r|<x,y<x$

2. lépés: Kész? Ha , akkor az algoritmus leáll. Nekünk van $r=0$

N={\frac {xy}{2}}\cdot {\frac {x+y-2}{2}}

3. lépés Lépjen az x-re. Hozzárendelése és . $r=r+x$ $x=x+2$

4. lépés Lépésről y. Hozzárendelése és . $r=ry$ $y=y+2$

5. lépés: Ellenőrizze az r-t. Ha , akkor térjen vissza a 4. lépéshez, ellenkező esetben térjen vissza a 2. lépéshez. $r>0$

Pollard ρ-algoritmusa

Bonyolultság . $O(n^{{1/4}})$

A Pollard-algoritmus egy valószínűségi algoritmus egy összetett szám osztójának megtalálására , olyan bonyolultsággal dolgozik, amely csak az osztó értékétől függ, de nem a faktorizált szám értékétől . Ez megkönnyíti ennek az algoritmusnak az alkalmazhatóságát olyan esetekben, amikor más algoritmusok, amelyek összetettsége függ -től , hatástalanná válnak [12] . Figyelemre méltó az is, hogy létezik egy ilyen algoritmus megvalósításának egy olyan változata, amelyben elegendő csak 3 egész számot tárolni a memóriában [13] . $n$ $n$ $n$

Algoritmus példa [14]

1. lépés : Kiválasztunk egy kis számot , és felállítunk egy számsorozatot , a következő képlet segítségével meghatározva a következőket : $x_{0}$ ${x_{k)),k=0,1,2,...,$ $x_{{k+1}}$ $x_{k+1}=x_{k}^{2}-1\mod n$

2. lépés Ezzel egyidejűleg minden lépésben kiszámítjuk a szám és az összes lehetséges eltérés GCD-jét , ahol . $én$ $d$ $n$ $|x_{i}-x_{j}|$ $j<i$

3. lépés : Ha olyan GCD -t talál , amely eltér a -tól , a számítás véget ér. Talált egy osztó . Ha nem prímszám, akkor az eljárás folytatható a szám helyett . $d=$ $(n,|x_{i}-x_{j}|)$ $egy$ $d$ $n$ $n/d$ $n$ $n/d$

Lenstra algoritmusa

Bonyolultság . $O(n^{{1/3}}\log ^{2}n)$

Annak ellenére, hogy az exponenciális algoritmusok között viszonylag jó a hatékonyság, Lenstra algoritmusában az algoritmus valamelyik lépésében ismételten szükséges a négyzetgyök kiszámítása, ami időigényesebb, mint az összeadás vagy kivonás [15] .

Példa az algoritmus módosítására [16]

Legyenek a feltételeket kielégítő természetes számok $r,s,n$ $1\leq r<s<n;\;n^{{1/3}}<s;\;\gcd(r,s)=1$

1. lépés: Használja az általánosított Euklidész algoritmust a kereséséhez . Találj valamit, ami . $r^{*}\in \mathbb{N} ,rr^{*}\equiv 1\mod s$ $r'$ $r'\equiv r^{*}n\mod s,0\leq r'<s$

2. lépés : A következő értékhez keressen számokat a következő szabályok szerint: $i=0,1,2,...$ $a_{i},b_{i},c_{i}$

a_{0}=s,\;b_{0}=0,\;c_{0}=0

a_{1}=rr'\mod s,0<a_{1}\leq s,\;b_{1}=1,\;c_{1}\equiv {\frac {n-rr'}{s} }r^{*}(\mods)

itt : $i\geq 2$

a_{i}=a_{{i-2}}-q_{i}a_{{i-1}},\;\;b_{i}=b_{{i-2}}-q_{i}b_ {{i-1}},\;\;c_{i}=c_{{i-2}}-q_{i}c_{{i-1}}(\mod s)

$q_{i}$ -vel való osztás hányadosa , kivéve azt az esetet, amikor páratlan, és az osztás maradéka nulla. $a_{{i-2}}$ $a_{i-1}$ $én$

3. lépés : A következő választáshoz keresse meg az összes olyan egész számot , amely megfelel a feltételeknek $a_{i},b_{i},c_{i}$ $c$

$c=c_{i}\mod s$ ,

$|c|<s,\;\;\;\;\;\;$ ha még, $én$

$2a_{i}b_{i}\leq c\leq {\frac {n}{s^{2}}}+a_{i}b_{i},\;\;$ ha páratlan. $én$

4. lépés. A 3. lépéstől kezdve minden c-hez oldja meg az egyenletrendszert egész számokban

$\left\{{\begin{array}{rcl}xa_{i}+yb_{i}\;\;\;\;\;\;&=&c\\(xs+r)(ys+r') &=&n\\\end{tömb}}\jobbra.$

Ha és kiderül, hogy nem negatív egész számok, akkor add hozzá $x$ $y$ $xs+r$

5. lépés Ha , akkor az algoritmus leáll. Ellenkező esetben visszatérünk a 2. lépéshez a következő értékhez . $a_{i}=0$ $én$

Pollard-Strassen algoritmus

Bonyolultság . $O(n^{{1/4}}\log ^{4}n)$

Ennek az algoritmusnak a bonyolultsági becslése hasonló a Shanks kvadratikus forma módszeréhez (amely a legjobb a determinisztikus faktorizációs algoritmusok között), de memóriafoglalást igényel. Közvetlenül használható nem túl nagy egész számok faktorizálására, valamint segédalgoritmusként Dixon szubexponenciális módszerében [17] , valamint a faktorizációs módszer második szakaszának elliptikus görbékkel történő számításainak felgyorsítására . [tizennyolc] $O(n^{1/4}\log n)$

Az algoritmus rövid leírása [15]

Tétel. Hadd . Ekkor bármely természetes számra számtani műveletekben megtalálhatjuk a szám legkisebb prímosztóját . $z\in \mathbb{N} ,y=z^{2}$ $t$ $\gcd(n,y!)$ $O(z\log ^{2}z\log ^{2}t)$

Algoritmus. Hadd . Ezután a tétel algoritmusával megkeressük a szám legkisebb prímosztóját . Mivel ez osztható a szám legkisebb prímosztójával , az algoritmus pontosan ezt a számot adja ki . $z=[n^{{1/4}}]+1,y=z^{2}>n^{{1/2}},t=n$ $\gcd(n,y!)$ $y!$ $p$ $n(p\leq n^{{1/2}}<y)$ $p$

Shanks másodfokú formák módszere

Garantált komplexitás és ha a Riemann-hipotézis igaz . $O(n^{1/4+\varepsilon })$ $O(n^{1/5+\varepsilon })$

A Pollard-Strassen algoritmussal ellentétben nem igényel nagy mennyiségű memória lefoglalását, sőt meglehetősen egyszerű számítási képletekkel rendelkezik [19] .

Pollard P-1 algoritmusa

Bonyolultság [20] . $O(n^{{1/2}}\log ^{c}n)$

Az exponenciális komplexitásbecslés ellenére az algoritmus minden esetben gyorsan megtalálja a kis prímosztókat , mivel ezek hatványsimák a simaság kis határa esetén . Gyakorlati feladatokban ezt az algoritmust általában a szubexponenciális faktorizációs algoritmusok alkalmazása előtt használják egy szám kis prímosztóinak elkülönítésére [20] . $n$ $B$ $n$

A bonyolultság becslése szakaszonként [21]

Az első szakasz nehézségei. , hol a határ [22] $O(B_{1}\log B_{1}\log ^{2}N)$ $B_1$

A második szakasz összetettsége. , hol van az új határ. [23] $O(\log ^{2}B_{2})+O(\log q_{{\pi (B_{1}))))+2(\pi (B_{2})-\pi (B_{1) }))$ $B_{2}$ $B_{2}>>B_{1}$

Lehmann módszere

Bonyolultság . $O(n^{{1/3}})$

Jelenleg az algoritmus inkább történeti, mint gyakorlati érdeklődésre tart számot, mivel ez az algoritmus volt az első determinisztikus algoritmus, amelynek végrehajtása bonyolultabb, mint . $O(\sqrt{n})$

Példa az algoritmus módosítására [24]

1. lépés : Minden től- ig : $p$ $2$ $\lceil {\sqrt[{3}]{m}}\rceil$

Ha , akkor adja vissza az m számot osztóként, és fejezze be az algoritmust. $m\equiv 0\mod p$ $p$

2. lépés : Minden től- ig : $b$ $egy$ $\lceil {\sqrt[{3}]{m}}\rceil$

2.1. lépés Határozza meg és

k = 0

D=\left\lfloor {\frac {\sqrt[{6}]{m)){4{\sqrt {b))))\right\rfloor +1

2.2 lépés Határozza meg és

x=\lfloor {\sqrt {4bm}}\rfloor +k

v=x^{2}-4bm

2.3. lépés Ha tökéletes négyzet, akkor határozza meg és fejezze be az algoritmust.

v

p=\gcd(m,x\pm v)

2.4. lépés: Határozza meg .

k=k+1

2.5. lépés Ha , akkor számítsa ki az új értékét , ellenkező esetben térjen vissza a 2.2. lépéshez

k\geq D

d

3. lépés : Futtassa az algoritmust úgy, hogy értesítse, hogy a faktorizált szám prím. $m$

Szubexponenciális algoritmusok

Az L-jelölés [4] a komplexitás jelölésére szolgál :

L_{n}(\alpha ,\;c):=O(\exp((c+o(1))(\log n)^{\alpha }(\log \log n)^{1 -\alpha })))

hol van a faktorizálandó szám, és van néhány konstans. $n$ $0<\alpha<1$ $c$

Dixon algoritmusa

Bonyolultság . $L_{n}(1/2,\;2{\sqrt {2)))$

Algoritmus példa [25]

1. lépés: Válasszon egy véletlenszerűt , és számítsa ki . $b,1<b<n$ $b^{2}\mod m$

2. lépés. A próbafelosztások megpróbálnak prímtényezőkre bontani a faktorbázisból. $b^{2}\mod m$

3. lépés : Ha egy -szám, azaz.

b

B

b^{2}\mod n=\prod \limits _{{p\in B}}p^{{\alpha _{p}(b)))

, majd emlékezzen és . Ismételje meg a számgenerálási eljárást , amíg meg nem találja a -számokat .

{\vec {\alpha }}(b)

{\vec {\varepsilon }}(b)

b

m=h+1

B

b_{1},...,b_{m}

4. lépés: Keresse meg (például egy homogén lineáris egyenletrendszer megoldásával az ismeretlenek vonatkozásában az ismeretlenek Gauss-féle szekvenciális eliminációjával ) a lineáris függőségi összefüggést $x_{1}{\vec {\varepsilon }}(b_{1})\oplus ...\oplus x_{m}{\vec {\varepsilon }}(b_{m})={\vec {0} }$ $(x_{1},...,x_{m})$

{\vec {\varepsilon }}(b_{{i_{1}}})\oplus ...\oplus {\vec {\varepsilon }}(b_{{i_{t}}})={\vec { 0}},\;\;\;\;\;\;1<t\leq m.

Tedd

x=b_{{i_{1}}}...b_{{i_{t}}},\;\;\;\;\;\;y=\prod \limits _{{p\in B} }p^{{{\frac {1}{2}}({\vec {\alpha _{p}}}(b_{{i_{1}}})+...+{\vec {\alpha _{p}}}(b_{{i_{t}}})))}}

5. lépés: Ellenőrizze . Ha igen, ismételje meg a generálási eljárást. Ha nem, akkor nem triviális dekompozíciót találunk $x\equiv \pm y(\mod n)$

n=u\cdot v,\;\;\;\;\;\;u=(x+y,n),\;\;\;\;\;\;v=(xy,n)

. Faktorizálás folyamatos törtekkel

Bonyolultság [26] . $L_{n}(1/2,\;{\sqrt {2)))$

Kvadratikus szita módszer

Bonyolultság [26] . $L_{n}(1/2,\;1)$

Ez a több polinomot használó módszer hatékony és meglehetősen könnyen megvalósítható számítógépen. Okkal feltételezhető, hogy ez a legismertebb faktorizációs algoritmus (eltekintve az elliptikus görbe faktorizációs módszerétől , amely bizonyos esetekben gyorsabb is lehet. Számok esetében a számmezőszita algoritmusok gyorsabban fognak működni, mint a kvadratikus szita módszer [27]). . $n<10^{{110}}$ $n>10^{{110}}$

Lenstra-faktorizáció elliptikus görbék segítségével

Komplexitás , ahol a legkisebb osztó prím [28] . $L_p(1/2,\;\sqrt{2})$ $p$ $n$

A paraméterek véletlenszerűen kerülnek kiválasztásra. Az értékeket empirikusan kell kiválasztani, figyelembe véve néhány növekvő értéksorozatot [28] . A gyakorlatban az algoritmus adott esetben egyetlen görbével hajtja végre az algoritmust. Ez addig ismétlődik, amíg faktorizálódik, vagy amíg az algoritmus számára rendelkezésre álló idő le nem telik. $a,x,y$ $w,v$ $n,v,w$ $n$

Az algoritmusnak vannak olyan módosításai, amelyek lehetővé teszik, hogy egyszerre több görbével dolgozzunk [28] .

Az algoritmus leírása [28]

Az algoritmus bemenete az a szám , amelyet faktorizálni kell, a -tól függő paraméterek ráadásul úgy vannak beállítva , hogy és a feltétel teljesüljön . Az algoritmus megkeresi a szám természetes osztóját . $n$ $v,w\in \mathbb{N}$ $n$ $a,x,y\in \mathbb{Z } /n\mathbb{Z }$ $P=(x:y:1)\in {\mathbb {V}}_{n}$ $b\equiv y^{2}-x^{3}-ax\mod n$ $6(4a^{3}+27b^{2})\in (\mathbb{Z } /n\mathbb{Z } )^{*}$ $d$ $n,1<d<n$

Mindenki számára támaszkodik $r\in \mathbb{N} ,2\leq r\leq w$

e(r)=max\{m|m\in Z_{{\geq 0)),r^{m}\leq v+2{\sqrt {v))+1\}

Szintén

k=\prod \limits _{{2\leq r\leq w}}r^{{e(r)}}

, egyszerűek.

r

Hadd . Ezután az egyenlet által meghatározott elliptikus görbén fekszik . A pontot az elliptikus görbék feletti aritmetika szabályai szerint kell kiszámítani . Ha a számítás során a szám osztóját találjuk , akkor azt faktorokra bontjuk. Ha megtalálható , de az osztó nem található, akkor az algoritmus leáll, és üzenetet küld a sikertelen faktorizálási kísérletről. $P=(x:y:1\in {\mathbb {V}}_{n})$ $P$ $E_{{a,b}}$ $\mathbb{Z } /n\mathbb{Z }$ $Y^{2}=X^{3}+aX+b$ $kP$ $d$ $n$ $n$ $kP$ $d$

Számmező szita

Jelenleg a leghatékonyabb faktorizációs algoritmusok a számmezőszita variációi [29] :

Speciális szitamódszer bonyolultságú számmezőhöz [30] (a módszer csak speciális típusú számok faktorizálására alkalmazható); $L_{n}(1/3,\;(32/9)^{{{\frac {1}{3)))))$
A komplexitású számmező általános szitamódszere [30] (a módszer minden számra alkalmazható). $L_{n}(1/3,\;(64/9)^{{{\frac {1}{3)))))$

Alkalmazások a kriptográfiában

A faktorizációs probléma feltételezett nagy számítási bonyolultsága bizonyos nyilvános kulcsú titkosítási algoritmusok , például az RSA kriptográfiai erősségének hátterében áll . Sőt, ha az RSA kulcsparaméterek közül legalább egy ismert, akkor a rendszer egyértelműen feltört, emellett számos algoritmus létezik a rendszer összes kulcsának visszaállítására, bizonyos adatok birtokában [31] .

Jelenlegi állapot

1994 márciusában a többszörös polinomi QS kettős variációját használva egy matematikuscsapat Lenstra vezetésével 129 bites (428 bites) számot faktorált. A számításokat önkéntesek végezték az interneten – nyolc hónapig 600 ember és 1600 számítógép dolgozott. A számítógépeket e-mailben kapcsolták össze, és az eredményeiket egy központi adattárba küldték, ahol a végső elemzést elvégezték. Ezek a számítások a QS-t és az öt évvel ezelőtti elméletet alkalmazták, az NFS felgyorsíthatja a számításokat. Tudósok egy csoportja arra a következtetésre jutott, hogy a széles körben használt 512 bites RSA modulokat feltörheti egy olyan szervezet, amely hajlandó több millió dollárt költeni és több hónapot várni [32] .

A faktorizálás művészetének fejlesztése érdekében az RSA Data Security, Inc. 1991 márciusában meghirdette az RSA Factoring Challenge programot (RSA faktoring verseny). A verseny nehéz számok sorozatának faktorálásából áll, amelyek mindegyike két, megközelítőleg azonos méretű prímszám szorzata. Minden prímszámot úgy választottunk ki, hogy 2 modulo 3-hoz kongruens legyen. Összesen 42 számot javasoltak, egy-egy 100-500 számjegy tartományban, 10 jegyű lépésekben (plusz egy további, 129 bites szám. Bővebben: RSA Faktoring Kihívás [ 32] .

Jegyzetek

↑ 1 2 Yashchenko, 1999 , p. 107.
↑ 1 2 3 Ismukhametov, 2011 , p. 7-8.
↑ Gardner M. Egy újfajta titkosítás, amelynek feltörése évmilliókba telik // Sci . amer. - NYC : NPG , 1977. - Vol. 237, Iss. 2. - P. 120-124. — ISSN 0036-8733 ; 1946-7087 - doi:10.1038/SCIENTIFICAMERICAN0877-120
↑ 1 2 Vasilenko, 2003 , p. 9.
↑ Vasilenko, 2003 , p. 48.
↑ Ismukhametov, 2011 , p. 52.
↑ Neszterenko, 2012 , p. 142-143.
↑ Knuth, 2007 , p. 424.
↑ Ismukhametov, 2011 , p. 52-54.
↑ Vasilenko, 2003 , p. 57.
↑ Knuth, 2007 , p. 431.
↑ Ismukhametov, 2011 , p. 64.
↑ Ismukhametov, 2011 , p. 63.
↑ Ismukhametov, 2011 , p. 62.
↑ 1 2 Vasilenko, 2003 , p. 73.
↑ Vasilenko, 2003 , p. 69.
↑ Vasilenko, 2003 , p. 73-74.
↑ 20 éves ECM .
↑ JASON E. GOWER ÉS SAMUEL S. WAGSTAFF, JR. SZÁMÍTÁSI MATEMATIKA . Archiválva az eredetiből 2017. augusztus 24-én.
↑ 1 2 Vasilenko, 2003 , p. 62.
↑ Ismukhametov, 2011 , p. 57.
↑ Ismukhametov, 2011 , p. 55.
↑ Ismukhametov, 2011 , p. 56.
↑ Neszterenko, 2012 , p. 151.
↑ Cseremuskin, 2002 , p. 78.
↑ 1 2 Vasilenko, 2003 , p. 87.
↑ Vasilenko, 2003 , p. 92.
↑ 1 2 3 4 Vasilenko, 2003 , p. 113.
↑ Schneier, 2002 , 11.4.
↑ 1 2 Vasilenko, 2003 , p. 93.
↑ Cseremuskin, 2002 , p. 87.
↑ 1 2 Schneier, 2002 , 11.4.

Irodalom

oroszul

Koblitz N. Számelmélet és kriptográfiai tanfolyam - 2. kiadás - M. : TVP Tudományos Kiadó , 2001. - 254 p. — ISBN 978-5-85484-014-9 , 978-5-85484-012-5
Cheremushkin A. V. Előadások a kriptográfiai aritmetikai algoritmusokról - M .: MTsNMO , 2002. - 104 p. — ISBN 978-5-94057-060-8
Vasilenko O. N. Számelméleti algoritmusok a kriptográfiában - M. : MTsNMO , 2003. - 328 p. — ISBN 978-5-94057-103-2
Ishmukhametov Sh. T. Faktorizációs módszerek természetes számokhoz : tankönyv - Kazan : Kazan University , 2011. - 190 p.
Nesterenko A. Yu. Számelméleti módszerek a kriptográfiában - Moszkva : Moszkvai Állami Elektronikai és Matematikai Intézet , 2012. - 224 p. — ISBN 978-5-94506-320-4
Knuth, D. A számítógépes programozás művészete. - Moszkva: Williams, 2007. - T. 2. - 832 p. - ISBN 978-5-8459-0081-4 .
Bevezetés a kriptográfiába / Yashchenko, V.V. - Moszkva: MTsNMO , 1999. - 272 p. - ISBN 5-900916-40-5 .
Schneier, B. Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód in C. - Moszkva: Triumph, 2002. - 816 p. - 3000 példányban. - ISBN 5-89392-055-4 .

angolul

Bressoud, DM- faktorizáció és elsődlegesség tesztelése. - N. Y .: Springer-Verlag, 1989. - 260 p. - ISBN 0-387-97040-1 .
Mahoney, MS Pierre de Fermat matematikai karrierje . - 2. - Princeton: Princeton Univercity Press, 1994. - P. 324 -332. — 438 p. - ISBN 0-691-03666-7 .

Számok oszthatósági jellemzők szerint
Általános információ	Egész számok faktorizálása Oszthatóság egységes osztó Osztófüggvény prímszám Az aritmetika alaptétele Számtani szám
Faktorizációs formák	prímszám Összetett szám Semiprime téglalap alakú szám Szfenikus szám Négyzet nélküli szám Teljes többszörös Tökéletes diploma Achilles-szám sima szám Normál szám durva szám szokatlan szám
Korlátozott osztókkal	tökéletes szám Kissé elégtelen számok Kissé redundáns számok Többszörösen tökéletes szám Féltökéletes számok hipertökéletes szám szuper tökéletes szám egységes prím féltökéletes szám pararitmiás szám Erdős-Nicolas szám
Számok sok osztóval	Túlzott számok Primitív többletszámok Erősen redundáns számok Szuper redundáns számok Rendkívül felesleges számok szuperkompozit szám Nagyon szuperkompozit szám furcsa szám
Alikvot szekvenciákkal kapcsolatos	szent szám baráti számok nyilvános számok Kvázi baráti számok
Egyéb	Nincs elég szám haver számok szublimált számok Ércszámok szerény szám Egyenlő számjegyek extravagáns szám