Annuler
connectez vous
arithmétique en post-bac
- Arithmétique dans Z - supérieur
- Exercice : le petit théorème de Fermat
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Un best-of d'exos de probabilités (après le bac)
- Espaces vectoriels et Applications linéaires - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Maths sup
Algoritme pour le calcul de racine dans Z/pZ ?
Posté par Ksilver
Bonsoir !
j'ai bessoin pour un programe d'un algoritme pour calculer la racine caré d'un nombre a, dans Z/pZ, pour p premier "assez grand". par assez grand j'entend de l'ordre du milliard : trop grand pour chercher au hasard une racine, mais on peut encore considérer que les opération avec p sont à temps constant car il ne dépasse pas la capacité du calculateur...
plus pécisement, j'ai bessoin de calculer la racine d'un nombre a fixé modulo p, pour un grand nombre de valeur de p...
par exemple calculer la racine de (-3) dans Z/pZ, pour tous les nombre premier p congru a 1 modulo 3 inférieur a 10^8 (si p n'est pas congru a 1 modulo 3 il n'y a pas de racine), en supposant la liste de ces nombres déja connu...
exist-il des algoritmes éfficace pour ca ?
Merci !
Tiens un bouquin ou il y a une partie sur la partie algorithmique des résidus quadratiques: 
.
Par curiosité,tu programmes quoi exactement?
Merci beaucoup, le premier lien me dépasse un peu j'ai l'impression, je n'ai jammais étudié les corps finit autre que les Z/pZ, et les algo proposé les utilises enormement :S ...
en revanche le bouquin semble etre exactement ce que je cherchais ! je vais exploiter ca de ce pas. Merci !
"Par curiosité,tu programmes quoi exactement?"
j'essai de compter les nombres premiers parmi les valeur prises par un polynome, en utilisant un systeme de crible.et en calculant la racines du discrimant modulo p, je peut savoir imédiatement pour qu'elle valeur de n, P(n) sera divisible par p.
pas vraiment, pour le moment, j'ai principalement de la recherche sur mon brouillon, mon cours d'arithmétique et quelque truc sur les loi de réciprocité quadratique, le symbole de Legendre/jacobie etc...
enfin le systeme du crible a rien d'exeptionel : on calcule les zeros du polynome p (de degré 2) dans Z/pZ (c'est la qu'il faut la racine du discrimant), et on coche dans le crible tous les représantants de la classe des zeros. et on recommence ca pour tous les nombres premier inférieur à une certaine valeurs. et il reste plus qu'a compter le nombre de valeur pas coché dans le crible à la fin.