Nombre premiers : Théorème de Proth et non-résidu quadratique

[invitebd8dbca5]

Bonjour.

Je suis en train de me faire une petite bibliothèque perso en C++ avec différents algorithmes de calcul concernant les nombres premiers.

Mais j'ai un petit problème concernant une remarque sur le théorème de Proth sur Wikipédia (allez voir l'article):

"If p is a quadratic nonresidue modulo a then the converse is also true, and the test is conclusive. Such an a may be found by iterating a over small primes and computing the Jacobi symbol until: (a/p)=-1."

Pourquoi si p est un non-résidu quadratique modulo a alors la réciproque du théorème de Proth est vraie et p est composé ?

Merci
-----

[invitebd8dbca5]

Aucune idée ?

[invite9cf21bce]

Pourquoi si p est un non-résidu quadratique modulo a alors la réciproque du théorème de Proth est vraie et p est composé ?

Bonsoir.

Déjà, je crois que la réciproque dont il est question est :

"Si p n'est pas résidu quadratique modulo a et si alors p est composé."

En tout état de cause, si l'énoncé était plutôt (comme semble l'indiquer le choix du symbole de Jacobi au lieu de ) :

"Si a n'est pas résidu quadratique modulo p et si alors p est composé."

alors je pense que ce serait plus ou moins évident. Je te rappelle que dans , lorsque p est premier impair, en raison de la factorisation , les éléments non nuls se répartissent en deux parties de même cardinal : ceux qui vérifient et ceux qui vérifient . La première partie coïncide (par inclusion et équipotence) avec l'ensemble des carrés non nuls.

Partant de là, je vois deux options :

• soit l'auteur de l'article de Wikipedia a fait une inversion dans l'énoncé (rapide) de la réciproque
• soit on peut faire quelque chose avec la loi de réciprocité (j'ai essayé un coup mais je suis gêné par les a pairs, je vais continuer de regarder).

Je penche pour la première option.

Amicalement.

Taar.

[invitebd8dbca5]

Merci beaucoup. J'ai fais prépa PSI et mes connaissances de sujets relatifs aux corps tels que Fp restent très "éparses" (disons que je continue à creuser certains sujets de maths dans mon temps libre).

Mais suite à ton "rappel" j'ai un peu approfondi et ça paraît effectivement assez évident.

Ainsi pour avoir un test concluant sur p, je commence par chercher un a tel que le symbole de Jacobi (a/p) soit égal à -1 (je peux me limiter à chercher a comme nombre premier pour accélérer le test). Ensuite j'applique le théorème de Proth qui me dit que si a^((p-1)/2)=-1(mod p) alors p est premier. Si ce n'est pas le cas, alors le test permet de conclure que p est composé.

Une confirmation ?

Merci beaucoup Taar

[A voir en vidéo sur Futura]

[invite9cf21bce]

...

Ainsi pour avoir un test concluant sur p, je commence par chercher un a tel que le symbole de Jacobi (a/p) soit égal à -1 (je peux me limiter à chercher a comme nombre premier pour accélérer le test). Ensuite j'applique le théorème de Proth qui me dit que si a^((p-1)/2)=-1(mod p) alors p est premier. Si ce n'est pas le cas, alors le test permet de conclure que p est composé.

Une confirmation ?

Pas de quoi.

Ta stratégie me semble correcte. Pour calculer le symbole de Jacobi, comme a est petit et p grand, on emploie la loi de réciprocité quadratique.

Comme "50% des valeurs de a conviennent pour le sens direct", on peut faire aussi comme cela :

On prend un a (premier impair par exemple).
On calcule modulo p. Ça se fait assez bien si on a p en binaire (mais je pense que tu le sais déjà... ).
Si c'est -1 c'est terminé.
Sinon, on calcule le symbole de Jacobi. Si c'est -1 c'est terminé.
Sinon, on passe à une autre valeur de a.

Les deux stratégies terminent (des tas de a ne sont pas résidus quadratiques modulo p), mais il faut évaluer leurs efficacités relatives. Essaie les deux ?

Bon courage.

Taar.