Test de primalité de Miller-Rabin - Bibm@th.net

Soit $p$ un nombre premier impair que l'on écrit sous la forme $p=2^s\times d+1$. Soit $a\in\{1,\dots, p-1\}$. On définit une suite $(b_i)$ en posant $$b_{i}=a^{d\times 2^i}.$$

1. Question préliminaire : Montrer que dans $\mathbb Z/p\mathbb Z$, l'équation $x^2=1$ entraine $x=1$ ou $x=-1$.
2. Montrer que $b_{s}\equiv 1\ [p]$.
3. On suppose que $b_0$ n'est pas congru à 1 modulo $p$. Montrer l'existence de $i\in\{0,\dots,s-1\}$ tel que $b_i\equiv -1\ [p]$.
4. En déduire un test de non-primalité d'un entier.