Primitivwurzeltest/Exponenzieren mit hohen Zahlen

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

      Primitivwurzeltest/Exponenzieren mit hohen Zahlen

      Guten Abend zusammen,

      da ich gerne einen Primitivwurzeltest in C# selbst implementieren würde und das auch schon soweit tut bis zu einer bestimmten Größe, die dummerweise vom Datentyp long begrenzt wird, muss ich mich jetzt hier mal hilfesuchend melden.
      Es gibt zwar noch die Möglichkeit wie ich gesehen habe BigInteger zu verwenden , meine Frage nun, gibt es eine weitere Möglichkeit (byte array etc) die Ergebnisse beim Exponenzieren zu speichern?
      Oder habe ich beim Exponenzieren eine Umformung übersehen bzw. kann ich das Modulo früher mit einbauen um die zu exponenzierenden Zahlen kleiner zu halten?

      Spoiler anzeigen

      Quellcode

      1. public long lowestPrimRoot(long p)//p ist die gewählte Primzahl
      2. {
      3. long sol = 0;
      4. long potenz = p - 2;
      5. for (long i = 1; i <= potenz; i++)
      6. {
      7. if (primRootTest(p, i))
      8. {
      9. sol = i;
      10. break;
      11. }
      12. }
      13. return sol;
      14. }
      15. private Boolean isPrimRoot(long p,long toTest)// toTest die aktuell gewählte "mögliche" Primitivwurzel
      16. {
      17. long phi = p-2;
      18. for(int i = 1; i<p-2;i++)
      19. {
      20. long tmp = (long)Math.Round((float)phi / (float)i, 0, MidpointRounding.AwayFromZero); ;
      21. long tmp2 = FastExp(toTest, tmp); //<----- Probleme mit Datentyp beim exponenzieren
      22. long tmp3 = tmp2 % p;
      23. if (tmp3 == 1)
      24. return false;
      25. }
      26. return true;
      27. }
      28. public long FastExp(long a, long b)
      29. {
      30. if (a == 0)
      31. return 1;
      32. long result = 1;
      33. while (b != 0)
      34. {
      35. if ((b % 2) == 1)
      36. {
      37. result *= a;
      38. }
      39. b >>= 1;
      40. a *= a;
      41. }
      42. return result;
      43. }
      Alles anzeigen


      Beste Grüße und vielen Dank

      Edit:

      Mit ist vergangene Woche doch promt am nächsten Tag aufgefallen das ich einen Denkfehler hatte, so wissen wir alle das gilt:
      (p^g) mod d = (p1*p2*...*pg) mod d = ((p1 mod d)*(p2 mod d)*...*(pg mod d)
      was bedeutet das wir beim Exponenzieren nicht mehr in allzu große Größen kommen.

      Methode würde dann auf folgendes rauslaufen:
      Spoiler anzeigen

      Quellcode

      1. public int FastExp(int a, int b,int mod)
      2. {
      3. if (a == 0)
      4. return 1;
      5. int result = 1;
      6. while (b != 0)
      7. {
      8. if ((b % 2) == 1)
      9. {
      10. result *= a;
      11. result %= mod;
      12. }
      13. b >>= 1;
      14. a *= a;
      15. a %= mod;
      16. }
      17. return result;
      18. }
      Alles anzeigen

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von oxxxe ()