Méthode $p - 1$ de Pollard

Soit $p$ un diviseur premier de $N$. Alors :

$$\forall a \in \mathbb{F}_p,\; a^{p-1} \equiv 1 \; mod \; p.$$

On dit que $p - 1$ est $B-lisse$ si toutes les puissances de ses diviseurs premiers sont inférieures à $B$.

$$p-1 \; B-lisse \Leftrightarrow (p-1 = \prod{l_i^{e_i}} \Rightarrow {l_i}^{e_i} \leq B).$$

Remarquons que

$$p-1 = \prod{l_i^{e_i}} = ppcm({l_i}^{e_i}) \Rightarrow ppcm({l_i}^{e_i})\; \vert\; ppcm(1,2, .. , B)$$

car

$${l_i}^{e_i} \leq B$$

et

$$\forall j, k\;\; l_j \wedge l_k = 1.$$

Donc s'il existe $p$ qui divise $N$ tel que $p - 1$ soit $B-lisse$ alors

$$p-1\; \vert\; ppcm(1,2, .. , B)$$

et comme par Fermat

$$a^{p-1} \equiv 1\; mod\; p$$

alors

$$a^{ppcm(1,2, .. , B)} \equiv 1\; mod\; p \Leftrightarrow p\;\vert\;a^{ppcm(1,2, .. , B)} - 1$$

et par hypothèse

$$p\;\vert\;N$$

donc

$$p\; \vert\; pgcd(a^{ppcm(1,2, .. , B)} - 1, N).$$

Ce pgcd est un diviseur non trivial de $N$, c'est donc celui-ci que l'on calcule, abandonnant le $p$ de notre hypothèse.

Bien entendu cette méthode ne s'applique que si $N$ possède de tels diviseurs.