Générateurs pseudorandom optimaux pour des polynômes de faible degré sur des champs modérément grands

Nous construisons des générateurs pseudorandom explicites qui trompent les polynômes à n variables de degré au plus d sur un champ fini Fq. La longueur de la graine de nos générateurs est O (d n + q), sur des champs de taille exponentielle en d et de caractéristique au moins d (d-1) +1. Les constructions précédentes comme celles de Bogdanov (STOC 2005) et de Derksen et Viola (FOCS 2022) avaient soit une longueur de graine suboptimale, soit nécessitaient que la taille du champ dépende de n. Notre approche suit le paradigme de Bogdanov tout en incorporant des techniques de l'algorithme de factorisation de Lecerf (J. Symb. Comput. 2007) et des aperçus de la construction de Derksen et Viola concernant le rôle de l'indécomposabilité des polynômes.