Programmierwettbewerb - Erzeugende Elemente im Primzahlenkörper

[Aqualon]

Hallo Leute!

Angeregt durch eine Übungsaufgabe in Mathematik, ist mir die Idee zu einem kleinen Programmierwettstreit gekommen.

Es geht um erzeugende Elemente a in einem Körper Z der ganzen Zahlen mit n Elementen, wobei n eine Primzahl sein muss.

Ein erzeugendes Element ist dasjenige a, das potenziert mit x|0 <= x < n und den Restwert mit Modulo n berechnet, alle Elemente des Körpers Z erzeugt.

In Z mit n=17 ist z.B. 3 ein erzeugendes Element, da 3^0 mod 17, 3^1 mod 17, ..., 3^15 mod 17, 3^16 mod 17, alle a|0 < a < 17 erzeugen kann.

Natürlich ist Z17 nicht gerade eine große Herausforderung, deswegen begeben wir uns in Z mit n = 8999. Gesucht sind alle erzeugenden Elemente und wieviele es von ihnen gibt. Ausgabe der Werte kann direkt auf dem Bildschirm oder auch in einer Datei geschehen.

Jede Programmiersprache ist natürlich grundsätzlich erlaubt, es sollte aber gesagt werden, dass 8999^8998 eine Zahl ist, die garantiert in keinen der üblichen Datentypen wie int oder long passt (~6,916e+35579), wenn sie komplett ausgerechnet wird. Ausserdem sollte das Ergebnis auch in endlicher Zeit rauskommen (<1h Rechenzeit).

Mein Lösungsversuch wird irgendwann am WE gepostet werden. Viel Spaß beim knobeln und optimieren!

Aqua

[HajottV]

na für sowas schmeiße ich doch ned den compiler an... :wink:

hingerotzt in awk sieht das so aus:


BEGIN {

n = 8999

for (g = 2; g < n; g++) {

delete field

s = 1

for (i = 1; ! (s in field); i++) {
field[s]
s *= g
if (s >= n) s %= n
}

if (i == n) print g
}
}


wenn Du die Anzahl brauchst: "| wc".

ergänzung: ist natürlich ned sonderlich performant, bleibt aber weit unter einer stunde.

[HajottV]

das ganze noch in c (braucht < 1s)



const int n = 8999;
int field[9000];
int s;

for (int g = 2; g < n; g++) {

s = 1;

for (int i = 1; field[s] != g; i++) {
field[s] = g;
s *= g;
if (s >= n) s %= n;
}

if (i == n) printf("%i\n", g);
}


man könnte das ganze jetzt noch optimieren, indem man so eine art sieb des Eratosthenes benutzt: wenn g generator ist und e' kein generator, dann ist g*e' ein generator. damit kann man sich eine menge tests sparen.

[HajottV]

0.3s

Ich nutze folgendes aus:

wenn g ein generator ist und e kein generator, ist e*g generator.
wenn g kein generator ist und e kein generator, ist e*g auch kein generator.


const int n = 8999;
int field[n + 1];
bool generator[n + 1];
bool known [n + 1];

for (int g = 2; g < n; g++) {

if (known[g]) continue;

int s = 1;

for (int i = 1; field[s] != g; i++) {
field[s] = g;
s *= g;
if (s >= n) s %= n;
}

generator[g] = (i == n);

if (! generator[g])
for (i = 2; i < g && i * g < n; i++)
if (generator[i]) {
known[i * g] = true;
generator[i * g] = true;
}
else {
known[i * g] = true;
generator[i * g] = false;
}
else
for (i = 2; i < g && i * g < n; i++)
if (! generator[i]) {
known[i * g] = true;
generator[i * g] = true;
}
}

for (g = 2; g < n; g++)
if (generator[g]) printf("%i\n", g);


um schon mal fragen vorzubeugen: hab liebeskummer und kann eh nicht schlafen :usad:

[micki]

dinner for one... emmm ich meine, contest for one ;)

[Dr.Doom]

Ich kapier die Aufgabe schon nicht. ;) Gibts da eine Anwendung für?

[Aqualon]

Mein Lösungsversuch mit Java:

import java.math.BigInteger;

/**
* Programm berechnet erzeugende Elemente fuer einen Koerper der ganzen Zahlen
* (Die Anzahl der Elemente muss prim sein!)
*
* @author Aqualon
*/
public class ErzeugendeElemente2 {

public static void main(String[] args) {

//Anzahl der Elemente des Koerpers
int n = Integer.parseInt(args[0]);

int z_erzeugendeElemente=0;

//Array zum Ueberpruefen der gefundenen Elemente
boolean[] gefundenesElement = new boolean[n];

//Berechnen aller Elemente fuer 0 <= a < n
for (int a = 0; a < n; a++)

{
//if(a%100==0) System.out.println(a);
boolean erzeugendesElement = true;

//Fuellen des Array mit false-Werten
for (int i = 1; i < gefundenesElement.length; i++) {
gefundenesElement[i] = false;
}

//Setzen von Stelle 0 auf true
gefundenesElement[0] = true;

//Setzen der berechneten Elemente auf true
for (int x = 0; x < n; x++) {
BigInteger bigint = BigInteger.valueOf(a);
bigint = bigint.modPow(BigInteger.valueOf(x), BigInteger.valueOf(n));
gefundenesElement[bigint.intValue()] = true;
}

//Auswerten des Array und setzen des Wertes von erzeugendesElement
for (int i = 0; i < gefundenesElement.length; i++) {
//System.out.println(gefundenesElement[i]);
if (gefundenesElement[i] == false) {
erzeugendesElement = false;
}
}


//Ausgabe, ob a ein erzeugendes Element ist.
if (erzeugendesElement == true) {
z_erzeugendeElemente++;
System.out.println(a);
} else {
//System.out.println(a + " ist kein erzeugendes Element");
}
}
System.out.println(z_erzeugendeElemente);
}
}

Gegenüber der Lösung von HajottV ist das natürlich grausamst langsam (8min auf einem PIV 2.4). Eine rekursive Version des ganzen in C hat aber 3h auf einem Pentium M 1.4 gebraucht.

Das einzige, was ich noch nicht so ganz nachvollziehen konnte ist, wieviele Lösungen es wirklich gibt. Das Programm von HajottV spuckt laut |wc Ausgabe 4079 Lösungen aus, das von mir dagegen 4080. Muss wohl doch noch Zahlenvergleiche durchführen, um zu schauen, ob da nur die Ausgabe nicht stimmt, oder ob die Werte an sich anders sind.

@HajottV: Hast du schon vorher etwas zu diesem Thema programmiert gehabt oder ist dir wirklich in nur einer Stunde diese Lösung eingefallen? Auf jedenfall sehr beeindruckend.

@Dr.Doom: Ich kenne keine praktische Anwendungsmöglichkeit, aber das muss nicht heissen.

Aqua

[HajottV]

Moin... sleepless in Aachen... mal wieder. :redface:

Die Lösung ist tatsächlich erst gestern Nacht entstanden, ohne daß ich da in einer Schublade etwas bereit liegen hatte. Um das aber ins rechte Licht zu rücken: Informatikstudium mit Nebenfach Mathe (Stochastik I-III), insofern habe ich im Grundstudium die Vorlesung Algebra durchstehen müssen, was bei Professor Plesken (RWTH Aachen) zwar enorm traumatisch war... aber, und das muß man dem Mann echt hoch anrechnen, mindestens ebenso lehrreich. Ich wußte daher, wo ich Nachzuschauen hatte, um ein bisschen was über Generatoren zu erfahren. Da stand dann der nette Satz

g ist Generator in G mit |G| = p, p prim <=> g^p != 1. :deal:

Damit war es dann ziemlich einfach, sich die Siebregeln für die ganz schnelle Lösung auszudenken. :idea:

Gruß

Jörg