Toate numerele prime, altele decât 2, sunt impare. Cu toate acestea, marea majoritate a numerelor impare nu sunt prime.
De exemplu, luați numerele prime 3 și 5, produsul lor este 15 și poate fi folosit ca un modul RSA (nesigur). 15 este un număr compus impar.
Compozit înseamnă că are mai mulți factori primi.
Numerele naturale mai mari decât 1 sunt toate fie prime, fie compuse.
Pentru RSA sigur folosim numere prime mult mai mari. Dar principiul este același. Înmulțim la numere prime impare mari și obținem un modul compozit impar mare $n$.
Găsirea factorilor unui compozit atât de mare poate fi foarte dificilă. În unele cazuri, dincolo de ceea ce este posibil în prezent. Dar greu de factorizat nu înseamnă că factorizarea nu există. Și, de fapt, cu ajutorul cheii private este chiar ușor.
Deci imposibil de factorizat ar putea însemna că nu este practic nici măcar de către un stat național care cheltuiește un miliard de dolari. Cu această definiție, RSA 4096 este imposibil de factorizat.
Dar dacă vrei să spui imposibil ca și imposibil, chiar și cu calcul nelimitat sau un computer quantom futurist. De aceea, toate modulele RSA sunt compuse și, prin urmare, pot fi factorizate.
P.s - factorizarea ar putea fi definită pentru a permite „factorizarea” numerelor prime, ceea ce este ușor, doar detectați că este prim, folosind, de exemplu, Miller-Rabin și, dacă da, returnați o listă care conține doar numărul de intrare.
