4. Problem beim Lösen von Kongruenzen mit großen Zahlen

Problem beim Lösen von Kongruenzen mit großen Zahlen

  • 6

    Hallo,
    ich wollte mir ein Programm basteln, welches das Verschlüsseln und Entschlüsseln gemäß des RSA-Verfahrens vereinfacht. Mein Problem ist nun, dass das Programm zwar bei Rechnungen (Kongruenzen) mit kleinen Zahlen wie 12^2 mod 99 das richtige Ergebnis liefert, bei Rechnungen wie z.B. 596^233 mod 851 (Ergebnis sollte 65 sein) aber leider nicht. Daher bitte ich um eure Hilfe. Hier mein Programm ( Ich programmiere noch nicht lange und nicht viel, daher bitte ich gewissse umständliche Zeilen zu verzeihen):

    int main(int argc, char *argv[])
{            printf("\n\n\t\t\tModulo-Rechner");
             printf("\n\n\t\t\tx = a^b mod n");
             long long a,b,c,n,x;
             char temp;
             printf("\n\tBitte a eingeben:\t\t");
             scanf("%lld%c", &a,&temp); 
             printf("\n\tBitte b eingeben:\t\t");
             scanf("%lld%c", &b,&temp);
             printf("\n\tBitte n eingeben:\t\t");
             scanf("%lld%c", &n,&temp);
                       c=pow(a, b);
                       x = c % n; 
             printf("\n\n\tErgebnis x:\t\t\t\t%lld\n\n\n\n",x);

    Ich hoffe ihr könnt mir helfen oder auf ein Programm verweisen, welches kostenlos ist und solche Rechnungen, aber wenn möglich nicht mehr, lösen kann.

    Mfg 6peg

    0
  • V

    Berechne die Potenz einfach selber in einer Schleife. Und fürre den Modulo-Schritt auch für jedes Zwischenergebnis aus, dann gibts keinen Überlauf.

    0
  • Mod

    596^233 ist wohl ein bisschen zu groß für einen long. Selbst für einen 128-Bit großen unsigned long long ist das immer noch um über 600 Größenordnungen zu groß (Größenordnungen! Nicht um einen Faktor 600!). Nein, da muss ein ganz anderes Verfahren her, um mit solch großen Zahlen zu rechnen. Was du suchst ist:
    http://en.wikipedia.org/wiki/Modular_exponentiation

    edit: Die zweite Methode auf der Seite ist übrigens das gleiche wie das was volkard vorschlägt.

    0
  • 6

    Hallo, danke erstmals für die schnellen Antworten. Ich dachte mir schon, dass diese Zahlen auch für long long "etwas" zu hoch sind ;-), wollte aber auf Nummer sicher gehen, da es ja ebenso gut sein könnte, dass ich einen Fehler gemacht habe. Ich habe das Programm nun umgeändert und mit euren Tipps umprogrammiert und mir dann erst den Link angesehen ( wollte erstmals selbst versuchen das Gesagte umzusetzen). Ich werde leider aber nicht ganz schlau aus dem Link, denke aber, dass ich es auf diese Art programmiet habe. Könnt ihr das bestätigen?

    Außerdem hätte ich noch eine Frage an euch als erfahrene Programmierer und zwar ob bzw. was ihr im Quelltext ändern würdet und warum (außer der Ordnung/Gliederung)? Würde mich sehr interessieren, da ich mich im Programmieren sehr gerne verbessern würde.

    Hier der Text:

    int main(int argc, char *argv[])
{            printf("\n\n\t\t\tModulo-Rechner");
             printf("\n\n\t\t\tx = a^b mod n");
             long long a,b,n;
             char temp;
             printf("\n\tBitte a eingeben:\t\t");
             scanf("%lld%c", &a,&temp); 
             printf("\n\tBitte b eingeben:\t\t");
             scanf("%lld%c", &b,&temp);
             printf("\n\tBitte n eingeben:\t\t");
             scanf("%lld%c", &n,&temp);
             int i=1;
             long long c=a;
             while(i<b) {

                         c = c * a;
                         c = c % n; 
                         i++;
                         }
             printf("\n\n\tErgebnis c:\t\t\t\t%lld\n\n\n\n",c);

    mfG 6peg

    0
  • V

    hier for statt while

    0
  • Mod

    So ungefähr sähe das bei mir aus:

    #include <stdio.h>

unsigned mod_exp(unsigned base, unsigned exponent, unsigned mod)
{
  unsigned long long c = 1;
  for (unsigned e = 0; e < exponent; ++e)
    {
      c *= (unsigned long long) base;
      c %= mod;
    }
  return c;
} 

int main()
{        
  puts("Modulo-Rechner: x = a^b mod n\nBitte a, b und n eingeben:");
  unsigned a,b,n;
  if (scanf("%u %u %u", &a, &b, &n) == 3)
    printf("Ergebnis: %u\n", mod_exp(a,b,n));
  else
    puts("Konnte Eingabe nicht lesen.");
}

    Mein Programm sollte richtig sein. Die Korrektheit deines Programms kannst du durch Vergleich überprüfen (oder, wenn du meinem Programm nicht traust:
    http://http://www.wolframalpha.com
    Wir bekommen jedenfalls beide 65 für deine Ursprungsfrage heraus.

    0
  • 6

    Nochmals danke für die schnellen Antworten und die Hilfe!

    Ich werde mir dein Programm genauer ansehen (kenne leider nicht alle Befehle) um etwaige Verbesserungen zu verstehen und auch über den Unterschied zwischen for und while werde ich mich nochmals genauer infromieren.

    mfg 6peg

    0
Anmelden zum Antworten