Suche Beweis...

12.11.2004, 13:53	Bebbo Erbse	Auf diesen Beitrag antworten »
Suche Beweis... Hallo! Auf einer Internetseite über Kryptologie hab ich gesehen, wie man eine zahl prüfen kann, ob sie prim sei: p = zu überprüfende Primzahl a = irgendeine Zahl = 2 a^(p-1) mod p = 1 Das muss nicht immer zutreffen, es gibt auch Nicht-Primzahlen, die die Gleichung in diesem Falle erfüllen, doch man kann diese zahl erneut prüfen, indem man eine andere zahl für a einsetzt. Jetzt interessiert mich der Beweis für diese Aussage, ich komme einfach nicht dahinter!
12.11.2004, 16:10	eule	Auf diesen Beitrag antworten »
Es gibt auch Nicht-Primzahlen welche diese Gleichung für alle a erfüllen. Die Aussage stimmt zwar ist aber als Primzahltest nicht geeignet.
12.11.2004, 16:59	Tobias	Auf diesen Beitrag antworten »
Das ist der kleine Satz von Fermat. Dieser sagt: $\begin{eqnarray} p \text{ Primzahl} \quad \iff \quad a^{p-1} \equiv 1 \; (\text{mod } p) \text{ fuer alle } a \in \mathbb{Z}_p \backslash \{0\}\;. \end{eqnarray}$ Es ist aber als Primzahlentest unbrauchbar, alle a's durchzuprobieren. Deshalb dient der von dir beschriebene Primzahlentest sozusagen als Möglichkeitstest. Findet man ein a, für das der Satz nicht gilt, so ist p sicher keine Primzahl. Findet man allerdings (nach ein paar Iterationen)kein a, für das der Satz widerlegt ist, so heißt dies nicht, dass p tatsächlich prim ist sondern nur die Wahrscheinlichkeit ist gegeben. In Primzahlentests wird deshalb eine etwas erweiterte Prüfung vorgenommen, in der auch der euklidische Algorithmus eine Rolle spielt. 100% Sicherheit bieten aber auch diese Tests nicht.
12.11.2004, 17:22	eule	Auf diesen Beitrag antworten »
Eben nicht. Es gilt $\begin{eqnarray} p \text{ Primzahl} \quad \Rightarrow \quad a^{p-1} \equiv 1 \; (\text{mod } p) \text{ fuer alle } a \in \mathbb{Z}_p \backslash \{0\}\;. \end{eqnarray}$ Die Gegenrichtung gilt nicht ( Carmichael-Zahlen).
12.11.2004, 17:53	Bebbo Erbse	Auf diesen Beitrag antworten »
ich weiß, dass es auch für andere zahlen geht, die nicht prim sind. Hab ich auch oben hin geschrieben. Außerdem ist die Wahrscheinlichkeit im Bereich der 10bit Zahlen sehr gering, dass p nicht prim ist. Das alles ist mir aber egal, ich brauche den Beweis um zu verstehen, wie man überhaupt auf diese Gleichung kommt.
12.11.2004, 18:02	Tobias	Auf diesen Beitrag antworten »
Dann lügt mein Buch. Aber du hast jetzt auf alle Fälle das Stichwort "Kleiner fermatscher Satz" und kannst das in einer Suchmaschine deiner Wahl eingeben.
Anzeige

12.11.2004, 18:50	eule	Auf diesen Beitrag antworten »
@Bebbo Erbse: Welche mathematische Vorwissen hast du denn? Hast du schon mit endlichen Körpern zu tun gehabt?
12.11.2004, 19:00	Bebbo Erbse	Auf diesen Beitrag antworten »
ja, genau das wollte ich euch grad fragen: Was sind mathematische Körper? Ich habe das mathematische Vorwissen eines Gymnasiasten der 9. Klasse, also nicht besonders viel. Mit dem Binärsystem bin ich aber sehr gut vertraut und auch mit anderen mathematischen Zusammenhängen, die wir noch nicht behandelt haben. Aber mathematische Körper sind mir ehrlich kein begriff... Wo gibts denn Internetseiten, wo ich mich darüber informieren kann?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »