Modulær invers via Fermat

Addition, subtraktion og multiplikation fungerer fint modulo et tal, men almindelig division gør ikke. Du kan ikke bare dividere og tage resten. ⚠️

Løsningen er den modulære invers: division med x bliver til multiplikation med inversen af x. Så a / b modulo m bliver til a ganget med inversen af b.

Inversen af x er det tal, der giver 1, når det ganges med x modulo et tal. Den spiller rollen som 1/x i almindelig aritmetik.

En invers findes kun, når x ikke har nogen fælles faktor med m. Et primmodul som 1e9+7 garanterer, at alle x bortset fra 0 har en invers.

Fermats lille sætning siger, at for et primtal p er x opløftet til p minus 1 kongruent med 1, så længe x ikke er et multiplum af p.

Isolér én faktor x, så må resten være dens invers. Derfor er inversen af x x opløftet til p minus 2, taget modulo p.

Den eksponent er enorm, så brug den hurtige eksponentiering fra den forrige lektion. I Python klarer ét kald til pow hele arbejdet for dig.

For at beregne a divideret med b modulo et tal skal du gange a med inversen af b. Resultatet er nøjagtigt den sande kvotient modulo p.

Der findes ingen invers til 0, eftersom intet gange nul giver én. Kontrollér, at du ikke dividerer med en værdi, der bliver til nul modulo tallet.

Hver invers med Fermats metode er én hurtig potensberegning, så den tager O(log p) tid. Det er billigt ved nogle få divisioner, men løber op, hvis du udfører millioner.

Når du skal bruge mange inverser, kan du beregne dem på forhånd med et smart lineært gennemløb i stedet for én pow pr. element. Det får du brug for til nCr lige om lidt.

Du kan nu dividere modulo et primtal ved at gange med den modulære invers, som findes som x opløftet til p minus 2 med pow. Invertér bare aldrig nul. ✅