AATA Exercices supplémentaires : primalité et factorisation

Exercices 7.5 Exercices supplémentaires : primalité et factorisation

Dans le cryptosystème RSA, il est important de pouvoir trouver facilement de grands nombres premiers. De plus, ce cryptosystème n’est pas sécurisé si l’on peut factoriser un nombre composé qui est le produit de deux grands nombres premiers. Les solutions à ces deux problèmes sont assez simples. Pour savoir si un nombre \(n\) est premier ou pour factoriser \(n\text{,}\) on peut utiliser la division par essai. On divise simplement \(n\) par \(d = 2, 3, \ldots, \sqrt{n}\text{.}\) Soit une factorisation sera obtenue, soit \(n\) est premier si aucun \(d\) ne divise \(n\text{.}\) Le problème est qu’un tel calcul est prohibitivement long si \(n\) est très grand.

🔗

1.

Un meilleur algorithme pour factoriser les entiers positifs impairs est l’algorithme de factorisation de Fermat.

🔗

Soit \(n= ab\) un entier composé impair. Prouver que \(n\) peut s’écrire comme différence de deux carrés parfaits :

\begin{equation*} n = x^2 - y^2 = (x - y)(x + y)\text{.} \end{equation*}

Par conséquent, un entier positif impair peut être factorisé exactement lorsque nous pouvons trouver des entiers \(x\) et \(y\) tels que \(n = x^2 - y^2\text{.}\)

🔗

🔗
Écrire un programme pour implémenter l’algorithme de factorisation suivant, basé sur l’observation de la partie (a). L’expression ceiling(sqrt(n)) désigne le plus petit entier supérieur ou égal à la racine carrée de \(n\text{.}\) Écrire un autre programme pour effectuer la factorisation par division par essai et comparer la vitesse des deux algorithmes. Quel algorithme est le plus rapide et pourquoi ?
🔗

🔗

x := ceiling(sqrt(n))
y := 1
1 : while x^2 - y^2 > n do
    y := y + 1
if x^2 - y^2 < n then
    x := x + 1
    y := 1
    goto 1
else if x^2 - y^2 = 0 then
    a := x - y
    b := x + y
    write n = a * b

🔗

2. Test de primalité.

Rappelons le petit théorème de Fermat du Chapitre 6. Soit \(p\) premier avec \(\gcd(a, p) = 1\text{.}\) Alors \(a^{p-1} \equiv 1 \pmod{p}\text{.}\) Nous pouvons utiliser le petit théorème de Fermat comme test de détection préliminaire des nombres premiers. Par exemple, \(15\) ne peut pas être premier puisque

\begin{equation*} 2^{15-1} \equiv 2^{14} \equiv 4 \pmod{15}\text{.} \end{equation*}

Cependant, \(17\) est un nombre premier potentiel puisque

\begin{equation*} 2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}\text{.} \end{equation*}

On dit qu’un entier composé impair \(n\) est un pseudo-premier si

\begin{equation*} 2^{n-1} \equiv 1 \pmod{n}\text{.} \end{equation*}

Parmi les nombres suivants, lesquels sont premiers et lesquels sont pseudo-premiers ?

\(\displaystyle 342\)
🔗

🔗
\(\displaystyle 811\)
🔗

🔗
601
🔗

🔗
\(\displaystyle 561\)
🔗

🔗
\(\displaystyle 771\)
🔗

🔗
\(\displaystyle 631\)
🔗

🔗

🔗

3.

Soit \(n\) un entier composé impair et \(b\) un entier positif tel que \(\gcd(b, n) = 1\text{.}\) Si \(b^{n-1} \equiv 1 \pmod{n}\text{,}\) alors \(n\) est un pseudo-premier en base \(b\text{.}\) Montrer que \(341\) est un pseudo-premier en base \(2\) mais pas un pseudo-premier en base \(3\text{.}\)

🔗

4.

Écrire un programme pour déterminer tous les nombres premiers inférieurs à \(2000\) par division par essai. Écrire un second programme qui déterminera tous les nombres inférieurs à \(2000\) qui sont soit premiers, soit pseudo-premiers. Comparer la vitesse des deux programmes. Combien y a-t-il de pseudo-premiers inférieurs à \(2000\) ?

🔗

Il existe des nombres composés qui sont des pseudo-premiers pour toutes les bases avec lesquelles ils sont premiers entre eux. Ces nombres sont appelés nombres de Carmichael. Le premier nombre de Carmichael est \(561 = 3 \cdot 11 \cdot 17\text{.}\) En 1992, Alford, Granville et Pomerance ont prouvé qu’il existe une infinité de nombres de Carmichael [4]. Cependant, les nombres de Carmichael sont très rares. Il n’y a que 2163 nombres de Carmichael inférieurs à \(25 \times 10^9\text{.}\) Pour des tests de primalité plus sophistiqués, voir [1], [6] ou [7].

🔗

Précédent Top Suivant