Publié · en amélioration
Algorithm
PGCD et PPCM, arithmétique modulaire et inverses, exponentiation rapide, crible d'Ératosthène et nCr mod p : la théorie des nombres pour l'algorithmique.
La théorie des nombres étudie les entiers, en particulier la divisibilité et les restes. En algorithmique, cela consiste à calculer le PGCD et le PPCM avec l'algorithme d'Euclide, à manipuler de très grandes valeurs grâce à l'arithmétique modulaire et à trouver des inverses modulaires avec l'algorithme d'Euclide étendu ou le petit théorème de Fermat. L'exponentiation rapide, le crible d'Ératosthène, la décomposition en facteurs premiers et les coefficients binomiaux modulo un nombre premier complètent la boîte à outils.
Ces outils reviennent sans cesse dans les entretiens techniques et les concours sous la forme « affichez la réponse modulo 10^9 + 7 ». En production, ils sont à la base de la cryptographie à clé publique comme RSA et Diffie-Hellman, des fonctions de hachage, des générateurs de nombres aléatoires et des chiffres de contrôle. La plupart s'exécutent en temps logarithmique ou quasi linéaire : les comprendre transforme des calculs qui ne finiraient jamais en opérations de quelques millisecondes.
Commencez par dérouler à la main les règles de l'arithmétique modulaire et l'algorithme d'Euclide, puis implémentez vous-même l'exponentiation rapide et le crible. Passez ensuite aux inverses modulaires et à nCr mod p. Si vous écrivez du C++ ou du Java, entraînez-vous à gérer les dépassements lors des multiplications et les restes négatifs. Apprenez aussi les fonctions standard comme pow(a, e, m) et math.gcd en Python.
Répéter pgcd(a, b) = pgcd(b, a mod b) donne le PGCD en O(log n) ; la version étendue renvoie aussi les coefficients de ax + by = pgcd(a, b).
L'addition, la soustraction et la multiplication conservent les restes, on réduit donc après chaque étape ; la division devient une multiplication par un inverse modulaire.
En élevant la base au carré selon les bits de l'exposant, on calcule a^e mod m avec environ log e multiplications au lieu de e.
Barrer les multiples de chaque nombre premier à partir de i × i trouve tous les premiers jusqu'à n en O(n log log n) ; une table du plus petit facteur premier permet ensuite de factoriser vite.
gcd calcule le plus grand commun diviseur avec l'algorithme d'Euclide, et le PPCM s'en déduit par a // gcd(a, b) * b. mod_pow est l'exponentiation rapide : elle parcourt les bits de l'exposant en élevant au carré et en multipliant, et avec un module premier p, a^(p-2) donne l'inverse modulaire de a. sieve utilise le crible d'Ératosthène pour lister tous les nombres premiers jusqu'à 30. Enregistrez le fichier et lancez 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.pySix chapitres pour aller de l'installation aux notions essentielles de Mathématiques et théorie des nombres.
Posez vos questions, partagez votre expérience et échangez vos avis sur Mathématiques et théorie des nombres.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.