Advanced Search

Dans cet article, on s’intéresse au problème suivant. Soient $p$ un nombre premier, $S\subset {𝔽}_p$ et $𝒫\subset \{P\in {𝔽}_p\left[X\right]:degP\le d\}$. Quel est le plus grand entier $k$ tel que pour toutes paires de sous-ensembles disjoints $𝒜,ℬ$ de ${𝔽}_p$ vérifiant $|𝒜\cup ℬ|=k$, il existe $P\in 𝒫$ tel que $P\left(x\right)\in S$ si $x\in 𝒜$ et $P\left(x\right)\notin S$ si $x\in ℬ$  ? Ce problème correspond à l’étude de la complexité de certaines familles d’ensembles pseudo-aléatoires. Dans un premier temps, nous rappelons la définition de cette complexité et resituons le contexte des ensembles pseudo-aléatoires. Ensuite, nous exposons les différents...