Rilasciato · in miglioramento
Algorithm
MCD e mcm, aritmetica modulare e inversi, esponenziazione rapida, crivello di Eratostene e nCr mod p: la teoria dei numeri per gli algoritmi.
La teoria dei numeri studia gli interi, in particolare la divisibilità e i resti. Negli algoritmi significa calcolare MCD e mcm con l'algoritmo di Euclide, gestire valori enormi con l'aritmetica modulare e trovare inversi modulari con l'algoritmo di Euclide esteso o il piccolo teorema di Fermat. L'esponenziazione rapida, il crivello di Eratostene, la fattorizzazione in primi e i coefficienti binomiali modulo un primo completano la cassetta degli attrezzi.
Questi strumenti compaiono di continuo nei colloqui tecnici e nelle gare di programmazione come «stampa la risposta modulo 10^9 + 7», e in produzione sono alla base della crittografia a chiave pubblica come RSA e Diffie-Hellman, delle funzioni hash, dei generatori di numeri casuali e delle cifre di controllo. Quasi tutti girano in tempo logaritmico o quasi lineare, quindi capirli trasforma calcoli che non finirebbero mai in operazioni da pochi millisecondi.
Inizia seguendo a mano le regole dell'aritmetica modulare e l'algoritmo di Euclide, poi implementa da solo l'esponenziazione rapida e il crivello. Passa quindi agli inversi modulari e a nCr mod p; se scrivi in C++ o Java, esercitati a gestire l'overflow nelle moltiplicazioni e i resti negativi. Impara anche le funzioni standard, come pow(a, e, m) e math.gcd di Python.
Ripetere mcd(a, b) = mcd(b, a mod b) dà l'MCD in O(log n); la versione estesa restituisce anche i coefficienti di ax + by = mcd(a, b).
Somma, sottrazione e moltiplicazione conservano i resti, quindi si riduce dopo ogni passo; la divisione diventa una moltiplicazione per un inverso modulare.
Elevando al quadrato la base lungo i bit dell'esponente si calcola a^e mod m con circa log e moltiplicazioni invece di e.
Cancellare i multipli di ogni primo a partire da i × i trova tutti i primi fino a n in O(n log log n); una tabella del minimo fattore primo permette poi di fattorizzare in fretta.
gcd calcola il massimo comune divisore con l'algoritmo di Euclide, e il minimo comune multiplo si ottiene come a // gcd(a, b) * b. mod_pow è l'esponenziazione rapida: scorre i bit dell'esponente elevando al quadrato e moltiplicando, e con un modulo primo p, a^(p-2) dà l'inverso modulare di a. sieve usa il crivello di Eratostene per elencare tutti i primi fino a 30. Salva il file ed esegui python number_theory.py.
number_theory.py
import math
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a
def mod_pow(base: int, exp: int, mod: int) -> int:
result, base = 1 % mod, base % mod
while exp > 0:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
def sieve(n: int) -> list[int]:
is_prime = [False, False] + [True] * (n - 1)
for i in range(2, math.isqrt(n) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i, p in enumerate(is_prime) if p]
MOD = 10**9 + 7
print(gcd(84, 36), 84 // gcd(84, 36) * 36) # 12 252
print(mod_pow(3, 200, 13)) # 9
print(mod_pow(3, MOD - 2, MOD)) # 333333336, the inverse of 3
print(sieve(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
python number_theory.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Matematica e teoria dei numeri.
Fai domande, condividi la tua esperienza e scambia opinioni su Matematica e teoria dei numeri.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.