Kann mal wer...

[Haarmann]

ne grosse Zahl in 2 Teiler zerlegen?

[Matrix316]

Und was hat das mit TCPA zu tun? ;)

[Unregistered]

da will wohl jemand einen rsa-key knacken. ;)

[Haarmann]

Matrix316

Von Kryptologie keinen Schimmer... Wenn Du das könntest, dann gäbs kein TCPA mehr ;).

Unregged

Bleibt wohl wieder alle Arbeit bei mir hängen ;).

[Matrix316]

Von Kryptologie hab ich wirklich kaum eine Ahnung, aber eine große Zahl in 2 Teiler zu zerlegen...hm...einfach mal die Wurzel ziehen. Da gibts zwar Stellen hinter dem Komma, aber mit dem Ergebnis kann man vielleicht sogar was anfangen. ;D

[GloomY]

Originally posted by Matrix316
Von Kryptologie hab ich wirklich kaum eine Ahnung, aber eine große Zahl in 2 Teiler zu zerlegen...hm...einfach mal die Wurzel ziehen. Da gibts zwar Stellen hinter dem Komma, aber mit dem Ergebnis kann man vielleicht sogar was anfangen. ;D Es sind ganze Zahlen gemeint.

btw: Wer für Haarmanns Problem eine schnelle(!) Lösung findet, der hat wohl für den Rest seines Lebens ausgesorgt. Alle Geheimdienste dieser Erde würden das sofort mit Handkuss kaufen...

[Haarmann]

Gloomy

Nö, wozu kaufen, was man sich auch einfacher beschaffen kann? Ich meine so dumm kannst ned sein und das nem Geheimdienst verkaufen wollen, denn das würdest mit grosser Wahrscheindlichkeit nicht überleben ;). Aber die Zahl müsste Faktorisierbar sein, wenn man das Problem umschreibt.

[EcHo]

Kann mal einer das Problem genauer definieren? rein interesse halber :)

[Haarmann]

Sagen wir mal ne ca 2048 Bit grosse Zahl hat genau 2 Primfaktoren ;)...

Und alles was Du kennst ist leider die grosse Zahl. Hättest Du nun die 2 Faktoren, so wärste eben viel weiter ... Nur wie kommste von der grossen Zahl an die 2 kleinen?

[Matrix316]

Originally posted by Haarmann
Sagen wir mal ne ca 2048 Bit grosse Zahl hat genau 2 Primfaktoren ;)...


2^2048 ist ja auch nur 3.23170060714*10^616 ;)

Ok, man kann ja erstmal probieren ob die Zahl durch 2 Teilbar ist. Dann durch 3 oder 4...

Sagen wir Zahl X / 2 = Y

Mit 2*Y hätten wir schon eine kleine und eine etwas größere Zahl. Wenn die größere Zahl wieder durch 2 Teilbar ist, hätten wir 2*2*nächste Zahl. Dann vielleicht 2*2*3, wenn diese neue Zahl durch 3 Teilbar ist...und so weiter. Irgendwann kommt man vielleicht zu 2*2*3*2*2*3*2*2*2*3*3*...*z. Dann rechnet man die einzelnen 2*2.. Faktoren aus und kommt so auf zwei Teiler der großen Zahl.

Und mit der Modulo Arithmetik sollte man so relativ schnell auf die Lösung kommen. Nebenbei muss man eben noch Prüfen ob eine neue Zahl vielleicht eine Primzahl ist.

So sollte man relativ schnell zu einer Lösung kommen.

[GloomY]

Originally posted by Haarmann
Gloomy

Nö, wozu kaufen, was man sich auch einfacher beschaffen kann? Ich meine so dumm kannst ned sein und das nem Geheimdienst verkaufen wollen, denn das würdest mit grosser Wahrscheindlichkeit nicht überleben ;).Wieso? Ich mach das über die Öffentlichkeit.

Erstmal gross verkünden, dass ich es geschafft habe. Das gibt erstmal riesen Wirbel, weil an diesem Problem die Mathematiker schon seit Jahren (Jahrzehnten) sich die Zähne ausbeissen.

Und dann halt verhandeln, welcher Geheimdienst mehr zahlt. Gerade wenn man das erstmal publik gemacht hat, dann können die Geheimdienste einen nicht einfach so um die Ecke bringen. Das gibt zu viel öffentliches Aufsehen.
Originally posted by Matrix316
2^2048 ist ja auch nur 3.23170060714*10^616 ;)

Ok, man kann ja erstmal probieren ob die Zahl durch 2 Teilbar ist. Dann durch 3 oder 4...D.h. du hättest im schlimmsten Fall einen Aufwand von 1,7*10^308.

Das Universum ist gerade mal 5 Milliarden Jahre, d.h. 1,5768 * 10^17 Sekunden alt.
Um in die Größenordnung um 10^300 zu kommen, ist ein Rechner mit fast unendlicher Rechenleistung nötig...

-> Mit dem Ansatz ist es völlig unmöglich, das zu schaffen.

[x-dragon]

Originally posted by GloomY
...
Und dann halt verhandeln, welcher Geheimdienst mehr zahlt. Gerade wenn man das erstmal publik gemacht hat, dann können die Geheimdienste einen nicht einfach so um die Ecke bringen. Das gibt zu viel öffentliches Aufsehen.
... Du glaubst doch nicht das die anderen zuschauen werden, wenn du dich für jemanden entscheidest? :eyes:

Notfalls läßt sich bestimmt ein ganz unauffälliger Autounfall oder ähnliches arangieren ...

[Haarmann]

GloomY

Naja... wenns angeblich geknackt ist, kannst nix mehr verkaufen, weils wohl niemand mehr benutzen will ;).
Aber XBox und TCPA erleidern dann ziemlichen Schiffbruch...

[Exxtreme]

Ja, es müssen Primzahlen sein, damit die Chose funktioniert. Der Nachteil der Primzahlen ist, daß diese "relativ" selten vorkommen. Wenn man es schaffen könnte, diese Primzahlen schnell genug zu generieren, dann wäre diese Verschlüsselung weniger ein Problem.

[Matrix316]

Die Berechnung der Primzahlen ist kein Problem - dieses ist eher, dass die Zahlen zu groß sind, vielleicht, für ein C Programm...

Wir sollten mal in IV2 ein Programm schreiben, was die Primzahlen von x bis y ausrechnen und raussortieren kann und diese dann ausgibt. Und das ging auch relativ Flott, aber nur von 0 bis 10000 oder so.

Nur würde es gehen Alle Zahlen von 0 bis irgendwas mit 600 Stellen in einen Array zu schreiben?

Und wie lange würde es dauern das auszurechnen? Das müsste man mal probieren...
:D

[x-dragon]

Originally posted by Matrix316
...
Wir sollten mal in IV2 ein Programm schreiben, was die Primzahlen von x bis y ausrechnen und raussortieren kann und diese dann ausgibt. Und das ging auch relativ Flott, aber nur von 0 bis 10000 oder so.
... Also mein Delphi-Programm brauch 24 Sek. für die Primzahlen von 1 bis 100.000 inkl. Ausgabe in einer Listbox :).

Ok, Delphi ist vielleicht nicht ganz die passende Programmiersprache dafür, aber mehr als 10.000 ist definitiv drin(in relativ kurzer Zeit).

[Matrix316]

Originally posted by X-Dragon
Also mein Delphi-Programm brauch 24 Sek. für die Primzahlen von 1 bis 100.000 inkl. Ausgabe in einer Listbox :).

Ok, Delphi ist vielleicht nicht ganz die passende Programmiersprache dafür, aber mehr als 10.000 ist definitiv drin(in relativ kurzer Zeit).

Also mein C Programm (ich habs mal etwas erweitert, naja, man muss nur die größe des Arrays ändern ;)) braucht von 0 bis 100000 jetzt mit ausgabe auf Bildschirm so ca. 4 Sekunden. Und wenn das Programm richtig funktioniert sind es genau 9593 Primzahlen. ;)

[GloomY]

Ups, Doppelpost...

[GloomY]

Originally posted by Haarmann
GloomY

Naja... wenns angeblich geknackt ist, kannst nix mehr verkaufen, weils wohl niemand mehr benutzen will ;).
Naja, alle Welt verwendet momentan noch Verschlüsselungen, deren Sicherheit genau auf der Tatsache der "langsamen" Faktorisierung großer Zahlen beruhen. Wenn ich nun hingehe und denen erzähle, dass ich es geschafft habe, diese Problem zu lösen, denke ich schon, dass da einige Leute interessiert sein werden...
Originally posted by Haarmann
Aber XBox und TCPA erleidern dann ziemlichen Schiffbruch... Yep. Aber nur solange es keine wirklich sichere Verschlüsselung gibt.
Originally posted by X-Dragon
Du glaubst doch nicht das die anderen zuschauen werden, wenn du dich für jemanden entscheidest? :eyes:

Notfalls läßt sich bestimmt ein ganz unauffälliger Autounfall oder ähnliches arangieren ... Wenn's erstmal publik ist, dass es geht, dann werden andere Wissenschaftler sicher auch mit dem Thema beschäftigen und früher oder später eine Lösung dafür finden. Ein Mord (oder eben ein Unfall) kann an der Tatsache, dass es möglich ist (also mal angenommen, das sei so) nichts ändern.

Selbst wenn der "Erfinder" verstirbt, gibt es genügend Leute, die durch das Wissen, dass es eine Lösung gibt, genau dort weiterforschen.
Dann wird halt jemand anders irgendwann später die Lösung finden und vielleicht publik machen, bevor irgend ein Geheimdienst den umlegen kann...
Originally posted by X-Dragon
Also mein Delphi-Programm brauch 24 Sek. für die Primzahlen von 1 bis 100.000 inkl. Ausgabe in einer Listbox :).

Ok, Delphi ist vielleicht nicht ganz die passende Programmiersprache dafür, aber mehr als 10.000 ist definitiv drin(in relativ kurzer Zeit). Öhm, ich meine mich daran zu erinnern, dass ich mit meinem 8086 die Primzahlen von 2 bis 50000 in etwa 30 Sekunden ausrechnen konnte. (edit: reine Rechenzeit; ohne Ausgabe gemessen)
Imho scheint dein Delphi Progrämmle nicht sehr effizient zu sein...

Die Programmiersprache war übrigends Turbo Pascal 5.0. In Assembler geht das sicher noch um den Faktor 5 schneller...

[Haarmann]

GloomY

Mit der Sieb Variante kann das sogar Excel sehr schnell ;) - nur die geht nimmer bei grossen Zahlen.

Weisste - wenn der Erfinder tot ist und Du dieser Erfinder bist, kratzt Dich das Danach nicht mehr wirklich ;).

[x-dragon]

Originally posted by GloomY
...
Öhm, ich meine mich daran zu erinnern, dass ich mit meinem 8086 die Primzahlen von 2 bis 50000 in etwa 30 Sekunden ausrechnen konnte. (edit: reine Rechenzeit; ohne Ausgabe gemessen)
Imho scheint dein Delphi Progrämmle nicht sehr effizient zu sein...

Die Programmiersprache war übrigends Turbo Pascal 5.0. In Assembler geht das sicher noch um den Faktor 5 schneller... Das Delphi nicht für sowas nicht geeignet stimmt auf jeden Fall :). Und da Pascal ja der Vorgänger ist und ohne den ganzen Windows-Balast auskommt, muss es auch einiges schneller sein. Assembler sowieso, könnte aber auch etwas mehr Arbeit sein ...

Hab mal mein Programm korrigiert und optimiert und komme jetzt auf 27 sek.(Pentium 633MHz/256 MB/WinXP mit Anzeige eines kleinen Fensters mit Start-Button) und auch auf 9593 Primzahlen :).

[Matrix316]

Originally posted by X-Dragon
Das Delphi nicht für sowas nicht geeignet stimmt auf jeden Fall :). Und da Pascal ja der Vorgänger ist und ohne den ganzen Windows-Balast auskommt, muss es auch einiges schneller sein. Assembler sowieso, könnte aber auch etwas mehr Arbeit sein ...

Hab mal mein Programm korrigiert und optimiert und komme jetzt auf 27 sek.(Pentium 633MHz/256 MB/WinXP mit Anzeige eines kleinen Fensters mit Start-Button) und auch auf 9593 Primzahlen :).

Juhu, meins stimmt. ;) Von 0 bis 200000 braucht es so ca. 14 Sekunden. Na gut, mein Prozzie ist auch etwas schneller. ;)

Das Problem ist IMO nur der Datentyp...(mod bzw % macht bei mir Probleme mit nicht int Werten)

[GloomY]

Originally posted by Haarmann
GloomY

Mit der Sieb Variante kann das sogar Excel sehr schnell ;) - nur die geht nimmer bei grossen Zahlen.Wegen des hohen Speicherplatzbedarfes? btw: Ich hab' mal ein Programm geschrieben, das auch ähnlich schnell war, aber nur jede Primzahl gespeichert hat (und nicht für jede Zahl ob sie ist oder nicht).

Was gibt's für grosse Zahlen sonst noch für Algorithmen?
Originally posted by Haarmann
Weisste - wenn der Erfinder tot ist und Du dieser Erfinder bist, kratzt Dich das Danach nicht mehr wirklich ;). Hmm, ja ok. :| Überzeugt ;D

Trotzdem würd' ich's versuchen, daraus Geld zu machen.

[Matrix316]

Originally posted by GloomY
Wegen des hohen Speicherplatzbedarfes? btw: Ich hab' mal ein Programm geschrieben, das auch ähnlich schnell war, aber nur jede Primzahl gespeichert hat (und nicht für jede Zahl ob sie ist oder nicht).

Was gibt's für grosse Zahlen sonst noch für Algorithmen?



Hier mal mein Programm:


/* Programm: ueb_80a.CPP========== (C) Kehm, Michael */
/* */
/* Erstellt: 19.10.01 */
/* Letzte Aenderung: 27.10.01 MK */
/* */
/* */
/* Primzahlenausgabe */
/* */
/* Beginn des Hauptprogramms ================================ */

#include <stdio.h>
#include <math.h>
#include <time.h>

main (void)

{
unsigned int a,b,d,g=0,feld[256001];
unsigned int i,f,e,c;
printf("\nGeben sie die Anfangszahl ein:\n");
scanf("%d",&a);

printf("Geben sie die hoechste Zahl ein:\n");
scanf("%d",&b);

// printf("\nWeiter mit Taste, abbruch mit a\n"); - nicht notwendig, da schnell genug

for (e=a; e<b; e=e+1)
{
feld[e]=e;
}

//Berechnung der Primzahlen

d=1;

for (f=1; f<b+1; f=f+1)
{
while (d<sqrt(b))
{
for (c=0; c<b+1; c=c+1)
{

if (feld[c]%(2*f)==0 && feld[c]/(2*f)!=1)
{
feld[c]=0;
}

if (feld[c]%((2*f)+d)==0 && feld[c]/((2*f)+d)!=1)
{
feld[c]=0;
}
}
d=d+1;

}
}

//Ausgabe der Primzahlen

printf("\nAlle Primzahlen von %d bis %d\n\n",a,b);

for (i=a; i<b; i=i+1)
{
if (feld[i]>0)
{
printf("%d\t",feld[i]);
g=g+1;
}
}

printf("\n\nEs wurden %d Zahlen gefunden!\n\n",g);

return 0;

}


Das Problem ist (bei meinem Prog) nicht der Algorithmus, sondern, dass die Zahlen, ganz einfach zu groß werden für den Datentyp (und den array ;))...

[GloomY]

Originally posted by Matrix316
Hier mal mein Programm:

[...]
while (d<sqrt(b))
[...]Wooaah. Allein aus Performancegründen schreibt man da:


while (d*d<b)
Quadrieren oder Multiplizieren geht viel schneller als Wurzel ziehen.
Originally posted by Matrix316
Das Problem ist (bei meinem Prog) nicht der Algorithmus, sondern, dass die Zahlen, ganz einfach zu groß werden für den Datentyp (und den array ;))... Hmm, es gibt Pakete (FLINT/C für C/C++), mit denen kann man Zahlen mit einige hundert Stellen verarbeiten.

[Haarmann]

Kein Wunder seit ihr arschlahm mit dem Algo :rofl:

Versuchs mal mit 2 und 3 und der Rest liegt neben 6n ;)

Mit dem Sieb bin ich fertig, bevor ihr angefangen habt ;) - bis 100k dürfte das nedmals ne Sekunde gehen. Bitmap und dann schnell durchgehen... ist ziemlich einfach.

[86318]

Originally posted by Matrix316


Juhu, meins stimmt. ;) Von 0 bis 200000 braucht es so ca. 14 Sekunden. Na gut, mein Prozzie ist auch etwas schneller. ;)



wird das hier ein wettbewerb? ;)
wenn ja dann schlagt mal das:
1 bis 100000 in 1 Sekunde, 9593 Primzahlen gefunden
1 bis 2^20 (=1048576) in 103 Sekunden :(, 82026 Primzahlen gefunden (stimmt das eigentlich?)

das ganze läuft auf einem athlon xp 1666mhz.

[Matrix316]

Originally posted by GloomY
Wooaah. Allein aus Performancegründen schreibt man da:


while (d*d<b)
Quadrieren oder Multiplizieren geht viel schneller als Wurzel ziehen.


Klugscheißer...:P

Ich habs mal probiert und es ist NICHT schneller...

Ganz einfach weil die For schleifen immer noch durchlaufen müssen...

Außerdem war das eines meiner ersten C Programme überhaupt...:P

[Matrix316]

Originally posted by 86318


wird das hier ein wettbewerb? ;)
wenn ja dann schlagt mal das:
1 bis 100000 in 1 Sekunde, 9593 Primzahlen gefunden
1 bis 2^20 (=1048576) in 103 Sekunden :(, 82026 Primzahlen gefunden (stimmt das eigentlich?)

das ganze läuft auf einem athlon xp 1666mhz.

WAS läuft auf einem XP1666...??

[x-dragon]

Originally posted by 86318
...
das ganze läuft auf einem athlon xp 1666mhz. Wow, nicht schlecht, womit hast du das denn geschrieben?

Mein Delphi-Programm kann ich auch noch einiges optimieren, von wegen vorher Zahlen aussieben und so, allerdings erst wieder Montag wenn ich wieder in der Firma bin :).

[86318]

habs noch einmal überarbeitet, braucht jetzt von 1 bis 2^20 nur mehr 12 Sekunden =)

geschrieben hab ichs in C, unter linux.

vorher aussortieren von unnötigen zahlen bringt sehr sehr viel.
so sieht das programm aus:


#include <stdio.h>
#include <sys/time.h>

#define PCRUNCHER_LIMIT 1048576
#define PCRUNCHER_CALCB 150

#define PCRUNCHER_CALCB_NULL PCRUNCHER_CALCB+1

int main() {
int i;
int primcounter=0;
time_t zeit;
int startzeit=time(zeit), endzeit;

printf("\nsuche primzahlen zwischen 1 und %d...\n", PCRUNCHER_LIMIT);

for (i=1;i<=PCRUNCHER_LIMIT;i++) {
int zahl;
int notprime=0;
int l;

zahl=i/PCRUNCHER_CALCB_NULL;
for (l=2;l<zahl;l++)
if (i%l==0) {
notprime=1;
break;
}
if (!notprime)
for (l=0;l<PCRUNCHER_CALCB;l++) {
zahl=i/(l+2);
if (zahl>1)
if (i%zahl==0) {
notprime=1;
break;
}
}
if (!notprime)
primcounter++;
}

endzeit=time(zeit);
printf("\nanzahl: %d\n", primcounter);
printf("rechenzeit: %d sekunden\n\n", endzeit-startzeit);
}


ziemlich konfus, ich weiß ;).
aber es funktioniert, und ich hab nicht lange gebraucht um es zu schreiben.

EDIT: code editiert. jetzt noch besser ;) 2^20 in 8 sekunden. (das macht süchtig :D )

[Dunkeltier]

Man könnte ja einen Client schreiben und so zig Rechner gegen die TCPA Verschlüsselung rechnen lassen. Da gibt es bestimmt einige, die mitmachen würden.

[Haarmann]

Wenn man das zerschlagen will, brauchts Brainpower und nicht Rechenpower. Ein optimierter Ansatz hilft da weit.

So zum Vergleich - unter ner Sekunde schaffte es auch ein 386er bis 100'000 per Sieb ;). Allerdings war da reiner Assembler im Spiel - daher war unser Info Lehrer ziemlich frustriert, weil sein Proggi in Comal konnt irgendwie ned ganz mithalten...

Wenn Du die grosse Zahl im Hex System siehst, kannst übrigens sagen, welche Art von Primzahlen es ist. Eins über oder unter 6n. Bei Ende 1 isses gleich und bei 5 isses verschieden. Das hilft einem auch nicht viel weiter. Solange man jedenfalls im Hex oder Dec System bleibt.

[Matrix316]

Und es gibt ja noch die Regeln:

Wenn die letzte Ziffer durch 2 Teilbar ist, ist die Zahl Teilbar durch 2.

Wenn die Quersumme durch 3 Teilbar ist, ist die Zahl durch 3 Teilbar.

Wenn die aus den beiden letzten Ziffern gebildete Zahl durch 4 Teilbar ist, ist die Zahl durch 4 Teilbar.

Wenn die letzte Ziffer eine 5 oder eine 0 ist, ist die Zahl durch 5 Teilbar.

So kann man sehr große Zahlen erstmal effektiv verkleinern und dann mit den Kleineren Zahlen arbeiten oder so. ;)

[Haarmann]

Matrix316

Die grossen Zahlen haben ja nur 2 Primfaktoren und da ist sicher keine 3 oder 2 dabei ;).

[Matrix316]

Originally posted by Haarmann
Matrix316

Die grossen Zahlen haben ja nur 2 Primfaktoren und da ist sicher keine 3 oder 2 dabei ;).

Aso...muss man ja auch wissen. ;)

[Unregistered]

Originally posted by Exxtreme
Ja, es müssen Primzahlen sein, damit die Chose funktioniert. Der Nachteil der Primzahlen ist, daß diese "relativ" selten vorkommen. Wenn man es schaffen könnte, diese Primzahlen schnell genug zu generieren, dann wäre diese Verschlüsselung weniger ein Problem. So selten sind die gar nicht. Die Dichte nimmt zwar ab, aber recht gemächlich.

[Frank]

Ich merk schon - ihr habt alle keine Ahnung :D


Wenn man große Primzahlen zb für RSA oder Elgamal sucht, nimmt man bestimmt nicht eine Methode die von 1 anfängt zu suchen. Ich suche ja nicht alle von - bis, sondern nur 2 Stück (zb). Und da brauch man sich über das Durchsuchen an sich keine Gedanken machen. Da reicht für die Praxis kurz Bruteforce aus, wo man einfach in einem Intervall auf alle ungeraden Zahlen nacheinander ein Primzahltest ausführt. Wichtig ist neben den Primzahltest selbst da evtl noch eine Abschätzung der Anzahl der in einem Intervall vorkommendne Primzahlen:
http://rcswww.urz.tu-dresden.de/~fh468638/temp/pz1.gif
Für den Primzahltest nimmt man dann auch stochastische Algorithmen. In der Praxis: Fermat-Test und Rabin-Miller-Test. Die sind zumindest hinreichend gut. Wer es ganz genau wissen will: Anfrage und ich schreib was dazu. So was wie Satz von Wilson kann man in der Praxis gleich wegwerfen. (der dürfte glaub ich auch in Schule rankommen). Das ganz neue Highlight bei der Primzahlerkennung ist ein halbes Jahr alt: @Haarmann: falls dich das interessiert empfehle ich dir http://www.cse.iitk.ac.in/news/primality.html diese Arbeit runter zuladen und durchzuarbeiten. Der Aufwand des Algos dort von O((log2 n)^12) ist recht gut.

Zu der eigentlich Frage:
Haarmann - dafür brauchst du höhere Zahlentheorie. Also nix mehr mit Spasszahlenalgorithmen. Einfach Sachen sind evtl die FermatFaktorisierung und die (p-1)Methode. Die eignen sich aber auch eher weniger für die Praxis. Möglichkeiten sind:
1. Das Quadratische Sieb (QS)
2. Faktorisierung auf elliptischen Kurven (ECM)
3. Algemeines ZahlkörperSieb (GNFS)

Die Aufwände sind:
http://rcswww.urz.tu-dresden.de/~fh468638/temp/pz2.gif
(n=p*q mit p,q prim)

Sind alle für leichte Unterschiedliche Zahlengrößen - aber performen letztendlich auf ähnlichen Level.
Aber: ein Bsp: mit GNFS wurde 1999 eine 512bit Zahl faktorisiert. Waren allerdings mehrere Rechner (300 glaub ich) und auch etwas länger gedauert. 2010 vermutet man damit eine 768bit Zahl zerlegen zu können und 2018 eine 1024bit Zahl (bei aktueller Rechnerentwicklung)

[barracuda]

Originally posted by Frank

Ich merk schon - ihr habt alle keine Ahnung :D

Ups, erwischt....
Originally posted by Frank
Das Quadratische Sieb wäre ich bereit zu erklären hier - aber auch erst wenn's jemand wirklich wissen will.

Oooooooooch nööööööööö, lass mal gut sein :D

[Frank]

Originally posted by barracuda
Oooooooooch nööööööööö, lass mal gut sein :D nö :)


Also kommen wir zum Quadratischen Sieb:

Die Grundidee ist eigentlich relativ simpel:
Man suche zwei ganze Zahlen x und y mit der Eigenschaft, dass
http://rcswww.urz.tu-dresden.de/~fh468638/temp/pzf5.gif
Ergo: wenn man diese beiden Zahlen x und y hat, ist die Zahl in ihre (großen) Primfaktoren zerlegt. Da mit es später nicht zu unverständlich wird, am besten ein Beispiel:
http://rcswww.urz.tu-dresden.de/~fh468638/temp/pzf6.gif
Aber wie kommt man nun zu den x und y? Am besten man rollt die Sache komplett von hinten auf:
http://rcswww.urz.tu-dresden.de/~fh468638/temp/pzf7.gif

Klar das Beispiel eignet sich net richtig - da ist man durchaus mit Bruteforce besser. Aber wenn die Zahlen dann so langsam 100stellig werden... naja. Evtl mach ich auch ein anderes Bsp mal falls gewünscht. Kann ja mal jemand coden den Algo.

[Frank]

Und damit auch hier niemand unwissend bleibt:

Zu den Primzahltests:

1. Fermat-Test

Dazu benötigt man (wer hätte das gedacht) den Satz von Fermat:
http://rcswww.urz.tu-dresden.de/~fh468638/temp/pzf1.gif
... und zusätzlich eine Definition:
Ist n eine Ungerade und a eine ganze Zahl mithttp://rcswww.urz.tu-dresden.de/~fh468638/temp/pzf2.gifdann nennt man n eine Pseudoprimzahl zur Basis a.
Der Fermat-Test ist nur noch ein Test auf Pseudoprimzahl. Man dürfte leicht sehen, dass dieser Algorithmus ein stochastischer ist (genauer: Monte Carlo Typ). Wenn er eine Zahl als nicht-pseudo Zufallszahl erkennt, ist es auch keine Primzahl. Andersrum benötigt man hinreichend viele Schritte um ausreichend sicher zu sein, dass die Zahl wirklich eine Primzahl ist. Die Wahrscheinlichkeit für k bestandene Tests ist kleiner als 1/(2^k). Dieser Test wird in der Praxis relativ häufig verwendet.

2. Miller-Rabin-Test

Dazu wird es schon etwas komplizierter. Aber da so halbwegs jeden Studenten der Naturwissenschaften prime Restklassengruppen was sagen müssten ...
Also fangen wir an mit einer Aussage (o.B.):
http://rcswww.urz.tu-dresden.de/~fh468638/temp/pzf3.gif
Analog zu der Pseudoprimzahl vom Fermat-Test definiert man sich jetzt eine starke Pseudoprimzahl:
http://rcswww.urz.tu-dresden.de/~fh468638/temp/pzf4.gif
Der M-R-Test testet quasi wie beim Fermat Test zuerst auf den ggT(a,n)=1 und dann auf starke Pseudoprimzahl. Wenn eine Zahl keine starke PseudoPZ ist, dann auch keine Primzahl. Die Wahrscheinlichkeit das eine PseudpPZ bei k verschiedenen a’s auch wirklich eine Primzahl ist, liegt bei 1-1/(4^k). Evtl. ein kleiner Anhaltspunkt wie gut der Test ist: für n bis 10^7 gibt es nur 7 starke Pseudoprimzahlen für a=2und3, die keine Primzahlen sind.



hoffe das kein Schreibfehler drin ist.

[zeckensack]

Das Sieb des Erastothenes (oder so) suckt.
Nehmt lieber das:
#include <vector>
#include <time.h>

typedef unsigned int uint;

int
main()
{
clock_t start_time=clock();
std::vector <uint> primes;

primes.push_back(2);

for (uint n=3;n<10000000;n+=2)
{
uint old_primes=primes.size();
bool is_prime=true;
for (uint i=0;i<old_primes;++i)
{
uint old_prime=primes[i];
if ((old_prime*old_prime)>n) break;
if ((n%old_prime)==0)
{
is_prime=false;
break;
}
}
if (is_prime) primes.push_back(n);
}

clock_t end_time=clock();
double elapsed=(end_time-start_time)/CLOCKS_PER_SEC;

printf("found %u primes in %f seconds\n",primes.size(),elapsed);

return(0);
}
Zahlenraum bis 10 Millionen in 9 Sekunden, bis 100 Millionen in 208 Sekunden. (XP1800+)

[Haarmann]

Frank

Deine Abneigung zu meiner, nennen wirs Hokus Pokus Mathe, ist verständlich. Jedoch sage ich dazu immer eines, wenn ich die Varianten dieser Mathe Hoschis einsetzte, käme ich auch nicht weiter als diese und diese sind ja an dem Problem gescheitert. Mein Ziel ist aber nicht das Scheitern.
Daher sagte mir meine bescheidene Logik, dass man wohl anders ansetzen muss. Eine Variante war das klassische (a-b)(a+b)=N, wobei N die grosse Primzahl ist. Aber egal wie ich es auslegte, ich kam ned wirklich auf nen grünen Zweig, daher versuchte ichs erstmals mit inneren Strukturen von Primzahlen, welche ich dann leider auch nicht fand -> Recycle Bin. Auch die netten geometrischen Ansätze blieben so ca ungefähr erfolglos. Alles was ich bis dahin gefunden hab war ne Alternative zum Beweis der fermatschen Vermutung, allerdings war ich zu faul um dem nachzugehen auch wenns sicherlich interessant is (und vor allem er passt auch auf ne Buchseite).

Irgendwann kam ich dann auf die Idee, dass man ev das Problem umformulieren muss... und siehe da, man kommt eben viel weiter mit dieser unmathematischen Alternative. Mein Einziges Problem sind eigentlich noch die einzelnen Gleichungen, die ich noch genauer hinkriegen sollte.
Ansonsten bleibt mir noch immer der Ansatz des direkten Splittens der Zahl, resp der Versuch dessen mit allen möglichen Längen. Sind gar nicht soviele Varianten, daher könnte das noch reichen.

Auf gut Deutsch ich halte vom durchschnittlichen Mathe Typen von ner Uni genau gar nix... Diese Leute sind mir zu Dogmenbehaftet.

P.S. Bei meinem Ansatz wird einem auch klar, weswegen man nie 2 Primzahlen der Art (2^n)-1 verwenden darf. Solch eine Zahl könnte ich nämlich gar von Hand innert Sekunden mit etwas Abzählen "knacken".

[Frank]

Dann erzähl doch mal etwas mehr über deinen Ansatz Haarmann. Ich bin ja gegenüber neuen nicht abgeneigt. Das man RSA innerhalb von Bruchteilen knacken kann unter gewissen Vorraussetzungen ist ja auch klar. Vorraussetzung bei der Wahl von gewissen Parametern ist immer dieses kleines Wörtchen "geeignet".
Aber worauf zielt jetzt deine eigentliche Frage am Threadstartdenn nun hinaus? Willst du ein komplett neuen Algorithmus suchen für die Primfaktorzerlegung oder einfach nur einen geeigneten genannt/erklärt/programmiert haben? (im ersten Fall würd ich evtl das http://www.cse.iitk.ac.in/news/primality.pdf mal als Anregung durchabreiten und rumprobieren - im zweiten Fall ECM in Google eingeben und versuchen zu verstehn)

ps.
"(a-b)(a+b)=N wobei N die grosse Primzahl ist"
damit meintest du wohl eher N als = p*q (mit p,q prim) , oder?

[Haarmann]

Frank

Binär mit ner simulierten Multiplikation statt ner "echten" Multiplikation. Gibt erstaunlicherweise auf recht einfache Art ne genügende Anzahl von Gleichungen, damit mans sicher lösen kann. Es müsste also 4 Lösungen geben und 2 davon sind 1 und N selber... Eigentlich recht einfach also.
zZ bastle ich allerdings an ner Vereinfachung der ganzen Sache rum. Ich bin zu faul mit sovielen Unbekannten mich zu ärgern. Nen paar kannst ja sehr einfach eliminieren.

Wenn Du es übrigens so machst, dann weisst auch wieso (2^n)-1 ned ideal ist, denn die Zahl sind dann nur 1er. Nimmst die hinterste 1 und zählst dann die Nullen davor dazu, bis wieder ne 1 kommt... das ist dann die Anzahl der 1er beim kleineren Faktor...

Ich werds also mal lesen... Ich denke der Grundsatz oben ist klar.

[Frank]

ja - vollkommen klar.

Aber die Quadratischen Reste lassen sich auch nicht trivial ausrechnen. Weiss jetzt nicht wie das über die Legendre Symbole performt. Muss'sch ma nachguggen.

[Haarmann]

Frank

Drum rechne ich vorerst weniger und verlagere mich aufs Erkennen von Mustern ...
Wenn z.B. die Länge der 2 Faktoren in Bit kennst, ist die Sache plötzlich nur noch halb so schwer.
Eine Idee, wie ich an die Länge des längeren kommen kann hab ich jedenfalls.

[Frank]

Wie willst du denn auf die Länge eines Primteilers kommen?

[Haarmann]

Frank

Kompliziert zum erklären... obs wirklich funktioniert ist noch nicht sicher ;). Ich hab lange diese Zahlen beobachtet und es ist mir halt ab und an was aufgefallen. Bei kleineren Zahlen gings - nun muss ichs nur mal auch auf grosse Zahlen loslassen. Je mehr Zeit ich hab, desto weiter komme ich wohl damit... es stehen ja mal 6 wochen Ferien von der Uni vor mir ;).

[Frank]

Originally posted by Haarmann
Frank

Kompliziert zum erklären... obs wirklich funktioniert ist noch nicht sicher ;). Ich hab lange diese Zahlen beobachtet und es ist mir halt ab und an was aufgefallen. Bei kleineren Zahlen gings - nun muss ichs nur mal auch auf grosse Zahlen loslassen. Je mehr Zeit ich hab, desto weiter komme ich wohl damit... es stehen ja mal 6 wochen Ferien von der Uni vor mir ;).
Wenn du von einer großen Zahl n eine Aussage über die Länge eines großen Primteilers machen könntest, hättest du ausgesorgt. :)

Naja - ab 12.3. (bis dahin 2 Diplprfs) hab ich auch mal "semesterferien" wo ich allerdings schon jetz ein Projekt aufgedrückt bekommen hab: RT/N Patches. Sieht nich gut aus mit Zeit :(

[Haarmann]

Frank

Mein Beileid... mich wirds sicher auch noch mit was eindecken...

Aber ich werds mal genauer ansehen müssen

[ollix]

Originally posted by Matrix316
Die Berechnung der Primzahlen ist kein Problem - dieses ist eher, dass die Zahlen zu groß sind, vielleicht, für ein C Programm...

Wir sollten mal in IV2 ein Programm schreiben, was die Primzahlen von x bis y ausrechnen und raussortieren kann und diese dann ausgibt. Und das ging auch relativ Flott, aber nur von 0 bis 10000 oder so.Moin, ich habe mal vor einiger Zeit im Studium genau so ein Programm mit Haskell geschrieben. Dies ist eine funktionale Programmiersprache und aufgrund für einige dieser Probleme recht gut geeignet. Das ganze Programm waren 3 oder 4 Zeilen und verdammt flott. Muß mal schauen, ob ich dies noch irgendwo wiederfinde und mal wieder einen Haskell Kompiler installieren.

Haskell ist in dieser Hinsicht sowieso witzig, weil man damit Sachen einfach machen kann, die einfach krank sind.

Zum Beispiel kann man in einer kurzen Zeile eine unendlich lange Liste an Zufallszahlen erzeugen und aus dieser unendlich langen Liste alle doppelten Einträge rausstreichen...
:D

Das hat mit der verzögerten Auswertung von Haskell zu tun - man hat erst ein Problem wenn man auf das letzte Element dieser Liste zugreifen will. :)

Auch ist das mit dem Typüberlauf nicht das Problem, da Haskell auf beliebig großen Zahlen rechnen kann - es muß nur genug Platz im Speicher sein....

[Frank]

hmmm

Haskell schnell ? :| :D

[Haarmann]

Kann diese Sprache grosse Zahlen ins Hex oder Bin System konvertieren?
Dann könnte ich mir diese Arbeit nämlich sparen ;).

[zeckensack]

Originally posted by Haarmann
Kann diese Sprache grosse Zahlen ins Hex oder Bin System konvertieren?
Dann könnte ich mir diese Arbeit nämlich sparen ;). Falls Bedarf besteht, in C/C++ macht man einfach
//really large integer to hex

char buffer[128];
unsigned int in[5]; //32 bit parts, in[0] is least significant

sprintf(buffer,"%08X%08X%08X%08X%08X",in[4],in[3],in[2],in[1],in[0]);
//really large integer to binary

unsinged int in[5]
char buffer[32*5+1];

char* position=buffer;
for (int part=4;part>=0;--part)
{
for (int bit=31;bit>=0;--bit)
{
if (0==(in[part]&(1<<bit)) *position++='0';
else *position++='1';
}
}
*position=0; //terminate string