Modulær invers ved hjelp av Fermat

Addisjon, subtraksjon og multiplikasjon oppfører seg fint modulo en modul, men vanlig divisjon gjør ikke det. Du kan ikke bare dividere og ta resten. ⚠️

Løsningen er den modulære inversen: divisjon med x blir til multiplikasjon med inversen til x. Dermed blir a / b modulo m til a multiplisert med inversen til b.

Inversen til x er tallet som gir 1 når det multipliseres med x modulo modulen. Den spiller rollen til 1/x i vanlig aritmetikk.

En invers finnes bare når x ikke har noen felles faktor med m. En primtallsmodul som 1e9+7 garanterer at alle x som ikke er null, har en invers.

Fermats lille teorem sier at for et primtall p er x opphøyd i p − 1 kongruent med 1, så lenge x ikke er et multiplum av p.

Skill ut én faktor x, så må resten være inversen til x. Derfor er inversen til x x opphøyd i p − 2, tatt modulo p.

Denne eksponenten er enorm, så bruk rask eksponentiering fra forrige leksjon. I Python gjør ett kall til pow hele jobben for deg.

For å beregne a delt på b modulo multipliserer du a med inversen til b. Resten er nøyaktig den sanne kvotienten modulo p.

Det finnes ingen invers til 0, siden ingenting multiplisert med null blir én. Pass på at du ikke dividerer med en verdi som blir null modulo modulen.

Hver invers ved Fermats metode er én rask eksponentiering, så den bruker O(log p)-tid. Det er billig for noen få divisjoner, men blir mye hvis du gjør millioner av dem.

Når du trenger mange inverser, kan du forhåndsberegne dem med ett smart lineært gjennomløp i stedet for å kalle pow for hvert element. Du får bruk for dette i nCr snart.

Du kan nå dividere modulo et primtall ved å multiplisere med den modulære inversen, som finnes som x opphøyd i p − 2 ved hjelp av pow. Inverter bare aldri null. ✅