Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

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



  1. #1
    RVmappeurCS

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


    ------

    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

    -----
    PHELMA Physique-Nanosciences + M2R Astro -> actuellement en thèse de Cosmologie

  2. #2
    RVmappeurCS

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

    Aucune idée ?
    PHELMA Physique-Nanosciences + M2R Astro -> actuellement en thèse de Cosmologie

  3. #3
    Taar

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

    Citation Envoyé par RVmappeurCS Voir le message
    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.

  4. #4
    RVmappeurCS

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

    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
    PHELMA Physique-Nanosciences + M2R Astro -> actuellement en thèse de Cosmologie

  5. A voir en vidéo sur Futura
  6. #5
    Taar

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

    Citation Envoyé par RVmappeurCS Voir le message
    ...

    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.

Discussions similaires

  1. Nombre de nombres premiers connus
    Par RVmappeurCS dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 05/07/2009, 20h25
  2. Nombre premiers
    Par J.M.M dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 06/12/2007, 07h05
  3. e n'est pas un nombre quadratique
    Par Arias dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 27/11/2007, 18h58
  4. divisibilité, nombre premiers
    Par Universmaster dans le forum Mathématiques du collège et du lycée
    Réponses: 9
    Dernier message: 18/11/2007, 09h47
  5. nombre de diviseurs premiers positifs d un nombre
    Par ludovic BOURGOIN dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 23/09/2007, 17h08