Discussion:Racine primitive modulo n
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Erreurs dans la table[modifier le code]
Désolé pour les erreurs que j'ai laissées dans la table précédente (diff, sous un autre nom d'utilisateur), je n'ai plus le programme sous la main mais il devait y avoir une boulette. Comme il me semble regrettable de s'arrêter à 569 (pourquoi 569 ?) et que d'autre part le site de l'OEIS donne les racines primitives des 10000 premiers nombres premiers (donc c'est sourcé), je me permets de remettre un tableau jusqu'à 1000. Pourquoi 1000, me dira-t-on, mais c'est au moins un compte rond.
Je laisse ci-dessous le programme en Python pour générer le tableau, pour ceux qui ont envie d'apporter des modifications qui prendraient trop de temps à la main. Noter que le programme calcule les racines primitives, mais vérifie aussi que ce sont les mêmes dans la table de l'OEIS, pour les nombres premiers < 1000, donc les données collent bien au fichier donné en référence dans l'article. Le programme de calcul est ici particulièrement naïf (on vérifie qu'il y a bien p-1 puissances distinctes modulo p), mais ça suffit pour générer la table rapidement, et pour être raisonnablement sûr que le programme est correct. Noter également que la lecture du fichier signale 7 erreurs : ce sont des lignes vides à la fin du fichier qui causent une erreur quand on convertit les deux nombres de chaque ligne en entier, et ça ne concerne donc pas les 168 premières lignes, les seules qui nous intéressent.
def isqrt(n):
if n < 0:
raise ValueError
elif n < 2:
return n
else:
a = 1 << ((1 + n.bit_length()) >> 1)
while True:
b = (a + n // a) >> 1
if b >= a:
return a
a = b
def isprime(n):
if n < 5:
return n == 2 or n == 3
elif n%2 == 0:
return False
else:
r = isqrt(n)
k = 3
while k <= r:
if n%k == 0:
return False
k += 2
return True
def readsep(name, sep="\t", encoding="utf-8", fun=None):
f = open(name, "rt", encoding=encoding)
a = []
err = 0
for line in f.readlines():
try:
if fun is None:
v = [x.strip() for x in line.strip().split(sep)]
else:
v = [fun(x.strip()) for x in line.strip().split(sep)]
a.append(v)
except ValueError:
err += 1
f.close()
if err > 0:
print("readsep(%s), %d lines not read" % (name, err))
return a
def isprimroot(a, n):
s = set()
r = 1
for i in range(n):
r = (r*a)%n
s.add(r)
return len(s) == n - 1
def findprimroot(n):
if n == 2:
return 1
else:
a = 2
while not isprimroot(a, n):
a += 1
return a
def primroots(a, b):
v = []
for n in range(a, b + 1):
if isprime(n):
v.append([n, findprimroot(n)])
return v
def diffindex(a, b):
n = len(a)
v = []
for i in range(n):
if a[i] != b[i]:
v.append(i)
return v
def buildtable():
a = primroots(1, 1000)
b = readsep("b001918.txt", sep=" ", fun=int)
b = b[:168]
v = diffindex([r[1] for r in a], [r[1] for r in b])
if len(v) != 0:
print("Erreur de calcul: %s" % v)
return
for i in range(14):
print('|----- align="center"')
for j in range(12):
p, r = a[i + 14*j]
print('! [[%d (nombre)|%d]] || bgcolor="lightgreen" | [[%d (nombre)|%d]]' % (p, p, r, r))
buildtable()