Problématique

3 problèmes se posent dans le domaine de la primalité :
soit $N \in \mathbb{Z}$,

• on veux prouver que $N$ n'est pas premier ($N$ est composé) (c'est très facile)
• on veux prouver que $N$ est premier (c'est relativement facile)
• on veux, sachant que $N$ est composé, factoriser $N$ (i.e. donner un diviseur de $N$) (c'est très difficile)