Sehr große Zahlen berechnen

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von styxx, 19. Januar 2007 .

Status des Themas:
Es sind keine weiteren Antworten möglich.
  1. 19. Januar 2007
    Habe das Problem alle Primitivwurzeln einer sehr großen Primzahl in C# zu bestimmen.
    Eine Methode dafür habe ich schon geschrieben, nur funktioniert die nur bis zur Primzahl 17 weil es bei allen größern Primzahlen zu einem Overflow kommt.

    Es geht um die Berechnung von a^b % c, d.h die Zahl die Berechnet wird lässt sich unter dem Typ double leicht speichern, nur die Berechnung von a^b (ohne mod) gibt wie gesagt einen Overflow.

    Gibt es eine Möglichkeit große Zahlen zu berechnen (zb 29^27) ?
    Es gibt einen Typ der sich BigInt nennt (http://www.codeproject.com/csharp/BigInteger.asp),
    nur brauch ich ja nur die Berechnung nicht das Speichern der Zahl. (Wenn keine Alternative gibt werde ich damit wohl arbeiten müssen)
    Bzw. gibt es eine Möglichkeit a^b % c auf eine andere Weiße zu berechnen das keine Großen Zahlen entstehen?
     
  2. 19. Januar 2007
    AW: Sehr große Zahlen berechnen

    Was hast du denn gegen die Klasse BigInt? Damit scheinen sich doch sehr große Zahlen berechnen lassen...

    mfg r90
     
  3. 19. Januar 2007
    AW: Sehr große Zahlen berechnen

    Hab im Grunde nichts dagegen, mich interessiert nur wie es ohne "fremde" Hilfe funktioniert.
    Das ganze wurde schon 1976 berechnet Diffie-Hellman-Schlüsselaustausch (auch wenn das mit meinem Problem nicht direkt zu tun hat)
    Von daher würde frag ich mich wie man das Problem mit niedrigen Programmiersprachen gelöst hat(dort wir man ja kaum ein spezielles Integer Array erstellt haben).

    Ein Quellcode von "einem" Diffie-Hellman-Schlüsselaustausch wäre natürlich auch Hilfreich
     
  4. 19. Januar 2007
    AW: Sehr große Zahlen berechnen

    Wie wäre es mit "Long" als ein anderer Datentyp?

    http://msdn2.microsoft.com/de-de/library/ctetwysk(VS.80).aspx

    Nash
     
  5. 19. Januar 2007
    AW: Sehr große Zahlen berechnen

    Long (-9.223.372.036.854.775.808 bis 9.223.372.036.854.775.807) bzw. wenn dann Ulong (0 bis 18.446.744.073.709.551.615)

    Hab ich leider schon ausprobiert ... ist dafür viel zu klein (wären nichtmal tauglich für 10^20 )
    Das Problem liegt daran das ich ne Alternative bzw. einen Trick suche die riesigen Zahlen zu umgehen.

    27^27 % 29 z.B. ist eine Zahl zwischen 0 und 28!
     
  6. 19. Januar 2007
    AW: Sehr große Zahlen berechnen

    hmmm sagt dir der begriff modulare aritmetik etwas?

    könnte dir vll helfen
     
  7. 19. Januar 2007
    AW: Sehr große Zahlen berechnen

    andere Möglichkeit wär du implemtierst rechnen mit Strings, also das alles über Strings läuft (sehr zeitaufwendig zu rechnen) oder du machst es über z.b. nen Long-Array (kP wie das geht, aber es geht)

    mfg r90
     
  8. 19. Januar 2007
    AW: Sehr große Zahlen berechnen

    Klingt gut, werd mich mal informieren
    Edit: Ja, ist eines der Prinzipien worauf der Schlüsselaustausch aufbaut
    Suche dennoch immer noch ne Möglichkeit a ^ b mod c auszurechnen ohne einen Overflow zu erhalten...

    Jep, das mit Strings funktioniert, ist mir aber dann zu aufwendig
    Longarray sollte das gleiche wie Bigint sein s.o.

    Bw, habt ihr beide...
     
  9. 19. Januar 2007
    AW: Sehr große Zahlen berechnen

    Reichen dir den die Möglichkeiten bei BigInt.
    Es ist ein sehr geschickter ansatz wie er arbeitet.

    Sonst bleibt dir wohl nur mit "decimal", was dir wohl auch nicht reicht, zu arbeiten oder die Zahl zu splitten.
     
  10. 19. Januar 2007
    AW: Sehr große Zahlen berechnen

    Die Möglichkeiten reichen da natürlich NUR hätte ich dann den Thread hier nicht aufmachen müssen
    Meine Frage ist aber ob es ne Möglichkeit gibt die Zahlen unabhängig von dem "Speichertyp" (so nenn ich das jetzt mal) auszurechnen. (Die Zahlen die ich erhalte bleiben dank dem Mod ja unter 8 Stellen und passen deshalb locker auf Double bzw Long).

    Sorry, wenn das oben nicht ganz rüber gekommen ist
     
  11. 19. Januar 2007
    AW: Sehr große Zahlen berechnen

    Moin,
    schau mal in Wiki unter 'Diskrete Exponentialfunktion' ich denke das wird dir helfen um die Berechnungen ohne Overflow durchzuführen.

    Gruß Resus
     
  12. 20. Januar 2007
    AW: Sehr große Zahlen berechnen

    1000 Dank
    Genau sowas habe ich gesucht
     
  13. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.