Résidus quadratiques
Source sur la loi de réciprocité quadratique et le symbole de Legendre :
In [277]:
Copied!
def decomposition_premiers(n : int) -> list:
"""Décompose l'entier n en facteurs premiers
"""
d = 2
decomposition = []
if n < 0:
decomposition.append((-1,1))
n = -n
while n > 1:
while n % d != 0:
d += 1
multiplicite = 0
while n % d == 0:
multiplicite += 1
n = n // d
decomposition.append((d, multiplicite))
return decomposition
def signe_reciprocite_quadratique(p, q):
"""Renvoie le signe du coefficient de changement de signe
(-1) ** ((p-1) // 2 * (q - 1)//2) dans la loi de réciprocité quadratique"""
if (p - 1) * (q - 1) % 8 == 0:
return 1
else:
return -1
def symbole_legendre(p, q, debug = False):
"""Renvoie le symbole de Legendre de p par rapport à q
0 (cas trivial) si q divise p
1 si p possède un résidu quadratique modulo q
-1 si p ne possède pas de résidu quadratique modulo q
"""
memo = dict() #dictionnaire de memoization des symboles de Legendre déjà calculés
compteur_appels = 0
def auxiliaire(p, q):
nonlocal compteur_appels
if debug:
print(f"Symbole de Legendre (p|q) avec p={p}, q={q}, décomposition en facteurs premiers de {p} : {decomposition_premiers(p)}")
compteur_appels += 1
if p % q == 0:
return 0
if (p, q) in memo:
return memo[(p,q)]
if p == 1:
memo[(p,q)] = 1
elif p == -1:
if q % 4 == 1:
memo[(p,q)] = 1
else:
memo[(p,q)] = -1
elif p == 2:
if q % 8 in [1, 7]:
memo[(p,q)] = 1
else:
memo[(p,q)] = -1
else:
symbole = 1
for (facteur_premier, multiplicite) in decomposition_premiers(p):
if multiplicite % 2 == 1:
if facteur_premier == 2:
symbole = symbole * auxiliaire(2, q)
else: #la loi de réciprocité quadratique ne s'applique qu'avec p et q pairs
signe = signe_reciprocite_quadratique(facteur_premier, q)
symbole = symbole * auxiliaire(q % facteur_premier, facteur_premier) * signe
memo[(p, q)] = symbole
return memo[(p, q)]
calcul = auxiliaire(p, q)
if debug:
print(f"Calcul en {compteur_appels} appels")
return calcul
def decomposition_premiers(n : int) -> list:
"""Décompose l'entier n en facteurs premiers
"""
d = 2
decomposition = []
if n < 0:
decomposition.append((-1,1))
n = -n
while n > 1:
while n % d != 0:
d += 1
multiplicite = 0
while n % d == 0:
multiplicite += 1
n = n // d
decomposition.append((d, multiplicite))
return decomposition
def signe_reciprocite_quadratique(p, q):
"""Renvoie le signe du coefficient de changement de signe
(-1) ** ((p-1) // 2 * (q - 1)//2) dans la loi de réciprocité quadratique"""
if (p - 1) * (q - 1) % 8 == 0:
return 1
else:
return -1
def symbole_legendre(p, q, debug = False):
"""Renvoie le symbole de Legendre de p par rapport à q
0 (cas trivial) si q divise p
1 si p possède un résidu quadratique modulo q
-1 si p ne possède pas de résidu quadratique modulo q
"""
memo = dict() #dictionnaire de memoization des symboles de Legendre déjà calculés
compteur_appels = 0
def auxiliaire(p, q):
nonlocal compteur_appels
if debug:
print(f"Symbole de Legendre (p|q) avec p={p}, q={q}, décomposition en facteurs premiers de {p} : {decomposition_premiers(p)}")
compteur_appels += 1
if p % q == 0:
return 0
if (p, q) in memo:
return memo[(p,q)]
if p == 1:
memo[(p,q)] = 1
elif p == -1:
if q % 4 == 1:
memo[(p,q)] = 1
else:
memo[(p,q)] = -1
elif p == 2:
if q % 8 in [1, 7]:
memo[(p,q)] = 1
else:
memo[(p,q)] = -1
else:
symbole = 1
for (facteur_premier, multiplicite) in decomposition_premiers(p):
if multiplicite % 2 == 1:
if facteur_premier == 2:
symbole = symbole * auxiliaire(2, q)
else: #la loi de réciprocité quadratique ne s'applique qu'avec p et q pairs
signe = signe_reciprocite_quadratique(facteur_premier, q)
symbole = symbole * auxiliaire(q % facteur_premier, facteur_premier) * signe
memo[(p, q)] = symbole
return memo[(p, q)]
calcul = auxiliaire(p, q)
if debug:
print(f"Calcul en {compteur_appels} appels")
return calcul
In [278]:
Copied!
def resolution_residu_quadratique(p, q, debug = False):
"""Renvoie une liste (x, y) de solutions de l'équation q * x + p = y ** 2
liste vide si p n'est pas un résidu quadratique modulo q"""
#premier cas : pas de solution
if symbole_legendre(p,q) == -1:
return []
#second cas
else:
#recherche des deux solutions avec 0 <= y < q par balayage
p = p % q
y = 0
carre_y = y ** 2
while carre_y % q != p:
y += 1
carre_y = (y ** 2) % q
solution = [((carre_y - p) // q, y), (((q - y) ** 2 - p) // q, q - y)]
if debug:
for (x, y) in solution:
print(f"{q} * {x} + {p} = {y} ** 2 = > {q * x + p == y ** 2}")
return solution
def resolution_residu_quadratique(p, q, debug = False):
"""Renvoie une liste (x, y) de solutions de l'équation q * x + p = y ** 2
liste vide si p n'est pas un résidu quadratique modulo q"""
#premier cas : pas de solution
if symbole_legendre(p,q) == -1:
return []
#second cas
else:
#recherche des deux solutions avec 0 <= y < q par balayage
p = p % q
y = 0
carre_y = y ** 2
while carre_y % q != p:
y += 1
carre_y = (y ** 2) % q
solution = [((carre_y - p) // q, y), (((q - y) ** 2 - p) // q, q - y)]
if debug:
for (x, y) in solution:
print(f"{q} * {x} + {p} = {y} ** 2 = > {q * x + p == y ** 2}")
return solution
In [279]:
Copied!
symbole_legendre(78,2, debug = True) #cas trivial
symbole_legendre(78,2, debug = True) #cas trivial
Symbole de Legendre (p|q) avec p=78, q=2, décomposition en facteurs premiers de 78 : [(2, 1), (3, 1), (13, 1)] Calcul en 1 appels
Out[279]:
0
In [280]:
Copied!
symbole_legendre(2,103, debug = True)
symbole_legendre(2,103, debug = True)
Symbole de Legendre (p|q) avec p=2, q=103, décomposition en facteurs premiers de 2 : [(2, 1)] Calcul en 1 appels
Out[280]:
1
In [281]:
Copied!
symbole_legendre(2,103, debug = True)
symbole_legendre(2,103, debug = True)
Symbole de Legendre (p|q) avec p=2, q=103, décomposition en facteurs premiers de 2 : [(2, 1)] Calcul en 1 appels
Out[281]:
1
In [282]:
Copied!
symbole_legendre(3, 103 , debug = True)
symbole_legendre(3, 103 , debug = True)
Symbole de Legendre (p|q) avec p=3, q=103, décomposition en facteurs premiers de 3 : [(3, 1)] Symbole de Legendre (p|q) avec p=1, q=3, décomposition en facteurs premiers de 1 : [] Calcul en 2 appels
Out[282]:
-1
In [283]:
Copied!
symbole_legendre(12, 103 , debug = True)
symbole_legendre(12, 103 , debug = True)
Symbole de Legendre (p|q) avec p=12, q=103, décomposition en facteurs premiers de 12 : [(2, 2), (3, 1)] Symbole de Legendre (p|q) avec p=1, q=3, décomposition en facteurs premiers de 1 : [] Calcul en 2 appels
Out[283]:
-1
In [284]:
Copied!
symbole_legendre(3, 13 , debug = True)
symbole_legendre(3, 13 , debug = True)
Symbole de Legendre (p|q) avec p=3, q=13, décomposition en facteurs premiers de 3 : [(3, 1)] Symbole de Legendre (p|q) avec p=1, q=3, décomposition en facteurs premiers de 1 : [] Calcul en 2 appels
Out[284]:
1
In [285]:
Copied!
symbole_legendre(78,103, debug = True)
symbole_legendre(78,103, debug = True)
Symbole de Legendre (p|q) avec p=78, q=103, décomposition en facteurs premiers de 78 : [(2, 1), (3, 1), (13, 1)] Symbole de Legendre (p|q) avec p=2, q=103, décomposition en facteurs premiers de 2 : [(2, 1)] Symbole de Legendre (p|q) avec p=1, q=3, décomposition en facteurs premiers de 1 : [] Symbole de Legendre (p|q) avec p=12, q=13, décomposition en facteurs premiers de 12 : [(2, 2), (3, 1)] Symbole de Legendre (p|q) avec p=1, q=3, décomposition en facteurs premiers de 1 : [] Calcul en 5 appels
Out[285]:
-1
In [286]:
Copied!
resolution_residu_quadratique(78, 103, debug = True)
resolution_residu_quadratique(78, 103, debug = True)
Out[286]:
[]
In [287]:
Copied!
symbole_legendre(11,89, debug = True)
symbole_legendre(11,89, debug = True)
Symbole de Legendre (p|q) avec p=11, q=89, décomposition en facteurs premiers de 11 : [(11, 1)] Symbole de Legendre (p|q) avec p=1, q=11, décomposition en facteurs premiers de 1 : [] Calcul en 2 appels
Out[287]:
1
In [288]:
Copied!
resolution_residu_quadratique(11, 89, debug = True)
resolution_residu_quadratique(11, 89, debug = True)
89 * 0 + 11 = 10 ** 2 = > False 89 * 70 + 11 = 79 ** 2 = > True
Out[288]:
[(0, 10), (70, 79)]
In [289]:
Copied!
symbole_legendre(713,1009, True)
symbole_legendre(713,1009, True)
Symbole de Legendre (p|q) avec p=713, q=1009, décomposition en facteurs premiers de 713 : [(23, 1), (31, 1)] Symbole de Legendre (p|q) avec p=20, q=23, décomposition en facteurs premiers de 20 : [(2, 2), (5, 1)] Symbole de Legendre (p|q) avec p=3, q=5, décomposition en facteurs premiers de 3 : [(3, 1)] Symbole de Legendre (p|q) avec p=2, q=3, décomposition en facteurs premiers de 2 : [(2, 1)] Symbole de Legendre (p|q) avec p=17, q=31, décomposition en facteurs premiers de 17 : [(17, 1)] Symbole de Legendre (p|q) avec p=14, q=17, décomposition en facteurs premiers de 14 : [(2, 1), (7, 1)] Symbole de Legendre (p|q) avec p=2, q=17, décomposition en facteurs premiers de 2 : [(2, 1)] Symbole de Legendre (p|q) avec p=3, q=7, décomposition en facteurs premiers de 3 : [(3, 1)] Symbole de Legendre (p|q) avec p=1, q=3, décomposition en facteurs premiers de 1 : [] Calcul en 9 appels
Out[289]:
1
In [290]:
Copied!
resolution_residu_quadratique(713, 1009, debug = True)
resolution_residu_quadratique(713, 1009, debug = True)
1009 * 0 + 713 = 210 ** 2 = > False 1009 * 632 + 713 = 799 ** 2 = > True
Out[290]:
[(0, 210), (632, 799)]
In [291]:
Copied!
symbole_legendre(3,5, True)
symbole_legendre(3,5, True)
Symbole de Legendre (p|q) avec p=3, q=5, décomposition en facteurs premiers de 3 : [(3, 1)] Symbole de Legendre (p|q) avec p=2, q=3, décomposition en facteurs premiers de 2 : [(2, 1)] Calcul en 2 appels
Out[291]:
-1
In [292]:
Copied!
resolution_residu_quadratique(3, 5, debug = True)
resolution_residu_quadratique(3, 5, debug = True)
Out[292]:
[]
In [293]:
Copied!
symbole_legendre(17,31, True)
symbole_legendre(17,31, True)
Symbole de Legendre (p|q) avec p=17, q=31, décomposition en facteurs premiers de 17 : [(17, 1)] Symbole de Legendre (p|q) avec p=14, q=17, décomposition en facteurs premiers de 14 : [(2, 1), (7, 1)] Symbole de Legendre (p|q) avec p=2, q=17, décomposition en facteurs premiers de 2 : [(2, 1)] Symbole de Legendre (p|q) avec p=3, q=7, décomposition en facteurs premiers de 3 : [(3, 1)] Symbole de Legendre (p|q) avec p=1, q=3, décomposition en facteurs premiers de 1 : [] Calcul en 5 appels
Out[293]:
-1
In [294]:
Copied!
resolution_residu_quadratique(17, 31, debug = True)
resolution_residu_quadratique(17, 31, debug = True)
Out[294]:
[]
In [295]:
Copied!
symbole_legendre(5984,7907, True)
symbole_legendre(5984,7907, True)
Symbole de Legendre (p|q) avec p=5984, q=7907, décomposition en facteurs premiers de 5984 : [(2, 5), (11, 1), (17, 1)] Symbole de Legendre (p|q) avec p=2, q=7907, décomposition en facteurs premiers de 2 : [(2, 1)] Symbole de Legendre (p|q) avec p=9, q=11, décomposition en facteurs premiers de 9 : [(3, 2)] Symbole de Legendre (p|q) avec p=2, q=17, décomposition en facteurs premiers de 2 : [(2, 1)] Calcul en 4 appels
Out[295]:
1
In [296]:
Copied!
resolution_residu_quadratique(5984,7907, debug = True)
resolution_residu_quadratique(5984,7907, debug = True)
7907 * 0 + 5984 = 364 ** 2 = > False 7907 * 7195 + 5984 = 7543 ** 2 = > True
Out[296]:
[(0, 364), (7195, 7543)]
In [297]:
Copied!
symbole_legendre(6988,7907, True)
symbole_legendre(6988,7907, True)
Symbole de Legendre (p|q) avec p=6988, q=7907, décomposition en facteurs premiers de 6988 : [(2, 2), (1747, 1)] Symbole de Legendre (p|q) avec p=919, q=1747, décomposition en facteurs premiers de 919 : [(919, 1)] Symbole de Legendre (p|q) avec p=828, q=919, décomposition en facteurs premiers de 828 : [(2, 2), (3, 2), (23, 1)] Symbole de Legendre (p|q) avec p=22, q=23, décomposition en facteurs premiers de 22 : [(2, 1), (11, 1)] Symbole de Legendre (p|q) avec p=2, q=23, décomposition en facteurs premiers de 2 : [(2, 1)] Symbole de Legendre (p|q) avec p=1, q=11, décomposition en facteurs premiers de 1 : [] Calcul en 6 appels
Out[297]:
1
In [298]:
Copied!
resolution_residu_quadratique(6988,7907, debug = True)
resolution_residu_quadratique(6988,7907, debug = True)
7907 * 0 + 6988 = 3408 ** 2 = > False 7907 * 2559 + 6988 = 4499 ** 2 = > True
Out[298]:
[(0, 3408), (2559, 4499)]
In [299]:
Copied!
symbole_legendre(-1, 5, True)
symbole_legendre(-1, 5, True)
Symbole de Legendre (p|q) avec p=-1, q=5, décomposition en facteurs premiers de -1 : [(-1, 1)] Calcul en 1 appels
Out[299]:
1
In [300]:
Copied!
resolution_residu_quadratique(-1, 5, debug = True)
resolution_residu_quadratique(-1, 5, debug = True)
5 * 0 + 4 = 2 ** 2 = > True 5 * 1 + 4 = 3 ** 2 = > True
Out[300]:
[(0, 2), (1, 3)]
In [301]:
Copied!
symbole_legendre(-1, 7, True)
symbole_legendre(-1, 7, True)
Symbole de Legendre (p|q) avec p=-1, q=7, décomposition en facteurs premiers de -1 : [(-1, 1)] Calcul en 1 appels
Out[301]:
-1
In [302]:
Copied!
resolution_residu_quadratique(-1, 7, debug = True)
resolution_residu_quadratique(-1, 7, debug = True)
Out[302]:
[]
In [303]:
Copied!
symbole_legendre(2, 7, True)
symbole_legendre(2, 7, True)
Symbole de Legendre (p|q) avec p=2, q=7, décomposition en facteurs premiers de 2 : [(2, 1)] Calcul en 1 appels
Out[303]:
1
In [304]:
Copied!
resolution_residu_quadratique(2, 7, debug = True)
resolution_residu_quadratique(2, 7, debug = True)
7 * 0 + 2 = 3 ** 2 = > False 7 * 2 + 2 = 4 ** 2 = > True
Out[304]:
[(0, 3), (2, 4)]
In [305]:
Copied!
symbole_legendre(2, 17, True)
symbole_legendre(2, 17, True)
Symbole de Legendre (p|q) avec p=2, q=17, décomposition en facteurs premiers de 2 : [(2, 1)] Calcul en 1 appels
Out[305]:
1
In [306]:
Copied!
resolution_residu_quadratique(2, 17, debug = True)
resolution_residu_quadratique(2, 17, debug = True)
17 * 0 + 2 = 6 ** 2 = > False 17 * 7 + 2 = 11 ** 2 = > True
Out[306]:
[(0, 6), (7, 11)]