On peut aussi énoncer le fait suivant :
g est un générateur du groupe
cyclique est un non carré.
La réciproque est vraie si .
La loi de réciprocité pour le symbole de Legendre affirme
Ainsi, de même que dans l'algorithme d'Euclide pour le calcul du PGCD ou que dans le test de primalité par descente-remontée (voir §), on est ramené, de proche en proche, à traiter des nombres de plus en plus petits.L'intérêt d'une stratégie de ``rapetissement progressif du problème'' transparaît dans l'algorithme de calcul du pgcd de (a,b)= :(r,s), dont voici l'algorithme :
DEBUT
tant que faire ;
(* on crunche et squeeze avec allégresse *)
retourner r ;
FIN