Gyakorlatban mi nehezebb probléma: nagy prímek szorzatának a faktorizációja vagy kis prímek nagy hatványainak szorzatának a faktorizációja?

Pontosítsd a kérdésedet.

Ha kis prímeket ismert hatványra emelünk, akkor viszonylag kevés próbálkozással megoldható. Ha a hatványkitevő is véletlenszerű, akkor engem is érdekel a válasz.

Kísérletképpen két nagy prím szorzata:

a = 170,141,183,460,469,231,731,687,303,715,884,105,727

b = 20,988,936,657,440,586,486,151,264,256,610,222,593,863,921

A kettő szorzata egy 82 számjegyű szám.

A [link] oldalra bemásoltam, prímtényezőkre bontás nálam majdnem pontosan 10 percig tartott.

Kiszámoltam a 29^10000-t. Ez egy 14624 számjegyű szám, nyilván sok-sok nagyságrenddel nagyobb az előbbinél. Ugyanezen az oldalon a prímtényezőkre bontás 0,7 másodpercig tartott.

~ ~ ~

Ha tehát a kérdés az, hogy egy közel ugyanolyan nagyságrendű szám esetén akkor nehezebb-e a prímtényezőkre bontás, ha a szám két nagy prím szorzata, vagy ha sok kis prím szorzata, akkor a válasz az, hogy az előbbi sokkal nehezebb. A 29^10000 esetén a dolog könnyebb. Osztod 2-vel, 3-mal, 5-tel, egyikkel sem osztható, de így a prímeken haladva a 10. lépésben kiderül, hogy 29-cel osztható a szám. Innen már az osztás eredményével kell tovább számolni. Ezt a tíz osztás tízezerszer kell ismételni, és megkapod a prímtényezőket. Ez összesen százezer osztás lesz.

Ha viszont az első példát nézzük, akkor osztani kell 2-vel, 3-mal, 5-tel stb. stb… Egyikkel sem lesz osztható. A prímszámtétel alapján a fenti példában jelzett „a” szám előtt van majdnem 2 szextillió darab prím. Még ha ismernénk is addig az összes számról, hogy prím-e vagy sem – így csak a prímekkel kellene az oszthatóságot ellenőrizni –, akkor is 10^36 nagyságrendű osztási kísérlet után kapnánk meg az első prímtényezőt, és az osztás után kapott „b” számról még mindig nem tudhatjuk teljes bizonysággal, hogy prím-e vagy sem, azt fel kell-e bontani prímtényezőkre vagy sem. (A prímtesztek itt nem nyújtanak teljes bizonyosságot.) Lehet trükközni persze, amivel ennél jóval kevesebb számítást igényel egy ekkora szám prímtényezőkre bontása, de így is jóval nagyobb feladat, mint a második eset.

~ ~ ~

De lehet más az összehasonlítási alap. Ha veszünk két prímet, egy kicsit és egy (nem túl) nagyot, mondjuk:

a = 11

b = 69313

Akkor azt kapjuk, hogy az a^b egy elég nagy szám lesz, egy 72 183 számjegyű szám, így a b^a egy jóval kisebb, 54 jegyű szám lesz. Nem érzem azt, hogy igazságos lenne egy súlycsoportban indítani őket.

> de így a prímeken haladva a 10. lépésben kiderül, hogy 29-cel osztható a szám. Innen már az osztás eredményével kell tovább számolni. Ezt a tíz osztás tízezerszer kell ismételni, és megkapod a prímtényezőket. Ez összesen százezer osztás lesz.

Módosítás: Mivel tudod, hogy az eredeti szám 29-nél kisebb prímekkel nem osztható, így az első 29-cel való osztás után már csak 29-től kell indítani az osztási kísérleteket, így nem százezer, hanem csak alig több, mint tízezer osztás után megkapod a prímtényezőket.

#2: "Kísérletképpen két nagy prím szorzata:"

Legyen pl. a szorzat:

1545098039215686274509803921568627451480650567647058823529411764705882352981668800396553

Próbáld ki a linkeden, vagy itt, ahol ugyanez a faktorizáció csak 1 mp!!!

[link]

A lényeg, hogy ha 2, vagy több nagy prím (pl. 100+ számjegyű) van a szorzatban, akkor a faktorizáció nagyon nehéz, különben könnyű.

#4: Érdekes…

A te szorzatod 88 számjegyű, az én két nagy prímem szorzata viszont csak 82 számjegyű. Az én számom esetén a WolframAlpha nem írja ki a prímtényezőit, mondván „Standard computation time exceeded...”. Lásd: [link]

A te számod esetén viszont az általam linkelt oldal kb. 35 percre saccolja a kiszámításhoz szükséges időt.

Sejtésem szerint a WolframAlpha valamilyen mélységben cache-el, így nem azért írja ki a te szorzatodra 1 másodperc alatt a prímtényezőket, mert ennyi idő volt neki kiszámolni, hanem mert csak elő kell kapnia azt az eredményt, amit fene tudja milyen hosszadalmasan számolt ki korábban, majd eltárolta, hogy ha valaki ugyanerre kérdez rá, akkor megspórolja az újraszámítás idejét. Amit linkeltem a #2-es válaszomban, az viszont kliens oldalon ténylegesen számol, nincs benne ilyen jellegű cache-elés.

#5: "Sejtésem szerint a WolframAlpha valamilyen mélységben cache-el ..."

Nem erről van szó, természetesen, hiszen az ilyen számok ugyan ritkák, de mégis sok kvadrillió lehet, tehát mindet kiszámolni, tárolni lehetetlen - és felesleges.

Valóban ilyen gyorsan számolható! Nem az ECM, vagy QS, egyszerűbb, Rabin-Miller alapokon.

Részleteket csak akkor írok, (milyen tulajdonságú számoknál és hogyan működik a "csodamódszer" :D ), ha valakit érdekel.

1. vagyok

x n. Hátránya az x*x*x*x*...

Ez könnyen feloldharó

"bankok éppen két nagy prím szorzatát használják alapvető biztonsági rendszerként"

Ha a TLS protokollra gondolsz (a bankok is használják) az nem kimondottan bank specifikus. A TLS protokollnak része az RSA aminek erőssége 2 prímszám szorzatának faktorizációjának nehézsége. A TLS protkollban RSA helyett használható elliptikus görbe is, így nem feltétlen prímszámokat használ a bank sem, ez a digitális tanúsítványtól függ, hogy RSA vagy elliptikus görbe.

A TLS-nél az RSA-ban kulcsgenerálásnál, hogy hogyan kell prímszámokat választani úgynevezett erős prímeket, azt is leírja a megfelelő RFC, vagyis a kiválasztás szigorúbb mint simán randomizálva választani prímszámokat.