Partage
  • Partager sur Facebook
  • Partager sur Twitter

Résidu Quadratic

Sujet résolu
    14 avril 2019 à 5:35:58

    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

    • Partager sur Facebook
    • Partager sur Twitter
      14 avril 2019 à 9:25:28

      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é  :p 

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

      • Partager sur Facebook
      • Partager sur Twitter
      tout ce qui est simple est faux, tout ce qui est compliqué est inutilisable
        16 avril 2019 à 17:38:10

        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 ?
        • Partager sur Facebook
        • Partager sur Twitter
          16 avril 2019 à 23:14:36

          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

          • Partager sur Facebook
          • Partager sur Twitter
          tout ce qui est simple est faux, tout ce qui est compliqué est inutilisable
            17 avril 2019 à 22:17:21

            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 ? 

            • Partager sur Facebook
            • Partager sur Twitter
              18 avril 2019 à 8:59:13

              je ne comprends pas trop la question.:o
              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 .  

              • Partager sur Facebook
              • Partager sur Twitter
              tout ce qui est simple est faux, tout ce qui est compliqué est inutilisable
                18 avril 2019 à 17:25:30

                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 :D merci beaucoup franchement ça m'a beaucoup aidé !
                • Partager sur Facebook
                • Partager sur Twitter

                Résidu Quadratic

                × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                • Editeur
                • Markdown