Primfaktorzerlegung

D Primfaktorzerleegig isch d Daarstellig von ere natürlige Zaal $n$ as Brodukt us Primzaale, wo denn as Primfaktore vo $n$ bezäichnet wärde. Die Daarstellig isch (bis uf d Räijefolg vo de Faktore) äidütig und zelt zu de grundlegende und klassische Wärkzüüg vo dr Zaaletheorii. Si isch dr Geegestand vom Fundamentalsatz vo dr Arithmetik. Bis jetz isch käi effiziänts Faktorisierigsverfaare bekannt, zum irgend e Zaal in sini Primfaktore z zerleege. Dr Exponänt $e_k$ vom ene Primfaktor $p_k$ isch d Vilfachhäit vo $p_k$ in $n$ und wird au as $p_k$-Bewärtig vo $n$ bezäichnet. Er git aa, wie mänggisch $n$ dur $p_k$ däilbar isch.

Bischbil

Au uf em Dreiegggitter vo de Eisenstein-Zaale git s für jede Gitterpunkt e Primfaktorzerleegig

$30=2\cdot 3\cdot 5$

$37=37$ (Primzahl)

$1001=7\cdot 11\cdot 13$

$1024=\underset{\text{10-mal}}{\underbrace{2\cdots 2}}=2^{10}$ (Zwäierpotänz)

$6936=2\cdot 2\cdot 2\cdot 3\cdot 17\cdot 17$, mit dr kanonische Daarstellig $2^3\cdot 3\cdot 17^2$

$10000=2^4\cdot 5^4$ (Zäänerpotänz)

Braktischi Aawändig

Us dr Primfaktorezerleegig gseet mä, öb e Zaal dur en anderi däilbar isch. S chlinste gmäinsame Vielfache (kgV) und dr grössti gmäinsami Däiler (ggT) chönne liicht us dr Primfaktorzerleegig bestimmt wärde. In dr Bruchrächnig chönne Brüch dur e ggT vom Zeler und vom Nenner kürzt wärde. Bim Addiere und Subtrahiere vo Brüch wärde die uf e chlinst gmäinsami Nenner erwiteret.

Krüptografii

E wichdigi Rolle spiile d Primzaale in dr Krüptografii. Verschlüsseligssüsteem wie RSA basiere druf, ass käi effiziänts Faktorisierigsverfaare bekannt isch. Eso isch s in Sekunde ooni Brobleem mööglig, ass mä zwäi 500-stelligi Primzaale cha finde und mitenander cha multipliziere. Mit de hütige Methode wurd s aber seer lang duure, zum die bäide Primfaktore vo däm 999- oder 1000-stellige Brodukt z finde.

Litratuur

• Vorlage:Literatur

Weblingg

• Factorization database vom Markus Tervooren – schnälli Verarbäitig, bis zu 200'000 Dezimalstelle
• Die Primzahlseite vom Arndt Brünner – brucht JavaScript, im Inhalt u. a. d Primfaktorzerleegig
• Factorization using the Elliptic Curve Method – Java-Applet, verarbäitet Iigoobe bis 10'000 Dezimalstelle