Bonjour, Bonsoir

J'essai depuis plusieurs jours de trouver une manière d'implémenter le test de residue quadratique en langage C, j'ai appliqué l'algorithme soit pour p nombre premier impar est a un entier : a est residu quadratic modulo p si et seulement s'il existe un entier b < p tel que b^2 = à mod(p).

Ça marche pour des petits nombre mais pour de très gros nombre le programme tourne beaucoup trop longtemps et ne s'arrête pas. 

J'aimerai donc trouver le moyen de faire moins de teste car en effet je teste toutes les valeurs de b inférieurs à (p-1) /2 avec b € Zp = {1,2,...p-1}

MERCI

Je ne connais pas ton niveau en arithmétique modulaire, tu trouveras facilement des explications ou preuves sur le Net de ce qui suit si besoin.

S'il s'agit simplement de tester si \(a\) est un résidu quadratique pour \(p\) premier  ( et non de calculer \(b\), ce qui est plus délicat), on calcule le symbole de Legendre \((n/p)\) par une formule d'Euler :\((n/p)  \equiv a^{\frac{p-1}{2}} mod(p)\) .

Si le symbole de Legendre vaut 1 , c'est que \(a\) est un résidu quadratique. ( si 0, c'est que \(p\) divise \(a\) et si -1 c'est que \(a\) n'est pas un résidu)
En fait dans le corps fini \(\mathbb{Z}/p\mathbb{Z}\), hors 0, \(\frac{p-1}{2}\) éléments sont des carrés .

edit il semble que l'éditeur soit réparé   

-
Edité par Sennacherib 14 avril 2019 à 9:38:29

Je comprend sauf que je ne comprend pas une chose la formule de calcul du symbole de Legendre est elle vrai tout le temps ou uniquement pour p impair premier ?

on considère uniquement le cas  p premier impair.

Le cas p = 2 ne présente pas d'intérêt. Il est clair que tout entier est résidu quadratique modulo 2

Sennacherib a écrit:

on considère uniquement le cas  p premier impair.

Le cas p = 2 ne présente pas d'intérêt. Il est clair que tout entier est résidu quadratique modulo 2

Est ce qu'on peut faire l'inverse c'est a dire voir s'il est résidu quadratique d'abord pour ensuite calculer le symbole de legendre ? 

je ne comprends pas trop la question.
le symbole de Legendre qui ne peut valoir que 0,1,-1 se calcule par le critère d'Euler justement pour voir facilement  si un nombre est un résidu quadratique.

En supposant que, par un autre moyen  , on est prouvé qu'un entier non divisible par p  est résidu quadratique, son symbole vaudra nécessairement 1.  Je ne vois donc pas trop l'intérêt de ce calcul inverse .  

J'ai bien compris on n'a pas besoni du tout de prouver que a est résidu quadratic pour pouvoir calculer le nombre de legendre, on a juste a calculer le nombre de legendre directement en fonction de la formule d'Euler merci beaucoup franchement ça m'a beaucoup aidé !