Erzeugen von großen Primzahlen

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Erzeugen von großen Primzahlen

    Hallo Leute,


    ich suche eine effiziente Lösung, um in PHP große Primzahlen (allerhöchstes Maximum sind ca. 120 Stellen, mehr brauche ich nicht) zu erzeugen.

    z.Zt. erzeuge ich eine große Zufallszahle (ungerade) und teste, ob diese Zahl eine Primzahl ist. Dazu nehme ich den Fermat-Test.

    Der Fermat-Test geht wie folgt.
    Wenn 2^(n-1) mod n = 1, dann ist n eine Primzahl.
    PHP-Code:
    function isPrime($n)
    {
     return ((
    bcpowmod(2,bcsub($n,1),$n)!="1") ? false true);

    In einigen PHP Versionen ist bcpowmod schon implementiert, in anderen noch nicht, dann muss man es in php implementieren.


    Falls die Zahl keine Primzahl ist, addiere ich 2 dazu und teste wieder, bis ich eine Primzahl finde. Das Problem bei dem Ganzen ist die Performance. Manchmal hat man Glück und liegt mit der Zufallszahl dicht neben einer Primzahl sodass nur ein paar Mal getestet werden muss und manchmal muss man ein paar hundert Tests durchführen. Und mein Primzahltest von oben ist in php nicht gerade schnell. Bei sehr sehr kleinen Zahlen geht es ja noch einigermaßen. Aber bei Zahlen wie 1546255733086197899652914449938053774373736611225094826481407302309289890044525493906099655458365041 403140043571 braucht die Funktion 1,6 Sekunden um zu testen, ob es eine Primzahl ist oder nicht (auf einem AMD K6-III 400 MhZ).

    Also nochmal meine Bitte von oben: Wer kennt einen effizienten Weg um große Primzahlen zu erzeugen?

    Ich habe mal in den C-Sourcecode von openssl reingeschaut, kapiere es allerdings nicht so ganz.

    [color="#334D7B"]"Los, lass uns loslegen! Hm ? Quatschen können wir hinterher immer noch!"[/color]
    [color="#9C5245"]"Aber Bommel, wir können jetzt nicht bumsen. Wir müssen doch erst den Kindern - ... "[/color]
    [color="#334D7B"]"Ja ja ja. Du willst immer nur das Eine. Buchstabenzeigen, Buchstabenzeigen - meine Gefühle sind dir wohl scheißegal."[/color]

    © Harald Schmidt

  • #2
    Die Summe zweier aufeinanderfolgender Primzahlen +-1 ist meist auch eine Primzahl.

    Das hilft dir vielleicht eine bessere Standzahl für deinen Algorithmus zu finden
    TBT

    Die zwei wichtigsten Regeln für eine berufliche Karriere:
    1. Verrate niemals alles was du weißt!


    PHP 2 AllPatrizier II Browsergame

    Kommentar


    • #3
      da gibs doch ganze seiten über primzahlermittlung im internet. hhmm

      darf ich mal fragen wozu du sowas brauchst ?
      meine Projekte bestaunen: http://www.kleiza.de

      Kommentar


      • #4
        würde mich auch mal interessieren.
        ich hab in der schule schon keinen wirklichen sinn in primzahlen gesehen *g*

        Es wäre ziemlich effizient sich einen stärkeren Server zuzulegen *fg*

        Kommentar


        • #5
          Kennst diese Seite, hilft sie Dir weiter?
          Zumindest hier wurde die Primzahlensuchen von PGP (Pretty Good Privacy)
          abgekupfert.
          http://dev.deepsource.ch/index.php?C...&SubCategory=6

          @Radium2k
          Dieser Link zeigt Dir ein Anwendungsbeispiel für Primzahlen.

          Kommentar

          Lädt...
          X