Das deutsche QBasic- und FreeBASIC-Forum

[ChâteauDeSenf]

[psygate]

Hab hier mal gestöbert... Wollte nur wissen, ob chateau noch da ist uind seinen beitrag sinnvoller verfassen kann...
_________________
Danke an Volta für seine großartige MMX_fade function. *verneig*
Personal-DNA:
<script src="http://personaldna.com/h/?k=qtrCFboSuCOpFrX-OI-AADBA-f78d&t=Free-Wheeling+Leader">
</script>

[Triton]

Ich beschäftige mich seit geraumer Zeit nun mit dem Thema und habe inzwischen (allerdings in BlitzBasic) eine recht leistungsfähige Sammlung von Funktionen geschrieben, um mit beliebig langen Zahlen rechnen zu können. Ich möchte daher mal berichten, dass das ganze nicht so einfach ist, wie man es sich oft vorstellt.

2 Fragen wurden hier gestellt, soweit ich das sehe:


1. Wie teste ich eine große Zahl auf ihre Primeigenschaft?
2. Wie faktorisiere ich eine große Zahl nach RSA-Muster in ihre 2 Primfaktoren?


zum ersten:
Also ein normaler Primzahltest funktioniert so, dass man von der 2 ausgehend alle Primzahlen testet, ob sie die zu testende Zahl teilen.
Wenn also die Gleichung

p mod a = r

den Wert 0 für r ergibt, teilt ergibt die Rechnung p/a keinen Rest und p ist somit keine Primzahl.
Ist es doch eine Primzahl, muss man bis zur Wurzel der Zahl alle Primzahlen als Teiler testen.
In der Praxis kennt man aber eben nicht alle Primzahlen bis zur Wurzel einer Zahl. Da reicht es dann auch alle Zahlen zu testen, die in den Term 6n +- 1 passen (da Primzahlen nur welche sein können, wenn sie diese Bedingung erfüllen - jedoch ist nicht jede dieser Zahlen auch eine Primzahl, das wäre ja zu einfach ).

Damit testet man also nurnoch 1/3 aller Zahlen als Teiler. Da sind dann auch ein paar zusammengesetzte Zahlen dabei, die man nicht testen müsste, aber das weiß man ja vorher nicht.

Nach dieser Methode muss man also bei einer Zahl p genau 1/3*sqr(p)
Zahlen testen, um festzustellen, ob sie Prim ist.
Bei 10^80 + 129 (was die erste Primzahl über 10^80 ist), muss man also
nicht weniger als 3,3333 * 10^39 Zahlen testen.
Angenommen, man schafft 10000 pro Sekunde, dauert das etwa
10'569'930'661'254'862'168'104'177'236 Jahre. Also rund 10^28 Jahre (unser Universum ist erst 10^10 Jahre alt..).

Viel Glück

Diese einfache Probedivision ist also nicht geeignet, um große Zahlen
auf ihre Primeigenschaft zu testen. Für diverse Spezialformen gibt es aber
weitaus schnellere Methoden.
z.B für Zahlen der form n = 2^p -1, wobei p selbst eine Primzahl ist.
Das sind die Mersenne'schen Primzahlen, für die es den Lucas-Lehmer-Test gibt, der nur p durchgänge braucht, um festzustellen, ob es eine Primzahl ist. Mit meinem Programm schaffte ich es so festzustellen, dass
2^607 -1 (eine Zahl mit 182 Stellen) prim ist. Das dauerte 1607 Sekunden (~27 min). Für die aktuelle Rekordprimzahl 2^30402457 -1
hätte aber auch das bei mir zumindest tausende von Jahren gebraucht.

Wie dann diese Rekordprimzahl überhaupt gefunden werden konnte?
Nun, erstens durch wesentlich schnellere Programme (die auf Bitebene arbeiten, statt wie wir mit Strings) und verteiltem Rechnen, an dem viele
viele einzelne Rechner teilnehmen (-> www.gimps.org).

zu zweitens
Das umgekehrte Problem zum finden einer Primzahl ist es, aus einer vorhandenen Zahl zu ermitteln, aus welcher Multiplikation von 2 Primzahlen sie entstanden ist. Dass das so schwer ist, macht das RSA-Kryptosystem so sicher.

Eine "normale" Faktorisierung funktioniert so:
Ich habe eine Zahl n = 6146 und starte bei 2 und teste alle Primzahlen,
ob sie die Zahl teilen. Hier ist es schon der fall, denn 2 teilt 6146:

6146/2 = 3073

Ich merke mir also die 2 als ersten Primteiler.
Nun beginne ich von vorne und teste das gleiche mit der neuen Zahl.
Hier werde ich bei 7 fündig.

3073/7=439

und abermals teste ich. Diesmal stoppe ich erst bei 439 (oder, wenn ich es wieder effektiver machen will, teste ich nur bis zur Wurzel wieder, also bis 20). Also ist 439 eine Primzahl und somit unser letzter Primfaktor:

2 * 7 * 439 = 6146

Das scheint ja relativ einfach zu sein. Das Problem ist nun, dass diese RSA-Zahlen nur 2 Primfaktoren haben (einer ist größer als die Wurzel der Zahl, einer kleiner). Wenn ich da bei 2 anfange zu testen,
braucht es schon bei einer 128-Bit Zahl wenn ich Pech habe 1/3*2^64 (6'148'914'691'236'517'205) Versuche, um einen Primfaktor zu finden.
Je größer die Zahlen (und in der Praxis sind sie weit größer), desto länger dauert es. De facto dauert es auf diese Art und wiese wieder...ewig.

Doch gibt es auch hier viel schnellere Möglichkeiten.
Da so eine RSA-Zahl immer nur 4 Teiler hat (1, primzahl1, pz2 und die Zahl selbst), ist es clever bei der Wurzel der Zahl anzufangen und alle 6n +- 1 runtergehend zu testen, ob sie die Zahl teilen. Da der Primfaktor
der kleiner ist als die Wurzel eher näher an der Wurzel als an 0 liegt,
spart man so schon einiges. Schließlich wäre eine RSA-Zahl sehr unsicher,
wenn sie so gebildet würde: 7*2147483647=15032385529.
Etwas wie 121607*179923=21879896261 ist viel sicherer, da beide Faktoren "mitten drin" liegen, und man daher länger testen muss.

Dass sowas schon bei recht kleinen Zahlen trotzdem sehr sehr lange dauern kann, zeigte mir die Zahl

4617089864672320117 = 2147483647 * 2150000011

Mein erstes Programm testete von der Wurzel ausgehend, alle Zahlen mit den Endungen 9,7,3,1, ob sie die Zahl teilen. Bis der Faktor 2150000011
gefunden wurde, dauerte es so 27 min und 21 sek.

Mein zweites Programm testete nurnoch alle 6n +- 1, was also alle durch 3 teilbaren Zahlen auch noch ausschloss und brauchte 21 min und 18 sek.

Dann kam mir gewissermaßen ein Geistesblitz.
Mein drittes Programm schließlich brauchte nurnoch 14 Sekunden.
Mein aktuelles Programm schafft es in etwa 5 Sekunden.

Und andere, moderene Algorithmen brauchen etwa um 0,1 Sekunden.


Das klingt nach verdammt schnellen Programmen, doch bei größeren Zahlen mit 100, 200 oder mehr Stellen, versagen auch die (bzw. brauchen wieder sehr sehr lange )



Man sieht also, statt Rechenpower braucht man vorallem effiziente Algorithmen. Aber mit Programmiersprachen wie QB, FB oder BB ist es nicht einfach, da man dort auf Strings zurückgreifen muss, die sehr langsam sind (verglichen mit hochoptimierten professionellen Programmen).


Das nur dazu um mal einen kleinen Überblick über das Thema zu geben.
Wer glaubt, da ein paar Zeilen hinklarren zu können und dann den großen
Durchbruch zu schaffen, irrt jedenfalls
_________________
Coding: silizium-net.de | Portfolio: Triton.ch.vu

[psygate]

Öhm.....jo....

Woltle was ergänzen...

Alle Primzahlen haben die form 4*x+3 oder 4*x+1. das ist einfacher als 6*x+-1. Außerdem ist eine Zahl der Form 4*x+3 schnell auf ihre eigentschaften als primzahl zu testen. Denn jede nicht primzahl der form 4*x+3 hat mindestens einen Faktor der form 4*x+3.


Ach ja, ich würde gerne eine lib schreiben für große zahlen, hab aber bisher keine brauchbaren tutorials auf BigNum-Arithmetics gefunden. Kennst du da was?
_________________
Danke an Volta für seine großartige MMX_fade function. *verneig*
Personal-DNA:
<script src="http://personaldna.com/h/?k=qtrCFboSuCOpFrX-OI-AADBA-f78d&t=Free-Wheeling+Leader">
</script>

[Triton]

[psygate]

bei 6*n+-1 kommt aber keine drei als primzahl, und zwei auch nicht. Ich sehe das als großes manko. Außerdem kann cih bei 4*n+3 primzahlen sehr viel einfach feststellen ob sie wirklich prim sind!
_________________
Danke an Volta für seine großartige MMX_fade function. *verneig*
Personal-DNA:
<script src="http://personaldna.com/h/?k=qtrCFboSuCOpFrX-OI-AADBA-f78d&t=Free-Wheeling+Leader">
</script>

[Triton]