Sujet: https://www-fourier.univ-grenoble-alpes ... lget25.pdf
1.1 il faut trouver un polynôme irréductible de degré 2. Par exemple si a n'est pas un carré mod p, alors x^2-a conviendra (car pas de facteur de degré 1). Modulo 5, on peut prendre a=2 ou 3, on prendra M=x^2-2 dans la suite. En général trouver un a qui n'est pas un carré avec a pris au hasard à (environ) 1 chance sur 2 d'être un succès, pour le savoir on peut utiliser l'exponentiation rapide powmod(a,(p-1)/2,p) et vérifier que c'est différent de -1 en O(ln(p)^3), on peut aussi calculer le symbole de Legendre. Comme on est polynomial en log(p), c'est adapté à p grand. Par contre tester pour tous les entiers entre 0 et p-1 qu'on n'a pas de racine pour un polynome de degré 2 ne serait pas adapté.
1.2 powmod(11,(p-1)/2,p) renvoie -1 mod p donc M=x^2-11
1.3 N^2*n^2*log(p)^2
1.4 Karatsuba fonctionne de manière très générale, et permet de descendre en N^(log(3)/log(2))*n^2*log(p)^2
1.5 On ne peut pas faire de la FFT avec une racine 2^t-ième primitive de l'unité sur GF(p,n) en général car une telle racine n'existe pas forcément : en particulier si p=2, car le cardinal de GF(2,n)^* est 2^n-1, non divisible par 2^t
1.6 x^2+(3y-5)*x+7 mod 5 devient x^2+3y*x+2 donc avec x=z^4 et y=z, z^8+3z^5+2
Génériquement le degré de Ptilde est N*2n+(n-1), ici N=2=n, on est seulement en degré 8 parce que le coefficient de x^2 ne contient pas de terme en y
1.7 et 1.8 Ptilde^2=(z^8+3z^5+2)^2=z^16+9z^10+4+6z^13+4z^8+12z^5
On réécrit en puissances de z^4
Ptilde=(z^4)^4+z*(z^4)^3+(4z^2+4)*(z^4)^2+2*z*z^4+4=x^4+y*x^3+(4y^2+4)*x^2+2*y*x+4
qu'on aurait obtenu en calculant directement (x^2+3y*x+2)^2, puisque le degré en y d'un coefficient est <n donc le degré en y d'un produit de coefficients est <2n (en fait même <2n-1), il ne peut donc pas y avoir de mélange car x=z^(2n). L'avantage c'est qu'on fait un produit de polynômes en 1 variable au lieu de 2.
Pour finir il faut remplacer y^2 en utilisant le polynôme minimal de y, y^2=2, donc
P=x^4+y*x^3+2x^2+2y*x+4
1.9 La même qu'une FFT donc N*ln(N)*n^2*log(p)^2
indications correction mai2025 exercice 1
Modérateur : xcasadmin