Se volessi calcolare il numero di numeri primi in un numero grande 100 cifre potrei fare una stima.
$$ \pi(x) = \dfrac{x}{ln(x)} $$
Ora posso provare sia con $x = 10^{100}$ e con $x = 10^{99}$ e vedrò
$$ \pi(100)-\pi(99) = 3.904 \times10^{97} $$
Che sono moltissimi numeri primi.
Gli algoritmi crittografici infatti sfruttano l’alta frequenza di numeri primi su alte cifre. L’attaccante ha una probabilità molto bassa di trovare il numero giusto e quindi tende a lasciar stare il brute-forcing.
Due numeri $a , b$ si dicono coprimi se :
$$ MCD(a,b)=1 $$
Se $MCD(a,b)=1$ vuole dire che non ci sono fattori in comune.
Per vedere se due numeri sono coprimi posso utilizzare l’algoritmo di Euclide .
L’algoritmo di Euclide si basa sul seguente teorema :
Dati due numeri $a,b$ con $a>b$ , in caso contrario li inverto. allora $MCD(a,b)=d$
$$ MCD(a,b) =d \\ a=bq1+r1 \\ b = r1q2 +r2 \\ r1 = r2 * q3 +r3 \\ r2 = r3*q4 +r4 $$
Continuo fino a che non trovo $r_k =0$ , una volta trovato allora :
$$ MCD(a,b)=r_{k-1}=d $$
$$ MCD(1180,482) \\ 1180 = 482 * 2 + 216\\ 482 = 216 * 2 +50 \\ 216 = 50 * 4 +16 \\ 50 = 16 * 3 + \underline2 \\ 16 = 2 * 8 +0 \\ MCD(1180,482) = \underline2 $$