Inverso modulare tramite Fermat

Addizione, sottrazione e moltiplicazione si comportano bene con un modulo, ma la semplice divisione no. Non è possibile dividere e poi applicare il resto. ⚠️

La soluzione è l'inverso modulare: dividere per x diventa moltiplicare per l'inverso di x. Quindi a / b mod m si trasforma in a moltiplicato per l'inverso di b.

L'inverso di x è il numero che, moltiplicato per x con il modulo applicato, dà 1. Svolge il ruolo di 1/x nell'aritmetica ordinaria.

Un inverso esiste solo quando x non condivide alcun fattore con m. Usare un modulo primo come 1e9+7 garantisce che ogni x diverso da zero abbia un inverso.

Il piccolo teorema di Fermat afferma che, per un primo p, x elevato alla potenza p meno 1 è congruo a 1, purché x non sia un multiplo di p.

Separando un fattore x, il resto deve essere il suo inverso. Quindi l'inverso di x è x elevato alla potenza p meno 2, calcolato modulo p.

Quell'esponente è enorme, quindi usi l'esponenziazione rapida della lezione precedente. In Python, una sola chiamata a pow esegue l'intera operazione.

Per calcolare a diviso b con il modulo, moltiplichi a per l'inverso di b. Il resto è esattamente il quoziente reale modulo p.

Non esiste l'inverso di 0, poiché nessun numero moltiplicato per zero dà uno. Eviti di dividere per un valore che si riduce a zero con il modulo.

Ogni inverso di Fermat richiede una potenza rapida, quindi ha un costo di O(log p). È conveniente per poche divisioni, ma il costo si accumula se ne esegue milioni.

Quando servono molti inversi, li precalcoli con un unico passaggio lineare ingegnoso invece di usare un pow per elemento. Questa tecnica servirà per nCr nella prossima lezione.

Quale potenza fornisce l'inverso modulare quando il modulo è primo?

Ora sa eseguire divisioni con un modulo primo moltiplicando per l'inverso modulare, ottenuto come x elevato alla potenza p meno 2 tramite pow. Non inverta mai zero. ✅