Primitivwurzeln ermitteln

[McMannus]

Hi all,
anlässlich meiner Facharbeit im Fach Mathematik bin ich über das mathematische Thema der Primitivwurzeln gestolpert. Ich habe mich hingesetzt und ein Programm geschrieben, dass theoretisch die Primitivwurzeln von Primzahlen bestimmt und mir die Materie ein wenig näher bringt. Um nun die Richtigkeit zu testen, habe ich meine ermittelten Werte mit den Tabellen von http://walhall.wiwi.hu-berlin.de/or/...root/index.php verglichen, jedoch werden bei mir nur ein Teil der Primitivwurzeln ermittelt, d.h. ein paar Zahlen werden einfach ausgelassen. Ich frage mich im Moment wo der Verständnisfehler liegt.
Bspw: Mein Programm ermittelt für die Primzahl 19 die Primitivwurzeln 2;3;10;14. Laut Tabelle sind es aber 2;3;10;13;14;15.

Anbei mein Programm. Danke für die Hilfe!

/*
Textfelder leeren
*/
function leeren() {
    primitivwurzeln_txt.text = "";
    status_txt.text = "";
}
 
/*
  Eingabe auf Primzahl überprüfen mit dem Sieb von des Eratosthenes
  max : Zu überprüfende natürliche Zahl
*/
function primzahlcheck(max):Boolean {
    var primcheck:Boolean = false;
    var sieve = new Array(max+1);
    sieve.push(0);
    var i = 2;
    while (i < max+1) {
        if (i == max) {
            primcheck = true;
        }
        for( var j = i * 2; j < max+1; j+= i){
            sieve[j] = 1;
        }
        do {
            i++;
        } while (sieve[i] == 1);
    }
    return primcheck;
}
 
/*
  Prüfen, ob alle Zahlen von 1..zahl-1 im Array enthalten sind
  zahl : Primzahl
  ergebnisse : Ergebnisse aller Potenzen a^0%zahl..a^zahl-2%zahl,
               wobei a alle Zahlen von 1..zahl-1 sind
*/
function zahlencheck(zahl:Number,ergebnisse:Array):Boolean {
    var zahlenarray:Array = [];
    var ergcheck:Boolean = true;
    for (var i:Number = 0;i<zahl-1;i++) {
        merke = ergebnisse[i];
        zahlenarray[merke] = merke;
    }
    for (var j:Number = 1;j<=zahl-1;j++) {
        if (isNaN(zahlenarray[j])) {
            ergcheck = false;
        }
    }
    if (ergcheck) {
        return true;
    } else { return false; }
}
 
/*
  Überprüfen, ob Primzahl Primitivwurzeln hat und diese ausgeben
  primzahl : Zu überprüfende Zahl
*/
function primitivwurzel(primzahl:Number) {
    status_txt.text = "Zu untersuchende Primzahl: "+primzahl+"\n\n";
    var ergebnisse:Array = [];
    var ergcheck:Boolean;
    for (var j:Number = 1;j<primzahl;j++) {
        status_txt.text += "Ist "+j+" eine Primitivwurzel modulo "+primzahl+"?\n";
        for (var i:Number = 0;i<primzahl-1;i++) {
            ergebnisse[i] = Math.pow(j,i)%primzahl;
            status_txt.text += j+" ^ "+i+" mod "+primzahl+" = "+Math.pow(j,i)%primzahl+"\n";
        }
        ergcheck = zahlencheck(primzahl,ergebnisse);
        status_txt.text += "Sind alle natürlichen Zahlen von 1 bis "+(primzahl-1)+" vorhanden? Antwort: "+ergcheck+"\n";
        if (ergcheck) {
            status_txt.text += j+" ist eine Primitivwurzel modulo "+primzahl+"!\n";
            primitivwurzeln_txt.text += j + "; ";
        } else { status_txt.text += j+" ist keine Primitivwurzel modulo "+primzahl+"!\n"; }
        status_txt.text += "\n";
    }
}
 
untersuchen_btn.onRelease = function() {
    leeren();
    if (primzahlcheck(primzahl_txt.text)) {
        primitivwurzel(primzahl_txt.text);
        mystring = primitivwurzeln_txt.text;
        primitivwurzeln_txt.text = mystring.substring(0,mystring.length-2);
    } else { status_txt.text = "Die Zahl " +primzahl_txt.text+" ist keine Primzahl!"; }
} 

Die Fla:www.holym.de/test/primitivwurzel.rar

Grüßle

[hgseib]

mächtig viel programm ;-)

wenn's dir was nützt:
http://www.seibsprogrammladen.de/fra...rithmen/Number
Primfaktoren


natürlich bin ich weder in diesem fachgebiet bewandert, noch kann ich dein programm auf die schnelle analysieren, aber

trace(Math.pow(13, 17)); // 8.65041591938134e+18

ich denke mal, es wäre richtig die ganze zahl zu kennen und nicht eine flieskommadarstellung mit maximal 15 signifikanten stellen?

[McMannus]

Mh, es tut mir Leid, dies sagen zu müssen, aber ich verstehe nicht ganz, was deine function mit der Ermittlung von Primitivwurzeln zu tun hat. Die Überprüfung, ob die Zahl eine Primzahl ist, ist eigentlich nur Nebensache. Ich gehe davon aus, dass eingegebene Zahlen Primzahlen sind.
So, wie ich das verstanden habe, ist eine Primitivwurzel modulo m diejenige natürliche Zahl a, mit deren Potenzen a^0 mod m bis a^m-2 modulo m man als Ergebnis alle Elemente der Restklassengruppe von m berechnen kann.
Nach diesem Prinzip habe ich mein Programm aufgebaut.
Meine Frage ist nun ob ich von vorneherein einen Denkfehler begangen habe. Das Programm selbst tract mir alle Ergebnisse zur Überprüfung, aber ich habe kein falsches Ergebnis gefunden, folglich müsst ja an meinem Ansatz etwas nicht stimmen.

Danke, dass ihr eure Matheköpfe für mich anstrengt

[hgseib]

da muss dir garnichts leid tun ;-)


dann nochmal so:

ergebnisse[i] = Math.pow(j, i)%primzahl;
trace(Math.pow(j, i)); // <--- das in dein programm ergänzen.

ich glaube kaum, das bei grösseren zahlen (mehr als 15 signifikante stellen) das modulo richtig berechnet wird.

[McMannus]

Das hab ich gerade mal getan.
Ergebnis Flash:

13 ^ 0 = 1
13 ^ 1 = 13
13 ^ 2 = 169
13 ^ 3 = 2197
13 ^ 4 = 28561
13 ^ 5 = 371293
13 ^ 6 = 4826809
13 ^ 7 = 62748517
13 ^ 8 = 815730721
13 ^ 9 = 10604499373
13 ^ 10 = 137858491849
13 ^ 11 = 1792160394037
13 ^ 12 = 23298085122481
13 ^ 13 = 302875106592253
13 ^ 14 = 3.93737638569929e+15
13 ^ 15 = 5.11858930140908e+16
13 ^ 16 = 6.6541660918318e+17
13 ^ 17 = 8.65041591938134e+18

13 ^ 0 mod 19 = 1
13 ^ 1 mod 19 = 13
13 ^ 2 mod 19 = 17
13 ^ 3 mod 19 = 12
13 ^ 4 mod 19 = 4
13 ^ 5 mod 19 = 14
13 ^ 6 mod 19 = 11
13 ^ 7 mod 19 = 10
13 ^ 8 mod 19 = 16
13 ^ 9 mod 19 = 18
13 ^ 10 mod 19 = 6
13 ^ 11 mod 19 = 2
13 ^ 12 mod 19 = 7
13 ^ 13 mod 19 = 15
13 ^ 14 mod 19 = 5
13 ^ 15 mod 19 = 11
13 ^ 16 mod 19 = 15
13 ^ 17 mod 19 = 9

Per Hand gerechnet:

13 ^ 0 = 1
13 ^ 1 = 13
13 ^ 2 = 169
13 ^ 3 = 2197
13 ^ 4 = 28561
13 ^ 5 = 371293
13 ^ 6 = 4826809
13 ^ 7 = 62748517
13 ^ 8 = 815730721
13 ^ 9 = 10604499373
13 ^ 10 = 137858491849
13 ^ 11 = 1792160394037
13 ^ 12 = 23298085122481
13 ^ 13 = 302875106592253
13 ^ 14 = 3937376385699289
13 ^ 15 = 51185893014090757
13 ^ 16 = 665416609183179841
13 ^ 17 = 8650415919381337933

13 ^ 0 mod 19 = 1
13 ^ 1 mod 19 = 13
13 ^ 2 mod 19 = 17
13 ^ 3 mod 19 = 12
13 ^ 4 mod 19 = 4
13 ^ 5 mod 19 = 14
13 ^ 6 mod 19 = 11
13 ^ 7 mod 19 = 10
13 ^ 8 mod 19 = 16
13 ^ 9 mod 19 = 18
13 ^ 10 mod 19 = 6
13 ^ 11 mod 19 = 2
13 ^ 12 mod 19 = 7
13 ^ 13 mod 19 = 15
13 ^ 14 mod 19 = 5
13 ^ 15 mod 19 = 8
13 ^ 16 mod 19 = 9
13 ^ 17 mod 19 = 3

Flash unterschlägt meine Stellen
Wie man sieht, liegt der Fehler nun wirklich an diesem Rundungsproblem, was bedeutet, dass ich das Thema verstanden habe, da die Ergebnisse nun den Restklassenbereich 1 bis 18 abdecken und somit 13 eine Primitivwurzel modulo 19 ist

@hgseib Besten Dank für den Hinweis!

PS: Wenn wir gerade dabei sind, welche Programmier-Sprachen haben denn genauere Verfahren, um eine größere Menge an Stellen ausrechnen zu können, denn wenn ich das Programm evtl mitabgebe, würde es nicht so gut kommen, wenn nur die Hälfte der Wurzeln ermittelt wird, auch wenn ich den Fehler mitangebe.

Gruß

[Rookie_BS]

unglaublich ;-) einfach so unterschlagen... was sag man dazu. vllt. solltest du für deinen doktortitel in Mathe (sorry fürs platte vokabular) nich auf flash setzen...

ich meine nen zahnarzt nimmt ja auch nich die HILTI auch wenn die sonst nahezu perfekt is...

[McMannus]

Mh, ist kein Doktortitel ist nur ne 15-seitige Facharbeit für die 13te Klasse. Habe nur auf Flash gesetzt, weil ich da am fittesten bin. In Delphi funktioniert es einwandfrei mit dem Int64-Datentyp, bei dem der Wertebereich -2^63..2^63-1 ist. In diesem Sinne ist das Problem quasi gelöst

Dankeschön

[Janoscharlipp]

Man kann sich selber einen Rechner bauen, welcher auf Strings basiert.
Das ist dann zwar viel langsamer, und macht natürlich auch mehr Mühe, aber solang man nicht so viele Rechenoperationen benötigt schon noch machbar.

Ansonsten kann man den Zahlenbereich auch immer Erweitern, indem man mehrere Zahlen hintereinander hängt, also z.B. immer nur den Bereich bis 2^32 verwendet, und dann zur nächsten Zahl umbricht, da muss man sich dann nur Gedanken machen, was an dem Übergang von einer Zahl zur nächsten passiert.

[Rookie_BS]

;-) für ne facharbeit inna 13ten - brennste da aber ganz schön was wech mit flash und so wa - och inhaltlich meen ick jezze!

:: burn baby :: grinz ::

viel spass DAbei

[McMannus]

Mh, es geht um die Transportsicherheit des SSL-Protokolls und Hash-Funktionen benutzen eben diese Primitivwurzeln

[hgseib]

nur als ergänzung:

in fachkreisen (also z.b. hier ;-) ist bekannt, das zahlen in computern (also nicht nur in flash) nach Norm IEEE 754 berechnet werden:
http://de.wikipedia.org/wiki/IEEE_754
vorallem dürfte kaum noch jemand irgendwelche rechenroutinen selbst programmieren. und die zeiten, als man arithmetic-prozessoren einzeln kaufen konnte ist auch schon lange vorbei, da inzwischen wohl jeder prozessor sogar mehrere APUs integriert hat.

15 signifikante stellen und ein wertebereich von +/-10 hoch 308 langt für das alltägliche rechnen. wer z.b. kaufmänische jobs zu erledigen hat, der muss halt gesondert darauf achten, das er keine falschen rundungsfehler bekommt.


für wissenschaftliches arbeiten mit astronomisch grossen/ kleinen zahlen dürfte wohl
http://de.wikipedia.org/wiki/Mathematica
der unangefochtene könig sein?

und wer langeweile hat, der kann sich auch in flash rechenoperationen für beliebige genauigkeit programmieren ;-) dafür benützt man anstelle von ziffern zahlen. so kann man z.b. im 100er, 10000er oder 1000000er system rechnen. die rechenforschriften sind überall gleich:
12345678901234567890
wäre dann z.b. im 100000er system eine zahl mit diesen 'ziffern':
x=[12345, 67890, 12345, 67890];

[hgseib]

Zitat von McMannus

Wenn wir gerade dabei sind, welche Programmier-Sprachen haben denn genauere Verfahren, um eine größere Menge an Stellen ausrechnen zu können, denn wenn ich das Programm evtl mitabgebe, würde es nicht so gut kommen, wenn nur die Hälfte der Wurzeln ermittelt wird, auch wenn ich den Fehler mitangebe.

halt mal im internet suchen, z.b. nach
modulo grosse zahlen

schliesslich musst du die zahl garnicht ausrechnen, du benötigst ja nur das mod

vielleicht kann dir sowas weiter helfen?
http://de.wikipedia.org/wiki/Eulersche_φ-Funktion