Oui, pardon, c’est juste une histoire de complexité. Avec ta représentation, un élément de Fpk ça prend klogp bits de mémoire, additionner c’est k opérations de Fp et multiplier ça dépend, mais ça va être en gros au moins du klogk (k2 si tu fais ça naïvement).
Je crois que ce que les gens font généralement, c’est au lieu de dire qu’un élément de Fpk c’est un polynôme de degré <k, tu dis que c’est un truc de la forme Xi, en supposant que le polynôme X est un générateur du groupe multiplicatif du corps Fp[X]/P où P c’est ton polynôme irréductible (condition qui est réalisée quand P est primitif, justement). Tu représentes l’élément 0 par 0, 1 par pk−1 et Xi par i pour 1≤i<pk−1. Ça prend toujours klogp bits en mémoire, mais multiplier/diviser devient super rapide (c’est en gros une seule addition dans Z/(pk−1)Z). Additionner/soustraire c’est un peu relou, mais en écrivant Xi+Xj=Xi(1+Xj−i) tu vois que si t’as assez de place pour stocker ton corps en mémoire, il suffit juste de précalculer la représentation multiplicative de tous les Xi+1. Si t’as ça, additionner/soustraire c’est aussi 2 ou 3 opérations de Z/(pk−1)Z.
Pour le coup c’est facile de compter le nombre de polynômes primitifs unitaires de degré k : il y en a ϕ(pk−1), donc la proba de tomber dessus c’est ϕ(pk−1)/kpk. Bon et avec les mains, si on utilise la borne inf sur ϕ de Wikipedia, apcr on a :
kpkϕ(pk−1)≥k(C(logk+loglogp)+1)1
Donc en gros tout à l’heure notre proba était de l’ordre de 1/k, maintenant de l’ordre de 1/klogk, donc il faudra juste un facteur logk en plus pour ré-obtenir une probabilité constante d’avoir un polynôme primitif (ce qui est plus fort qu’irréductible).
Mais effectivement, ce que tu dis marche tout à fait (et il y a même des cas où c’est plus intéressant de faire comme tu dis).
mais je vais jeter un coup d’œil au papier de J.M. COUVEIGNES et R. LERCIER, qui s’il tient ses promesses a l’air très intéressant
Bonne chance, il a pas l’air facile ![^^](/static/smileys/hihi.png)