Modulares Inverses mit Fermat

Addition, Subtraktion und Multiplikation verhalten sich unter einem Modulus problemlos, eine gewöhnliche Division jedoch nicht. Sie können nicht einfach dividieren und anschließend den Rest nehmen. ⚠️

Die Lösung ist das modulare Inverse: Division durch x wird zur Multiplikation mit dem Inversen von x. Also wird a / b mod m zu a multipliziert mit dem Inversen von b.

Das Inverse von x ist die Zahl, die beim Multiplizieren mit x unter dem Modulus 1 ergibt. Es übernimmt die Rolle von 1/x in der gewöhnlichen Arithmetik.

Ein Inverses existiert nur, wenn x keinen gemeinsamen Faktor mit m hat. Ein Primzahlmodul wie 1e9+7 garantiert, dass jedes von null verschiedene x ein Inverses besitzt.

Der kleine Satz von Fermat besagt, dass für eine Primzahl p x hoch p minus 1 kongruent zu 1 ist, solange x kein Vielfaches von p ist.

Wenn Sie einen Faktor x abspalten, muss der verbleibende Teil sein Inverses sein. Das Inverse von x ist also x hoch p minus 2, modulo p genommen.

Dieser Exponent ist riesig, verwenden Sie daher die schnelle Exponentiation aus der letzten Lektion. In Python erledigt ein einziger Aufruf von pow die gesamte Berechnung für Sie.

Um a geteilt durch b modulo zu berechnen, multiplizieren Sie a mit dem Inversen von b. Der Rest entspricht genau dem echten Quotienten modulo p.

Es gibt kein Inverses von 0, da keine Zahl multipliziert mit null 1 ergibt. Verhindern Sie die Division durch einen Wert, der unter dem Modulus zu null reduziert wird.

Jedes Inverse nach Fermat ist eine schnelle Potenzierung und benötigt daher O(log p) Zeit. Das ist für wenige Divisionen günstig, summiert sich aber bei Millionen von Berechnungen.

Wenn Sie viele Inverse benötigen, berechnen Sie sie in einem cleveren linearen Durchlauf vor, statt für jedes Element pow aufzurufen. Darauf werden Sie als Nächstes bei nCr zurückgreifen.

Sie dividieren unter einem Primzahlmodul nun, indem Sie mit dem modularen Inversen multiplizieren, das Sie mit pow als x hoch p minus 2 bestimmen. Invertieren Sie nur niemals null. ✅