Modulär invers via Fermat

Addition, subtraktion och multiplikation fungerar bra med en modul, men vanlig division gör det inte. Du kan inte bara dividera och sedan ta resten. ⚠️

Lösningen är den modulära inversen: division med x blir multiplikation med inversen till x. Alltså blir a / b modulo m lika med a multiplicerat med inversen till b.

Inversen till x är det tal som ger 1 när det multipliceras med x modulo modulen. Den spelar rollen av 1/x i vanlig aritmetik.

En invers finns bara när x och m saknar gemensamma faktorer. En primtalsmodul som 1e9+7 garanterar att varje x som inte är noll har en invers.

Fermats lilla sats säger att x upphöjt till p minus 1 är kongruent med 1 för ett primtal p, så länge x inte är en multipel av p.

Bryt ut en faktor x, så måste resten vara dess invers. Alltså är inversen till x x upphöjt till p minus 2, taget modulo p.

Den exponenten är enorm, så använd den snabba exponentiering från förra lektionen. I Python gör ett enda anrop till pow hela jobbet åt Dig.

För att beräkna a dividerat med b modulo modulen multiplicerar Du a med inversen till b. Resten är exakt den riktiga kvoten modulo p.

Det finns ingen invers till 0, eftersom inget gånger noll blir ett. Kontrollera att Du inte dividerar med ett värde som blir noll modulo modulen.

Varje invers med Fermats sats är en snabb exponentiering och kostar därför O(log p) tid. Det är billigt för några få divisioner, men kostnaden växer om Du gör miljontals.

När Du behöver många inverser kan Du förberäkna dem med en smart linjär genomgång i stället för att använda pow för varje element. Du kommer att behöva detta för nCr härnäst.

Du kan nu dividera modulo ett primtal genom att multiplicera med den modulära inversen, som beräknas som x upphöjt till p minus 2 med pow. Invertera bara aldrig noll. ✅