13 - Loi de reciprocité quadratique II : symbole de Jacobi et symbole de Kronecker

A Course in Arithmetic, chapitre 3 (Serre, GTM 7). Le carnet 11 a presente le caractere de Legendre \((d/p)\) pour \(p\) premier, et esquissee le symbole de Kronecker \((d/n)\) pour \(n\) impair quelconque (par multiplicativite sur les facteurs premiers). Ce carnet approfondit ces deux symboles en unifiant leur traitement : le symbole de Jacobi \((d/n)\) est defini pour \(n\) impair et reproduit la loi de reciprocite quadratique par un algorithme rapide en \(O(\log n)\) multiplications modulaires (algorithme d’Euler-Legendre). Le symbole de Kronecker \((d/n)\) etend Jacobi a \(n\) quelconque, y compris \(n\) pair, et permet de calculer le conducteur d’un corps quadratique - un invariant central en theorie analytique des nombres (Dirichlet, Kronecker, Weber). Outils : Python stdlib pur (math.isqrt). Le carnet 11 a pose la reciprocite quadratique et le symbole de Kronecker en fin de parcours ; ce 13 reprend le flambeau et l’etend.

Plan

Symbole de Jacobi \((d/n)\) pour \(n\) impair - definition, proprietes multiplicatives
Algorithme d’Euler-Legendre : reciprocite quadratique en \(O(\log n)\)
Symbole de Kronecker \((d/n)\) pour \(n\) quelconque - extension aux paires
Conducteur d’un corps quadratique et table des petits discriminants
Exercices

1. Symbole de Jacobi

Pour \(d \in \mathbb{Z}\) et \(n \in \mathbb{N}\) impair avec \(\gcd(d, n) = 1\), le symbole de Jacobi \((d/n)\) est defini par \[(d/n) = \prod_{p \mid n} \left(\frac{d}{p}\right)^{v_p(n)},\] ou \(\left(\frac{d}{p}\right)\) est le caractere de Legendre (carnet 11). Le symbole de Jacobi partage trois regles fondamentales : - Multiplicativite en \(d\) : \((d_1 d_2 / n) = (d_1/n)(d_2/n)\). - Multiplicativite en \(n\) : \((d/n_1 n_2) = (d/n_1)(d/n_2)\). - Reciprocite quadratique : pour \(d, n\) impairs positifs, \(\left(\frac{d}{n}\right) = \left(\frac{n}{d}\right) (-1)^{\frac{(d-1)(n-1)}{4}}\). Caveat : \((d/n) = -1\) n’implique pas que \(d\) n’est pas un carre modulo \(n\) quand \(n\) est compose. Le symbole de Jacobi est donc un test rapide mais non definitif de residu quadraticite. Pour la residu quadraticite exacte modulo \(n\), voir l’algorithme de Cipolla (ordre Carnet).

from math import isqrt, gcd

def jacobi_symbol(d, n):
    if n <= 0 or n % 2 == 0:
        raise ValueError(f'n doit etre > 0 et impair (n = {n})')
    d = d % n
    if d == 0:
        return 0
    out = 1
    while True:
        if d == 0:
            return 0
        if d == 1:
            return out
        e = 0
        while d % 2 == 0:
            d //= 2
            e += 1
        if e > 0:
            # (2/n) = (-1)^((n^2-1)/8) : -1 pour n = 3, 5 (mod 8), +1 pour 1, 7.
            # Le facteur (2/n) s'applique e fois (e facteurs 2 extraits de d).
            n_mod_8 = n % 8
            if n_mod_8 in (3, 5):
                out *= (-1) ** e
        if d == 1:
            return out
        d, n = n, d
        if (d - 1) * (n - 1) // 4 % 2 == 1:
            out = -out
        d = d % n
        if d == 0:
            return 0

# Tests : reciprocite quadratique et valeurs numeriques
print('Symbole de Jacobi : verification de la loi de reciprocite')
print()
pairs = [(3, 5), (5, 13), (7, 11), (3, 7), (5, 7), (7, 13), (11, 13), (3, 11), (5, 11)]
print(f"{'d':>3} | {'n':>3} | {'(d/n)':>5} | {'(n/d)':>5} | sign reciprocity | (-1)^((d-1)(n-1)/4)")
print('-' * 70)
for d, n in pairs:
    jac_d_n = jacobi_symbol(d, n)
    jac_n_d = jacobi_symbol(n, d)
    recip_sign = 1 if jac_d_n == jac_n_d else -1
    theory_sign = -1 if ((d - 1) * (n - 1) // 4) % 2 == 1 else 1
    ok = recip_sign == theory_sign
    print(f'{d:>3} | {n:>3} | {jac_d_n:>5} | {jac_n_d:>5} | {recip_sign:>16} | {theory_sign:>20} {"OK" if ok else "KO"}')

Symbole de Jacobi : verification de la loi de reciprocite

  d |   n | (d/n) | (n/d) | sign reciprocity | (-1)^((d-1)(n-1)/4)
----------------------------------------------------------------------
  3 |   5 |    -1 |    -1 |                1 |                    1 OK
  5 |  13 |    -1 |    -1 |                1 |                    1 OK
  7 |  11 |    -1 |     1 |               -1 |                   -1 OK
  3 |   7 |    -1 |     1 |               -1 |                   -1 OK
  5 |   7 |    -1 |    -1 |                1 |                    1 OK
  7 |  13 |    -1 |    -1 |                1 |                    1 OK
 11 |  13 |    -1 |    -1 |                1 |                    1 OK
  3 |  11 |     1 |    -1 |               -1 |                   -1 OK
  5 |  11 |     1 |     1 |                1 |                    1 OK

Lecture du resultat

Sur les 9 paires impaires \((d, n)\) testees : - La loi de reciprocite est verifiee a chaque ligne : \((d/n) \cdot (-1)^{\frac{(d-1)(n-1)}{4}} = (n/d)\) - c’est le signe relatif qui est controle ici ; la branche paire \((2/n)\) de l’algorithme est exercee et verifiee separement a l’exercice 2. - L’algorithme est en \(O(\log n)\) multiplications modulaires - il s’arrete en quelques iterations meme pour \(n > 10^6\). Le symbole de Jacobi n’est pas un Legendre : pour \(n\) compose, \((d/n) = -1\) ne prouve pas que \(d\) n’est pas un carre modulo \(n\). C’est un test rapide mais non definitif de residu quadraticite. Pour le test exact, voir Cipolla (carnet a venir).

2. Algorithme d’Euler-Legendre - complexite

L’algorithme d’Euler-Legendre pour le symbole de Jacobi a une structure recursive : 1. Reduction modulo power \(n\) : \((d/n) = (d \bmod n / n)\). Le symbole est invariant modulo \(n\). 2. Extraction des puissances de 2 dans \(d\) : \((2/n) = (-1)^{\frac{n^2-1}{8}}\), qui vaut \(+1\) pour \(n \equiv \pm 1 \pmod 8\) et \(-1\) pour \(n \equiv \pm 3 \pmod 8\). 3. Reciprocite : si \(d\) et \(n\) sont impairs, on swap \((d/n) = (n/d) (-1)^{\frac{(d-1)(n-1)}{4}}\). La complexite est dominee par les swaps modulo \(n\) successifs, ce qui donne \(O(\log n)\) multiplications modulaires (l’algorithme ressemble a l’Euclide etendu). Pour \(n < 10^9\), l’algorithme s’execute en moins de 100 iterations.

import time

def jacobi_with_count(d, n):
    if n <= 0 or n % 2 == 0:
        raise ValueError
    d = d % n
    if d == 0:
        return 0, 0
    out = 1
    iters = 0
    while True:
        iters += 1
        if d == 0:
            return 0, iters
        if d == 1:
            return out, iters
        e = 0
        while d % 2 == 0:
            d //= 2
            e += 1
        if e > 0:
            # (2/n) : -1 pour n = 3, 5 (mod 8) ; facteur applique e fois.
            n_mod_8 = n % 8
            if n_mod_8 in (3, 5):
                out *= (-1) ** e
        if d == 1:
            return out, iters
        d, n = n, d
        if (d - 1) * (n - 1) // 4 % 2 == 1:
            out = -out
        d = d % n
        if d == 0:
            return 0, iters

# Pire cas de l'algorithme d'Euclide : paires de Fibonacci consecutives
# (quotient 1 a chaque etape de la descente). F(k) est pair si k = 0 mod 3,
# donc k != 0 mod 3 garde n impair pour le symbole de Jacobi.
def fib_pair(k):
    a, b = 0, 1
    for _ in range(k - 1):
        a, b = b, a + b
    return b, a  # (F(k), F(k-1))

print('Complexite de jacobi_symbol : iterations vs taille de n (pire cas Fibonacci)')
print()
for k in [11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41]:
    n, d = fib_pair(k)
    t0 = time.perf_counter()
    sym, iters = jacobi_with_count(d, n)
    elapsed = (time.perf_counter() - t0) * 1e6
    print(f'k = {k:>3} : n = F(k) a {n.bit_length():>3} bits : iters = {iters:>3}, elapsed = {elapsed:>8.2f} us')

Complexite de jacobi_symbol : iterations vs taille de n (pire cas Fibonacci)

k =  11 : n = F(k) a   7 bits : iters =   3, elapsed =     3.90 us
k =  14 : n = F(k) a   9 bits : iters =   3, elapsed =     2.60 us
k =  17 : n = F(k) a  11 bits : iters =   4, elapsed =     3.20 us
k =  20 : n = F(k) a  13 bits : iters =   5, elapsed =     2.50 us
k =  23 : n = F(k) a  15 bits : iters =   6, elapsed =     2.20 us
k =  26 : n = F(k) a  17 bits : iters =   6, elapsed =     3.20 us
k =  29 : n = F(k) a  19 bits : iters =   7, elapsed =     2.70 us
k =  32 : n = F(k) a  22 bits : iters =   8, elapsed =     2.90 us
k =  35 : n = F(k) a  24 bits : iters =   9, elapsed =     2.80 us
k =  38 : n = F(k) a  26 bits : iters =  10, elapsed =     3.40 us
k =  41 : n = F(k) a  28 bits : iters =  11, elapsed =     3.30 us

Lecture du resultat

L’algorithme d’Euler-Legendre pour le symbole de Jacobi est rapide, meme sur son pire cas : - Le benchmark utilise des paires de Fibonacci consecutives, le pire cas de l’algorithme d’Euclide (quotient 1 a chaque etape) : le compteur passe de 3 iterations pour n sur 7 bits a 11 iterations pour n sur 28 bits - une croissance lineaire dans le nombre de bits de n, exactement le regime \(O(\log n)\) attendu. - Sur des paires generiques les quotients sont plus grands et le compteur est encore plus bas ; l’exercice 3 pousse la mesure jusqu’a \(n\) de 30 chiffres. C’est l’algorithme utilise par PARI/GP et Magma pour le symbole de Jacobi/Kronecker en pratique (au-dessus de GMP pour l’arithmetique).

3. Symbole de Kronecker - extension aux paires

Le symbole de Kronecker \((d/n)\) etend le symbole de Jacobi aux \(n\) quelconques (pairs ou impairs, positifs ou negatifs), via une decomposition : 1. Signe : \((d/n) = \text{sgn}(n)^{(d-1)/2} \cdot (d/|n|)\) - pour rendre le symbole defini pour \(n\) negatifs aussi. 2. Extraction a zero : \((d/0) = 0\) si \(d \neq \pm 1\), et \((1/0) = (\pm 1/0) = 1\) par convention. 3. Multiplicativite en \(n\) : \((d/n) = (d/2^{v_2(n)}) \cdot \prod_{p \mid n, p \text{ impair}} (d/p)^{v_p(n)}\). 4. Symbole en \(2\) : \((d/2)\) depends par modulo 8 - voir la table. Le symbole de Kronecker est l’outil canonique pour definir le caractere de Dirichlet quadratique \(\chi_D(n) = (D/n)\), qui sert a la loi de Dirichlet et au theoreme des nombres premiers en progression arithmetique.

def kronecker_symbol(d, n):
    if n == 0:
        if d == 1 or d == -1:
            return 1
        return 0
    if n == 1:
        return 1
    if n < 0:
        if d % 4 == 1:
            sign = 1
        elif d % 4 == 3:
            sign = -1
        else:
            if d % 4 == 0:
                return 0
            sign = 1
        return sign * kronecker_symbol(d, -n)
    out = 1
    e = 0
    while n % 2 == 0:
        n //= 2
        e += 1
    if e > 0:
        d_mod_8 = d % 8
        if d_mod_8 in (1, 7):
            k2 = 1
        elif d_mod_8 in (3, 5):
            k2 = -1
        else:
            k2 = 0
        if k2 == 0:
            return 0
        out *= k2 ** e
    if n == 1:
        return out
    d = d % n
    if d == 0:
        return 0
    while True:
        if d == 0:
            return 0
        if d == 1:
            return out
        e = 0
        while d % 2 == 0:
            d //= 2
            e += 1
        if e > 0:
            # (2/n) : -1 pour n = 3, 5 (mod 8) ; facteur applique e fois.
            n_mod_8 = n % 8
            if n_mod_8 in (3, 5):
                out *= (-1) ** e
        if d == 1:
            return out
        d, n = n, d
        if (d - 1) * (n - 1) // 4 % 2 == 1:
            out = -out
        d = d % n
        if d == 0:
            return 0

print('Symbole de Kronecker : cas degenere (d/2) selon d mod 8')
print()
for d in range(0, 16):
    print(f'd = {d:>2} (mod 8 = {d % 8}): (d/2) = {kronecker_symbol(d, 2)}')

Symbole de Kronecker : cas degenere (d/2) selon d mod 8

d =  0 (mod 8 = 0): (d/2) = 0
d =  1 (mod 8 = 1): (d/2) = 1
d =  2 (mod 8 = 2): (d/2) = 0
d =  3 (mod 8 = 3): (d/2) = -1
d =  4 (mod 8 = 4): (d/2) = 0
d =  5 (mod 8 = 5): (d/2) = -1
d =  6 (mod 8 = 6): (d/2) = 0
d =  7 (mod 8 = 7): (d/2) = 1
d =  8 (mod 8 = 0): (d/2) = 0
d =  9 (mod 8 = 1): (d/2) = 1
d = 10 (mod 8 = 2): (d/2) = 0
d = 11 (mod 8 = 3): (d/2) = -1
d = 12 (mod 8 = 4): (d/2) = 0
d = 13 (mod 8 = 5): (d/2) = -1
d = 14 (mod 8 = 6): (d/2) = 0
d = 15 (mod 8 = 7): (d/2) = 1

Lecture du resultat

Le symbole de Kronecker en \(n = 2\) depend de \(d \pmod 8\) : - \((d/2) = +1\) pour \(d \equiv 1, 7 \pmod 8\) (deux cas). - \((d/2) = -1\) pour \(d \equiv 3, 5 \pmod 8\) (deux cas). - \((d/2) = 0\) pour \(d \equiv 0, 2, 4, 6 \pmod 8\) (\(d\) pair, hors cas triviaux). C’est l’extension du caractere de Legendre en \(p = 2\) (Legendre lui-meme n’est defini que pour \(p\) premier impair). Le symbole de Kronecker est l’ingredient central du caractere de Dirichlet quadratique \(\chi_D(n) = (D/n)\). Le carnet 14 a venir approfondira la construction du caractere \(\chi_D\) et la formule analytique pour \(L(1, \chi_D)\).

4. Conducteur d’un corps quadratique

Soit \(K = \mathbb{Q}(\sqrt{d})\) avec \(d\) squarefree. Son discriminant est \(D = d\) si \(d \equiv 1 \pmod 4\), \(D = 4d\) sinon. Pour un discriminant fondamental \(D\), le conducteur du caractere de Kronecker \(\chi_D\) est simplement \[f_D = |D|.\] Le conducteur gouverne les premiers ramifies dans \(K\) : ce sont les \(p\) qui divisent \(f_D\). Pour les \(d = \{1, 2, 3, 7, 11, 19, 43, 67, 163\}\), les discriminants fondamentaux sont \(D = \{-4, -8, -3, -7, -11, -19, -43, -67, -163\}\), et les conducteurs sont \(f_D = |D| = \{4, 8, 3, 7, 11, 19, 43, 67, 163\}\). Le symbole de Kronecker \((D/n)\) est periodique de periode \(f_D\) - c’est l’invariant qui normalise la loi de Dirichlet.

def prime_factors(n):
    if n <= 1:
        return []
    out = []
    p = 2
    while p * p <= n and p < 100:
        if n % p == 0:
            out.append(p)
            while n % p == 0:
                n //= p
        p += 1
    if n > 1:
        out.append(n)
    return out

print('Conducteurs des 9 corps quadratiques de Heegner :')
print()
heegner_D = [-3, -4, -7, -8, -11, -19, -43, -67, -163]
print(f"{'D':>6} | {'f_D':>5} | {'premiers ramifies'}")
print('-' * 50)
# Les 9 Heegner sont des discriminants FONDAMENTAUX : pour un discriminant
# fondamental, le conducteur du caractere de Kronecker chi_D est |D| tout court
# (le case-split |D|/4 decrit la derivation de D depuis le radicande squarefree,
# pas le conducteur). Q(i) -> D = -4 -> f = 4 ; Q(sqrt(-2)) -> D = -8 -> f = 8.
for D in heegner_D:
    f_D = abs(D)
    primes_d = prime_factors(f_D)
    print(f'{D:>5} | {f_D:>5} | {primes_d}')

Conducteurs des 9 corps quadratiques de Heegner :

     D |   f_D | premiers ramifies
--------------------------------------------------
   -3 |     3 | [3]
   -4 |     4 | [2]
   -7 |     7 | [7]
   -8 |     8 | [2]
  -11 |    11 | [11]
  -19 |    19 | [19]
  -43 |    43 | [43]
  -67 |    67 | [67]
 -163 |   163 | [163]

Lecture du resultat

Les conducteurs des 9 corps quadratiques de Heegner valent \(f_D = |D|\) : \(\{4, 8, 3, 7, 11, 19, 43, 67, 163\}\). Tous sont premiers sauf \(4\) et \(8\) (puissances de \(2\)) : \(2\) ramifie dans \(Q(i)\) et \(Q(\sqrt{-2})\), ce que la colonne des premiers ramifies montre (\(\{2\}\) pour \(D = -4\) et \(D = -8\), un seul premier pour chaque \(|D|\) premier). Le conducteur est un invariant de Dirichlet : il parametre la famille de \(L\)-series associees au caractere \(\chi_D\) du Kronecker. La position de \(\chi_D\) dans la table des caracteres de Dirichlet quadratiques est determinee par \(f_D\) et la parite (caractere pair pour \(D > 0\), impair pour \(D < 0\)).

5. Exercices

Trois mesures qui poussent l’etude du symbole de Jacobi/Kronecker au-dela de la routine : Exercice 1 : Verifier que pour les 9 discriminants de Heegner et les 100 premiers \(p\), la moyenne \(\frac{1}{100} \sum_{p} (D/p)\) tend vers \(0\) - densite caracteristique de Chebotarev \(1/2\) dans les deux signes. Exercice 2 : Calculer le symbole de Jacobi \((2/n)\) pour \(n\) impair : combien valent \((2/n)\) pour \(n \in \{3, 5, 7, 9, 11, 13, 15, 17, 19\}\) ? Verifier contre la formule \((-1)^{\frac{n^2-1}{8}}\). Exercice 3 : Tester l’algorithme d’Euler-Legendre sur un \(n\) de 30 chiffres : combien d’iterations sont-elles necessaires ? La complexite reste-t-elle \(O(\log n)\) ?

def isprime_native(n):
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    for k in range(3, isqrt(n) + 1, 2):
        if n % k == 0:
            return False
    return True

print('Exo 1 : moyenne de (D/p) sur 100 premiers p pour D Heegner')
print()
primes_lt_1000 = [p for p in range(5, 1000) if isprime_native(p)][:100]
print(f'{len(primes_lt_1000)} premiers utilises, de {primes_lt_1000[0]} a {primes_lt_1000[-1]}')
print()
print(f"{'D':>6} | {'somme (D/p)':>13} | {'moyenne':>10}")
print('-' * 40)
for D in heegner_D:
    s = sum(kronecker_symbol(D, p) for p in primes_lt_1000)
    avg = s / len(primes_lt_1000)
    print(f'{D:>5} | {s:>13} | {avg:>10.3f}')

Exo 1 : moyenne de (D/p) sur 100 premiers p pour D Heegner

100 premiers utilises, de 5 a 557

     D |   somme (D/p) |    moyenne
----------------------------------------
   -3 |            -4 |     -0.040
   -4 |            -4 |     -0.040
   -7 |            -3 |     -0.030
   -8 |            -6 |     -0.060
  -11 |            -5 |     -0.050
  -19 |            -1 |     -0.010
  -43 |             5 |      0.050
  -67 |             7 |      0.070
 -163 |           -17 |     -0.170

print('Exo 2 : (2/n) vs formule (-1)^((n^2-1)/8)')
print()
for n in [3, 5, 7, 9, 11, 13, 15, 17, 19]:
    sym = kronecker_symbol(2, n)
    theory = (-1) ** ((n * n - 1) // 8)
    ok = sym == theory
    print(f'n = {n:>2}: (2/n) = {sym:>2}, formule = {theory:>2}, OK = {ok}')

Exo 2 : (2/n) vs formule (-1)^((n^2-1)/8)

n =  3: (2/n) = -1, formule = -1, OK = True
n =  5: (2/n) = -1, formule = -1, OK = True
n =  7: (2/n) =  1, formule =  1, OK = True
n =  9: (2/n) =  1, formule =  1, OK = True
n = 11: (2/n) = -1, formule = -1, OK = True
n = 13: (2/n) = -1, formule = -1, OK = True
n = 15: (2/n) =  1, formule =  1, OK = True
n = 17: (2/n) =  1, formule =  1, OK = True
n = 19: (2/n) = -1, formule = -1, OK = True

print('Exo 3 : complexite pour n de 30 chiffres')
print()
n_big = 2**100 + 123456789
d = 2**100 - 987654321
t0 = time.perf_counter()
sym_big = kronecker_symbol(d, n_big)
elapsed = (time.perf_counter() - t0) * 1e6
print(f'n = {n_big} (30 chiffres), d = (30 chiffres)')
print(f'sym = {sym_big}, elapsed = {elapsed:.2f} us')

print()
print('Complexite vs log(n) (n de plus en plus grand) :')
for k in range(1, 100, 10):
    n = 2 ** k + 1
    d = 2 ** (k // 2) + 3
    t0 = time.perf_counter()
    sym, _ = jacobi_with_count(d, n)
    elapsed = (time.perf_counter() - t0) * 1e6
    print(f'k = {k:>3}, log2(n) = {k}, elapsed = {elapsed:>8.2f} us')

Exo 3 : complexite pour n de 30 chiffres

n = 1267650600228229401496826662165 (30 chiffres), d = (30 chiffres)
sym = 0, elapsed = 34.40 us

Complexite vs log(n) (n de plus en plus grand) :
k =   1, log2(n) = 1, elapsed =     1.40 us
k =  11, log2(n) = 11, elapsed =     2.60 us
k =  21, log2(n) = 21, elapsed =     1.80 us
k =  31, log2(n) = 31, elapsed =     2.00 us
k =  41, log2(n) = 41, elapsed =     1.70 us
k =  51, log2(n) = 51, elapsed =     1.30 us
k =  61, log2(n) = 61, elapsed =     2.60 us
k =  71, log2(n) = 71, elapsed =     2.00 us
k =  81, log2(n) = 81, elapsed =     1.30 us
k =  91, log2(n) = 91, elapsed =     1.40 us

Conclusion

Le symbole de Jacobi \((d/n)\) pour \(n\) impair et son extension Kronecker \((d/n)\) pour \(n\) quelconque sont les outils canoniques de l’arithmetique quadratique : - L’algorithme d’Euler-Legendre calcule \((d/n)\) en \(O(\log n)\) multiplications modulaires. - Le symbole de Kronecker est periodique modulo le conducteur \(f_D\) du corps quadratique \(\mathbb{Q}(\sqrt{D})\). Le conducteur est l’invariant qui parametre les caracteres de Dirichlet quadratiques, et gouverne la position de \(\chi_D\) dans la table des caracteres. Le carnet 11 (celebrer le symbole de Kronecker en fin de parcours) avait clos ce theme ; ce carnet 13 le reprend et l’etend en passant du premier au caractere de cout asymptotique \(O(\log n)\). C’est le chemin de la reciprocite quadratique en Serre ch. 3.

Ressources

Serre, A Course in Arithmetic, chapitre 3 (Springer GTM 7) - la reference canonique.
Cohen, A Course in Computational Algebraic Number Theory (Springer GTM 138), vol. I ch. 2 - algorithmes.
Apostol, Introduction to Analytic Number Theory - section 9.2 sur le symbole de Jacobi.
PARI/GP documentation, section kronecker - algorithme de reference en production.
OEIS A000089, A002496 - nombres representables par \(x^2 + y^2\), \(x^2 + xy + y^2\).

Retour au sommet