Dans la version effective du théorème de Chebotarev sous l'hypothèse de Riemann généralisée et la conjecture d'Artin (voir le livre d'Iwaniec et Kowalski, Analytic Number Theory, §5.13) apparaît un invariant numérique d'un sous-ensemble $D$ d'un groupe fini $G$, que nous appelons la complexité de Littlewood de $D$. Nous étudions en détail cet invariant. À l'aide de cette étude, et d'une application du grand crible, nous traitons de manière améliorée deux questions iques liées à Chebotarev : celle de prouver une majoration du plus petit nombre premier d'un ensemble frobénien, et celle de donner une estimation asymptotique du nombre de nombres premiers ayant des Frobénius donnés dans une famille d'extensions galoisiennes. Nous donnons ensuite des applications concrètes de ces résultats au problème de la factorisation des polynômes à coefficients entiers modulo un nombre premier $p$, à la conjecture de Lang-Trotter pour les surfaces abéliennes, et à la conjecture de Koblitz, obtenant dans chacun de ces cas des estimations meilleures que celles qu'on trouve dans la littérature.