Algorithmus für 177778! mod 123477767

Question

Ich kenne zwar den
de.wikipedia.org/wiki/Satz_von_Wilson
aber da geht es nur um Primzahlen.

Es geht auch nicht um speziell dieses Beispiel, sondern um große Zahlen, wo man das Zwischernergebnis nicht so einfach berechnen kann.

Ich kenne auch den Algorithmus für die Anzahl der Nullen am Ende von x!, aber wie hilft das weiter?

Da WolframAlpha das Ergebnis in unter 1s liefert, muss es was interessantes geben...

Answer 1

Für einen Computer ist das kein Problem. Anbei ein C++-Code-Schnipsel:

    auto erg = int64_t(1);
    for( int i= 177778; i>1; --i )
        (erg *= i) %= 123477767;
    cout << erg << endl;

liefert in <1s den Wert 23358699. Der 'Trick' besteht halt darin, die Modulo-Funktion nach jeder Multiplikation aufzurufen.

Comments

Ja Werner, so etwas suchte ich - danke.

http://www.lamprechts.de/gerd/Roemisch_JAVA.htm##@Na=177778;b=a-1;c=123477767;d=a%25c;IM=1;@Nd=(d*b)%25c;b--;@Nb%3C2@N0@N0@N#

ergibt nach START in Variable d auch 23358699.

Hier noch ein anderes Beispiel:

Nur kann ich Den Kommentar nicht bewerten wie eine Antwort...

---

EDIT: Habe den Kommentar von Werner zu einer Antwort gemacht.

Answer 2

Habe 23 358 699 heraus. Gerechnet in Haskell in ca. einer Minute mit einem schlechten Prozessor. Dann traue ich Wolfram Alpha die Berechnung unter einer Sekunde auch ohne speziellen Algorithmus zu