Praštevilski razcep

Práštevílski razcép (práštevilska faktorizácija, prafaktorizácija ali razcép na práfáktorje) števila je predstavitev števila, kot zmnožek manjših števil, deliteljev (faktorjev). Vsako pozitivno celo število, večje od 1, je bodisi zmnožek dveh ali več celih faktorjev, večjih od 1, v tem primeru je sestavljeno število, bodisi ni, v tem primeru je praštevilo. Na primer, 15 je sestavljeno število, ker je 15 = 3 · 5, 7 pa je praštevilo, ker ga ni mogoče razstaviti na ta način. Če je eden od faktorjev sestavljen, se ga lahko zapiše kot zmnožek manjših faktorjev, na primer 60 = 3 · 20 = 3 · (5 · 4). Nadaljevanje tega postopka, dokler ni vsak faktor praštevilo, se imenuje razcep (faktorizacija) praštevil  – rezultat je vedno enoličen do vrstnega reda faktorjev po osnovnem izreku aritmetike (izreku o faktorizaciji praštevil). Tako se pride do osnovnih gradnikov števil prafaktorjev, oziroma praštevil: 60 = 2 · 2 · 3 · 5, kar se zapiše kot $60=2^{2}\cdot 3\cdot 5\!\,$.

Zgled drevesnega diagrama razcepa števila $n=864=2^{5}\cdot 3^{3}\!\,$

Za razcep majhnega celega števila $n\!\,$ z uporabo miselne ali papirnate aritmetike je najpreprostejša metoda poskusno deljenje: preverjanje, ali je število deljivo s praštevili 2, 3, 5 in tako naprej, do kvadratnega korena števila $n\!\,$. Za večja števila, zlasti pri uporabi računalnika, so učinkovitejši različni bolj sofisticirani algoritmi za razcep. Algoritem za preštevilski razcep običajno vključuje preverjanje, ali je vsak faktor praštevilo vsakič, ko je faktor najden.

Ko so števila dovolj velika, ni znan noben učinkovit algoritem za razcep nekvantnih celih števil. Vendar ni bilo dokazano, da tak algoritem ne obstaja. Domnevna težavnost tega problema je pomembna za algoritme in postopke, ki se uporabljajo v kriptografiji, kot sta šifriranje z javnim ključem RSA in digitalni podpis RSA (DSA). S tem problemom so se ukvarjala mnoga področja matematike in računalništva, vključno z eliptičnimi krivuljami, algebrsko teorijo števil in kvantnim računanjem.

Vsa števila dane dolžine ni enako težko razcepiti. Najtežji primeri teh problemov (za trenutno znane tehnike) so polpraštevila, zmnožek dveh praštevil. Ko sta obe veliki, na primer dolgi več kot dva tisoč bitov, naključno izbrani in približno enake velikosti (vendar ne preblizu, na primer, da bi se izognilo učinkovitemu razcepu s Fermatovo metodo razcepa), lahko tudi najhitrejši algoritmi za praštevilski razcep na najhitrejših klasičnih računalnikih trajajo dovolj dolgo, da je iskanje nepraktično  – to pomeni, da se s povečanjem števila števk razceplenega celega števila drastično poveča število operacij, potrebnih za izvedbo razcepa na poljubnem klasičnem računalniku.

Mnogi kriptografski protokoli temeljijo na domnevni težavnosti razcepa velikih sestavljenih celih števil ali sorodnem problemu  – na primer problemu RSA. Algoritem, ki učinkovito razceplja poljubno celo število, bi kriptografijo z javnim ključem, ki temelji na RSA, naredil nezanesljivo.

Razcepi se lahko tudi polinome in matrike.

Zgled

Diagram deljenja

${\begin{array}{r|l}72&2\\36&2\\18&2\\9&3\\3&3\\1&\end{array}}$

Glej tudi

• algoritmi za razcep števila
• Eratostenovo sito
• praštevilski izrek (izrek o praštevilih)
• osnovni izrek aritmetike
• osnovni izrek algebre

Viri

• Lenstra, Arjen Klaas (2011), »Integer Factoring«, v van Tilborg, Henk C. A.; Jajodia, Sushil (ur.), Encyclopedia of Cryptography and Security, Boston: Springer, str. 611–618, doi:10.1007/978-1-4419-5906-5_455, ISBN 978-1-4419-5905-8

Zunanje povezave

• »Factoris«, wims.unice.fr} (v angleščini)