Tests de primalité probabilistes

Une façon de procéder peut sans doute consister à prendre un élément primitif (par exemple la classe de 2) et à l'élever à une puissance aléatoire.

On prend au hasard (avec équiprobabilité) un élément dans $\Z/n\Z$. S'il est inversible, on a gagné. Sinon, on recommence.

Je crois que tu dis une bêtise. Pour ce qui est de savoir si la classe d'un entier $k$ est inversible modulo $n$, c'est l'algorithme d'Euclide qui permet de répondre à la question. C'est quelque chose à savoir faire pour mettre en place la stratégie de Guego.

Pour $2$ c'est facile, il s'agit juste de savoir si ton nombre est pair ou impair.

La question était "comment tirer uniformément des éléments de $\left(\mathbb Z/n \mathbb Z\right)^{\times}$".