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] .

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] .

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] .

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.

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 .

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] .

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 )

2. lépés : Ha , az algoritmus véget ér.

3. lépés : Oszd meg. Hozzárendelése (Ide , illetve a szám hányadosa és maradéka osztva a számmal . )

4. lépés: A maradék nulla? Ha , akkor folytassa a 6. lépéssel.

5. lépés: A szorzó megtalálva. Nagyítson és rendeljen hozzá . Térjen vissza a 2. lépéshez.

6. lépés. Privát kicsit? Ha , növelje 1-gyel, és térjen vissza a 3. lépéshez.

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

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

Nehézség ill .

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] .

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 .)

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

3. lépés Lépjen az x-re. Hozzárendelése és .

4. lépés Lépésről y. Hozzárendelése és .

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.

Pollard ρ-algoritmusa

Bonyolultság .

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] .

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 :

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 .

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 .

Lenstra algoritmusa

Bonyolultság .

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

1. lépés: Használja az általánosított Euklidész algoritmust a kereséséhez . Találj valamit, ami .

2. lépés : A következő értékhez keressen számokat a következő szabályok szerint:

itt :

-vel való osztás hányadosa , kivéve azt az esetet, amikor páratlan, és az osztás maradéka nulla.

3. lépés : A következő választáshoz keresse meg az összes olyan egész számot , amely megfelel a feltételeknek

,

ha még,

ha páratlan.

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

Ha és kiderül, hogy nem negatív egész számok, akkor add hozzá

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 .

Pollard-Strassen algoritmus

Bonyolultság .

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]

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 .

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 .

Shanks másodfokú formák módszere

Garantált komplexitás és ha a Riemann-hipotézis igaz .

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] .

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] .

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

Az első szakasz nehézségei. , hol a határ [22]

A második szakasz összetettsége. , hol van az új határ. [23]

Lehmann módszere

Bonyolultság .

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 .

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

1. lépés : Minden től- ig :

Ha , akkor adja vissza az m számot osztóként, és fejezze be az algoritmust.

2. lépés : Minden től- ig :

2.1. lépés Határozza meg és 2.2 lépés Határozza meg és 2.3. lépés Ha tökéletes négyzet, akkor határozza meg és fejezze be az algoritmust. 2.4. lépés: Határozza meg . 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

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

Szubexponenciális algoritmusok

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

hol  van a faktorizálandó szám, és  van néhány konstans.

Dixon algoritmusa

Bonyolultság .

Algoritmus példa [25]

1. lépés: Válasszon egy véletlenszerűt , és számítsa ki .

2. lépés. A próbafelosztások megpróbálnak prímtényezőkre bontani a faktorbázisból.

3. lépés : Ha egy -szám, azaz. , majd emlékezzen és . Ismételje meg a számgenerálási eljárást , amíg meg nem találja a -számokat .

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

Tedd

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

. Faktorizálás folyamatos törtekkel

Bonyolultság [26] .

Kvadratikus szita módszer

Bonyolultság [26] .

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]). .

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

Komplexitás , ahol  a legkisebb osztó prím [28] .

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.

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 .

Mindenki számára támaszkodik

Szintén

, egyszerűek.

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.

Számmező szita

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

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. 1 2 Yashchenko, 1999 , p. 107.
  2. 1 2 3 Ismukhametov, 2011 , p. 7-8.
  3. 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
  4. 1 2 Vasilenko, 2003 , p. 9.
  5. Vasilenko, 2003 , p. 48.
  6. Ismukhametov, 2011 , p. 52.
  7. Neszterenko, 2012 , p. 142-143.
  8. Knuth, 2007 , p. 424.
  9. Ismukhametov, 2011 , p. 52-54.
  10. Vasilenko, 2003 , p. 57.
  11. Knuth, 2007 , p. 431.
  12. Ismukhametov, 2011 , p. 64.
  13. Ismukhametov, 2011 , p. 63.
  14. Ismukhametov, 2011 , p. 62.
  15. 1 2 Vasilenko, 2003 , p. 73.
  16. Vasilenko, 2003 , p. 69.
  17. Vasilenko, 2003 , p. 73-74.
  18. 20 éves ECM .
  19. JASON E. GOWER ÉS SAMUEL S. WAGSTAFF, JR.  SZÁMÍTÁSI MATEMATIKA . Archiválva az eredetiből 2017. augusztus 24-én.
  20. 1 2 Vasilenko, 2003 , p. 62.
  21. Ismukhametov, 2011 , p. 57.
  22. Ismukhametov, 2011 , p. 55.
  23. Ismukhametov, 2011 , p. 56.
  24. Neszterenko, 2012 , p. 151.
  25. Cseremuskin, 2002 , p. 78.
  26. 1 2 Vasilenko, 2003 , p. 87.
  27. Vasilenko, 2003 , p. 92.
  28. 1 2 3 4 Vasilenko, 2003 , p. 113.
  29. Schneier, 2002 , 11.4.
  30. 1 2 Vasilenko, 2003 , p. 93.
  31. Cseremuskin, 2002 , p. 87.
  32. 1 2 Schneier, 2002 , 11.4.

Irodalom

oroszul 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 .