Aufgabe 1 Primzahl wählen

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Aufgabe 1 Primzahl wählen

Beitrag von null »

Hallo,

kann mir jemand eine gute Java Libary empfehlen, die mit zufällig 96 Bit Primzahlen für die erste Übung ausspuckt?

Oder darf ich ein paar Primzahlen dieser Größenordnung hart einprogrammieren und dann zuvällig von diesen eine wählen?

Vielen Dank

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: Aufgabe 1 Primzahl wählen

Beitrag von sab »

Die BigInteger Klasse bringt eine Methode mit, die probablePrime(int bitLength, Random rnd) heißt.

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: Aufgabe 1 Primzahl wählen

Beitrag von null »

ohhh!! :D :D :D Ein Grund, das ganze Zeug in Java zu implementieren :)

Aber wie der Name der Methode schon sagt, kann wahrscheinlich nicht zu 100 % gesagt werden, ob es sich um eine Primzahl handelt, oder?

Danke für den Tipp!

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: Aufgabe 1 Primzahl wählen

Beitrag von sab »

Das stimmt wohl mit Java, ich glaube für C gibt es sowas (zumindest von Haus aus) nicht, aber ich weiß es um ehrlich zu sein nicht.
null hat geschrieben:Aber wie der Name der Methode schon sagt, kann wahrscheinlich nicht zu 100 % gesagt werden, ob es sich um eine Primzahl handelt, oder?
Andreas Peters, der heute die Vorlesung gehalten hat, sagte, dass diese Wahrscheinlichkeit ausreicht, weil es wohl in diesen Größenordnungen keine richtige (vielleicht auch nur effiziente) Verfahren gibt, um Primzahlen zu bestimmen - allerdings können wir uns wohl auf diese Wahrscheinlichkeiten verlassen. Außerdem würden ohnehin fast alle Implementierungen nur probabilistisch sein.

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Re: Aufgabe 1 Primzahl wählen

Beitrag von null »

Ok, vielen Dank!

Außerdem würde ich gerne wissen, warum die Primzahl p', also die die wir mit "probablePrime" erhalten, die Eigenschaft p = 2p'-1 erfüllen muss, wobei p auch eine Primzahl ist. Was bringt das? Warum suchen wir uns nicht einfach eine Primzahl heraus, mit der wir dann die Restklassengruppe bilden?

Danke

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Aufgabe 1 Primzahl wählen

Beitrag von JannikV »

sab hat geschrieben:Das stimmt wohl mit Java, ich glaube für C gibt es sowas (zumindest von Haus aus) nicht, aber ich weiß es um ehrlich zu sein nicht.
Für C und C++ gibt es die "GNU Multiple Precision Arithmetic Library". Eine ziemlich mächtige Bibliothek. Muss man sich erstmal einarbeiten, aber dann kann das Ding wirklich ne ganze Menge. http://gmplib.org/manual/

null hat geschrieben:Außerdem würde ich gerne wissen, warum die Primzahl p', also die die wir mit "probablePrime" erhalten, die Eigenschaft p = 2p'-1 erfüllen muss, wobei p auch eine Primzahl ist. Was bringt das? Warum suchen wir uns nicht einfach eine Primzahl heraus, mit der wir dann die Restklassengruppe bilden?
Auf dem Aufgabenblatt steht, dass wir einen Generator g finden, in dem wir zeigen, dass die Eigenschaften \(g^2 \not\equiv 1 (\bmod p)\) und \(g^{p'} \not\equiv 1 (\bmod p)\) gelten.

VG
Zuletzt geändert von JannikV am 27. Dez 2012 18:12, insgesamt 1-mal geändert.

studentabc
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 31. Okt 2011 13:56

Re: Aufgabe 1 Primzahl wählen

Beitrag von studentabc »

JannikV hat geschrieben: Auf dem Aufgabenblatt steht, dass wir einen Generator g finden, in dem wir zeigen, dass die Eigenschaften \(g^2 \ne 1 \bmod p\) und \(g^{p'} \ne 1 \bmod p\) gelten.

VG
muss ich dann nicht folgendes überprüfen: \((g^2 \bmod p )\ne 1 \bmod p\) und \((g^{p'} \bmod p )\ne 1 \bmod p\)
sonst würde das ja keinen sinn machen oder?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Aufgabe 1 Primzahl wählen

Beitrag von JannikV »

Das ist damit gemeint. Das mod p sollte vll in Klammern dahinter stehen, dann ist es klarer.
Ich editier mal...

VG

Antworten

Zurück zu „Archiv“