GPPari: liste des polynômes irréductibles

Joaopa · July 2017

Bonjour,

je voudrais savoir s'il existe une fonction sous GP/Pari qui donne tous les polynômes irréductibles de degré $d$ donné sur un corps fini $\mathbb F_q$.

Merci d'avance

GaBuZoMeu · July 2017

En Sage, on peut faire ça de manière pas très intelligente :

F9.<a> = FiniteField(3^2, 'a')
print 'polynôme minimal de a :',charpoly(a,'y')
R.<x>=PolynomialRing(F9)
L=[]
for c in F9 :
    for d in F9 :
        P=x^2+c*x+d
        if P.is_irreducible() : L+=[P]
print 'liste des polynômes irréductibles de degré 2 sur F9 :',L

donne

polynôme minimal de a : y^2 + 2*y + 2
liste des polynômes irréductibles de degré 2 sur F9 : [x^2 + a, x^2 + 2*a + 1, x^2 + 2*a, x^2 + a + 2, x^2 + a*x + 2*a + 1, x^2 + a*x + 2, x^2 + a*x + 2*a, x^2 + a*x + 1, x^2 + (a + 1)*x + a + 1, x^2 + (a + 1)*x + 2*a, x^2 + (a + 1)*x + 2*a + 2, x^2 + (a + 1)*x + a + 2, x^2 + (2*a + 1)*x + a, x^2 + (2*a + 1)*x + 2, x^2 + (2*a + 1)*x + a + 2, x^2 + (2*a + 1)*x + 1, x^2 + 2*x + a, x^2 + 2*x + a + 1, x^2 + 2*x + 2*a + 1, x^2 + 2*x + 2*a + 2, x^2 + 2*a*x + 2*a + 1, x^2 + 2*a*x + 2, x^2 + 2*a*x + 2*a, x^2 + 2*a*x + 1, x^2 + (2*a + 2)*x + a + 1, x^2 + (2*a + 2)*x + 2*a, x^2 + (2*a + 2)*x + 2*a + 2, x^2 + (2*a + 2)*x + a + 2, x^2 + (a + 2)*x + a, x^2 + (a + 2)*x + 2, x^2 + (a + 2)*x + a + 2, x^2 + (a + 2)*x + 1, x^2 + x + a, x^2 + x + a + 1, x^2 + x + 2*a + 1, x^2 + x + 2*a + 2]

Joaopa · July 2017

Merci pour cette solution. Mais pour les très grand degré ca devient vite impraticable.
Une autre solution ?

GaBuZoMeu · July 2017

Et que feras-tu avec une liste des polynômes irréductibles de degré $10^5$ sur $F_{37^{116}}$ ?

Shah d'Ock Anonyme · July 2017

le seigneur des anneaux a écrit:

Je le chérirai, Madame, répondit-il.

Plus serieusement: du papier peint?

GaBuZoMeu · July 2017

Shah d'Ock, tu n'as pas mis suffisamment d'espace avant ton "Edité 2 fois".

Shah d'Ock Anonyme · July 2017

Si, mais ils sont automatiquement supprimés.

GaBuZoMeu · July 2017

Bah, tu ne sais pas y faire
$$\quad$$
Edité 1337 fois. La dernière correction date de il y a trois ans et a été effectuée par GaBuZoMeu.

Shah d'Ock Anonyme · July 2017

Merci! T'es un génie!

Joaopa · July 2017

@ GaBuZoMeu les petits $q$ me conviennent très bien. Par contre, j'ai besoin de lister les irréductibles pour des degré disons jusqu'à 50-100.

Je travaille sur les exponentielles des modules de Drinfeld

GaBuZoMeu · July 2017

Es-tu complètement zinzin ? Le nombre de polynômes irréductibles de degré $d$ sur $\mathbb{F}_q$ est équivalent à $\dfrac1d q^d$ quand $d$ tend vers l'infini. Même pour $q=2$, tu t'imagines avoir une liste de $\dfrac1{60} 2^{60}$ polynômes ?

Joaopa · July 2017

Ca ne me semble pas être un ordre de grandeur irréaliste pour un ordinateur.

Foys · July 2017

2^60/60 fait environ 20 millions de milliards.

parisse · July 2017

Chaque polynome ayant 61 coefficients sur 1 bit, cela ferait environ 2^60 bits, donc 2^57 octets, soit 144 millions de gigaoctets. Impossible de stocker tout ca. Sans compter le temps qui serait necessaire pour faire le calcul.

samok · July 2017

Bonjour Parisse,

c'est pas possible de trouver 144 millions d'ordinateurs avec 1 GO de libre ?

Je veux bien en donner 12 (des Go), si c'est pour comprendre le sens de la vie.

Bon alors en quel temps, histoire de refroidir les machines qui tournent dans les machines

?

S

GaBuZoMeu · July 2017

@Joaopa : outre le caractère totalement irréaliste de cette demande, je ne comprends pas à quoi pourrait te servir d'avoir cette liste. Qu'en ferais-tu ?
Si tu veux compter de manière exacte, c'est bien connu (et même l'objet d'un développement classique d'agreg).

Joaopa · July 2017

Le calcul des exponentielles des modules de Drinfeld fait intervenir les quantités analogues à $\displaystyle \prod_{\substack{h\in\mathbb F_q[T]\\\deg h=i\\h\text{ unitaire}}} h$.
Si on veut voir apparaître des motifs reconnaissables, il faut en sortir quelques dizaines.