From: nikl+sm000785@mathematik.tu-muenchen.de (Gerhard Niklasch)
Subject: Re: équation diophantienne
Date: 16 May 1999 17:20:04 GMT
Newsgroups: sci.math
Keywords: Computing modular square roots

In article <7hkks0$r44$1@front4.grolier.fr>,
 "Jean Yves" <ifra@club-internet.fr> writes:
|> Help! existe t'il une méthode (ou une formule) pour trouver toutes les
|> solutions quand elle en admet de l'équation diophantienne:
|> x^2=a modulo A avec A premier donné et a donné?
|> Excusez moi d'écrire en français mais je ne parle pas un mot d'Anglais!

Et bien, il n'y a qu'un nombre fini de cas, donc il existe bien
une méthode...  mais une énumeration naïve ne sera pas une bonne
idée lorsque A est grand.

PARI-GP utilise l'algorithme suivant.

(1) cas A=2 : retourner a.
(2) cas a=0 : retourner 0.
(3) (précalculation, ne dépendant que d'A)
  (3.1) écrire A-1 = 2^e * t avec t impair.
  (3.2) trouver un y tel que y^(2^e) = 1 (mod A) mais y^(2^(e-1))
        n'est pas égal à 1 mod A.  Lorsque e=1, on prend y := -1.
        Lorsque e>1, essayer y := k^t pour k=2,3,... (donc la
        première condition est satisfaite)  jusqu'à ce que l'on
        en a trouvé un qui satisfait aussi la seconde condition.

Tous les calculs suivants s'entendent mod A.

(4) calculer v := a^((t+1)/2) et w := a^t.  (Il est utile de commencer
    par calculer z := a^((t-1)/2), et alors v := z*a, w := z^2*a.)

L'idée de ce qui suit est que si w=1, v et -v (mod A) seront déjà
les solutions désirées.  Or, on ne peut pas s'en attendre d'être si
heureux - en général il faudra corriger v en utilisant la quantité
y calculée auparavant.

(5) boucle - répéter jusqu'à w=1 :
  (5.1) poser x := w^2, k := 1,
        répéter jusqu'à x=1 : { k := k+1, x := x^2 } ;
        (donc nous savons que w^(2^k)=1 mais w^(2^(k-1)) ne l'est pas)
  (5.2) si k=e, on peut finir : il n'y a pas de solution ;
  (5.3) poser x := y^(2^(e-k-1)) (en prenant le carré e-k-1 fois)
        (donc x^(2^(k+1))=1 mais x^(2^k) ne l'est pas) ;
  (5.4) remplacer  e := k, v := v*x, y := x^2, w := w*y
        (donc on a encore une fois, avec les nouvelles valeurs,
        y^(2^e)=1 mais y^(2^(e-1)) non égal à 1 mod A) ;
  et répéter (5) si w n'est pas encore égal à 1.

(La quantité e devient plus petite avec chaque itération, et on a
toujours w^(2^e)=1, donc (5) n'est répété qu'un nombre fini de fois.)

(6) retourner les solutions : +-v mod A  (ou si ceci est préférable :
    v et A-v.)

Gerhard
-- 
* Gerhard Niklasch <nikl@mathematik.tu-muenchen.de> * spam totally unwelcome
* http://hasse.mathematik.tu-muenchen.de/~nikl/ ******* all browsers welcome
* This .signature now fits into 3 lines and 77 columns * newsreaders welcome