www.LaserFreak.net

Hallo zusammen,

ne kleine challenge...
Habe ein kleines Programm geschrieben das
aus einem einzugebendem Zahlenbereich von 0-35000000
nach Primzahlen sucht. Das ganze geschiet nach der Methode
des Eratosthenes.

-Getestet unter Windows XP.
-Belegt 138Mb RAM
-Verschlingt bei der Suche zwischen 34999000-35000000
satte 15Min. CPU Zeit (System 1,4Ghz P4 ohne Hyp. mit genügend RAM )

Wer meinem Programm nicht glaubt der prüfe hier:
http://www.primzahlen.de/

Quellcode & fertige ausfürbare Datei im Anhang.

Bug's an -> richard@web-world.ch

viel Spass damit RichardK

Hi,

nettes proggie!

Wie war das noch ... man nehme eine Reihe von Zahlen, streiche alle geraden raus, und alle weiteren, die durch die verbleibenen von unten angefangen teilbar sind ... (Sieb des Eratosthenes).
Hatten wir kurz in Verschlüsselungsalgorithmen.

Wenn ich hier ausgezogen bin (Ende des Monats) werde ich mich mal mit dem proggie beschäftigen.
Im Moment halten mich Klausuren, Erkältung mit Fieber, Zahnarzttermine und der Auszug ganz schön auf Trab

Hallo medra,

Ja so ungefähr. Auf der Webseite die ich verlinkt habe ist das alles
wunderbar nachzulesen. Da hat sich jemand die Mühe gemacht dies
korrekt Deutsch & Mathematisch in Worte zu fassen.

Na ja, C++ ist's ja eher nicht.. habe es als procedural geschrieben.
Aber da wir eigentlich C++ lernen an der HF... na ja,
laäuft auf jedenfall im Compiler

Dir wünsche ich gute Besserung und viel spass beim Umzug.
Da kommen immer wieder Sachen hervor, die man geglaubt hat
schon längst entsorgt zu haben *gg*

RSA Key selber basteln wär ja mal was...

Gruss Richard

RichardK wrote:RSA Key selber basteln wär ja mal was...

Oh, weh ... RSA ist schon etwas schwiriger ...
RSA ist zunächst einmal asymmetrisch, d.h. ein Schlüssel zum Ver-, einer zum Entschlüsseln der Nachricht. Man erzeugt (oder nutzt) die allgemeinen Parameter p, q; erzeugt den öffentlichen Schlüssel d und den geheimen Schlüssel e.
Mit dem allgemeinen Parameter und dem öffentlichen Schlüssel lässt sich nun eine Nachricht verschlüsseln, die dann mittels e vom Empfänger wieder entschlüsselt werden kann.

Das ganze basiert darauf, dass man eine hohe Zahl aus zwei Priemfaktoren p und q errechnet:
n = p * q
phi(n) = (p-1)(q-1)
p, q brauchste dann nicht mehr.

Danach denkt man sich zwei weitere Zahlen aus:
d, e | ggt(d, phi(n)) = ggt(e, phi(n)) = 1 (d.h. es gibt nur den gemeinsamen Teiler 1, d und e sind teilerfremd zu phi(n)

weiter d * e kongruent 1 mod phi(n)


Jetzt erzeugt man die verschlüsselte Nachricht (N = originalnachricht)

X = N^d mod n, und veröffentlicht X und N (bzw. verschickt dies)

per X^e kongruent N^(d*e) kongruent N^1 mod n (e ist der geheime schlüssel) kann der empfänger (=besitzer des geheimen schlüssel) die Nachricht wieder entschlüsseln.


Ähnlich lässt sich hiermit eine Signatur erzeugen:
X = N^e mod n
N = X^d mod n (jeder, der den öffentlichen Schlüssel d kennt, kann die Signatur prüfen.


Die Priemzahlen sind hier so interessant, da sich teilerfremde Zahlen erzeugen lassen. D.h. mit mathematischen Verfahren (z.B. Potenzieren) erzeugte verschlüsselte nachrichten lassen sich eindeutig zurückrechnen, und die chance, Angriffspunkte im Verfahren zu finden, sinkt.

---
keine Garantie auf Richtigkeit, das war ein grober Abriss