7 hoch 23 modulo 143

peethebee

Hallo!

Wer kann mir den mathematischen Ausruck "7 hoch 23 modulo 143" in C++ umsetzen?
Meine eigenen Versuche stehen hier:

cout << pow(7, 23) % 143 <<endl;

Das fürht zu folgender Fehlermeldung meines Dev-C++ 4.9.9.2:

22 Y:\C++\main.cpp invalid operands of types `double' and `int' to binary `operator%'

Was läuft hier falsch?

Wäre für eine kleine Hilfe dankbar,
peethebee

Hall

Die Fehlermeldung riecht nach casten, würde ich sagen.

chrische

fmod(pow(7, 23), 143)

peethebee

Danke!! Funktioniert. Ich hatte es mit mod(pow...)) versucht - grml.

Ponto

peethebee schrieb:

Danke!! Funktioniert. Ich hatte es mit mod(pow...)) versucht - grml.

Wenn du dich auf das Ergebnis von fmod(pow(7, 23), 143) verlässt, dann wirst du für diese Aufgabe 0 Punkte erhalten. Die Lösung ist nicht 93.

Vielleicht micht am schnellsten aber sicher kann man die Lösung mit folgendem Ansatz berechnen:

(a^b) mod c = (a * a^(b-1)) mod c = (a * ((a^(b-1)) mod c)) mod c

Jester

Und wenn's schneller sein muß, dann noch square&multiply benutzen zum Potenz ausrechnen.

peethebee

(a^b) mod c = (a * a^(b-1)) mod c = (a * ((a^(b-1)) mod c)) mod c

Das ist aber kein C++, oder?
Außerdem sieht mir das rekursiv aus...

Ich brauche das, um RSA zu demonstrieren, d.h. Geschwindigkeit ist ein Hauptproblem bei den riesigen Zahlen.
Kann mir vielleicht jemand ein korrektes und funktionierendes Beispiel in C++ machen?

Danke,
peethebee

Jester

peethebee schrieb:

(a^b) mod c = (a * a^(b-1)) mod c = (a * ((a^(b-1)) mod c)) mod c

Das ist aber kein C++, oder?
Außerdem sieht mir das rekursiv aus...

Ne, das ist noch kein C++. Aber es ist ne Formel, die Du einfach implementieren kannst. So wie's da steht ist es auch rekursiv definiert. Läßt sich aber auch sehr leicht iterativ implementieren. Probier's mal!

peethebee

Ich frage mich wie das sinnvoll werden soll, wenn ich Zahlen jenseits von sagen wir 10000 haben...
Dann sollte diese Rekursion doch langsam sein, oder?
Leider sind meine C++-Kenntnisse noch ganz frisch und in RSA (Modulorechnung) lese ich mich gerade erst ein, aber mal sehen...

peethebee

Jester

peethebee schrieb:

Ich frage mich wie das sinnvoll werden soll, wenn ich Zahlen jenseits von sagen wir 10000 haben...
Dann sollte diese Rekursion doch langsam sein, oder?
Leider sind meine C++-Kenntnisse noch ganz frisch und in RSA (Modulorechnung) lese ich mich gerade erst ein, aber mal sehen...

Wie gesagt, implementiere es iterativ. Mit square&multiply sollte es dann auch gut schnell werden.

http://de.wikipedia.org/wiki/Schnelles_Potenzieren da kannst Du fast abschreiben.

Ponto

peethebee schrieb:

Ich frage mich wie das sinnvoll werden soll, wenn ich Zahlen jenseits von sagen wir 10000 haben...
Dann sollte diese Rekursion doch langsam sein, oder?
Leider sind meine C++-Kenntnisse noch ganz frisch und in RSA (Modulorechnung) lese ich mich gerade erst ein, aber mal sehen...

peethebee

Dann musst du den Vorschlag von Jester implementieren, falls ich das richtig verstehe. Da hilft folgender Ansatz:

7^23 = 7^(16 + 4 + 2 + 1) = 7⁽²4 + 2^2 + 2^1 + 2^0) = 7⁽²4) * 7⁽²2) * 7⁽²1) * 7⁽²0)

und a⁽²b) = a⁽²(b-1) + 2^(b-1)) = a⁽²(b-1)) * a⁽²(b-1))

Wenn du aber schnell für RSA rechnen möchtest, solltest du eine BigInteger-Bibliothek wie zum Beispiel gmp verwenden. Die kann dann deine Operationen korrekt und schnell ausrechnen.

peethebee

Danke. Sieht machbar aus. Werde ich heute Nacht mal versuchen.

Edit: wo komme ich an die Bib ran? oder ist die bei Devcpp 4.9.9.2 irgendwo dabei?

peethebee

Helmut S.

#include <iostream>
using namespace std;

#define pMod(b, e, m)   ( e-1  >= 0 ? b : 1)% m * \
                        ( e-2  >= 0 ? b : 1)% m * \
                        ( e-3  >= 0 ? b : 1)% m * \
                        ( e-4  >= 0 ? b : 1)% m * \
                        ( e-5  >= 0 ? b : 1)% m * \
                        ( e-6  >= 0 ? b : 1)% m * \
                        ( e-7  >= 0 ? b : 1)% m * \
                        ( e-8  >= 0 ? b : 1)% m * \
                        ( e-9  >= 0 ? b : 1)% m * \
                        ( e-10 >= 0 ? b : 1)% m * \
                        ( e-11 >= 0 ? b : 1)% m * \
                        ( e-12 >= 0 ? b : 1)% m * \
                        ( e-13 >= 0 ? b : 1)% m * \
                        ( e-14 >= 0 ? b : 1)% m * \
                        ( e-15 >= 0 ? b : 1)% m * \
                        ( e-16 >= 0 ? b : 1)% m * \
                        ( e-17 >= 0 ? b : 1)% m * \
                        ( e-18 >= 0 ? b : 1)% m * \
                        ( e-19 >= 0 ? b : 1)% m * \
                        ( e-20 >= 0 ? b : 1)% m * \
                        ( e-21 >= 0 ? b : 1)% m * \
                        ( e-22 >= 0 ? b : 1)% m * \
                        ( e-23 >= 0 ? b : 1)% m * \
                        ( e-24 >= 0 ? b : 1)% m
int main()
{
   int result1 = pMod(7, 23, 143);  // Ergebnis vom Precompiler

   int result2 = 1;
   int b = 7;
   for (int e = 23; e; e--)         // RSA (Modulorechnung) 
      result2 = (result2 * b) % 143; 

   if (result1 == result2)
      cout << "Ergebnis = " << result1 << endl; 
   return 0;
}

Javaner

peethebee schrieb:

Ich frage mich wie das sinnvoll werden soll, wenn ich Zahlen jenseits von sagen wir 10000 haben...

Auf jeden Fall sinnvoller als mit floats(doubles) zu hantieren.
Gerade in der Modulo-Berechnung kommt es auf exakte Berechnung an
und floats haben nur eine begrenzte Genauigkeit. Darum gibt es nur 2 Möglichkeiten:

Ausweichen auf beliebig große Integer. In Java sind das BigInteger.
Keine Ahnung ob's in C++ auch sowas gibt.
Implementierung eines Algorithmusses auf den Jester hingewiesen hat.

Schließlich kamen die Mathematiker auch 2.500 Jahre ohne Taschenrechner aus.

Edit: Uuppss! Da gab es ja schon eine zweite Seite in diesem Thread