Il tuo numero è primo?

Come funziona

Un numero primo è un intero maggiore di 1 i cui unici divisori sono 1 e sé stesso: 2, 3, 5, 7, 11 e così via. Ogni altro intero maggiore di 1 è composto e si esprime come prodotto di primi in un unico modo, a parte l’ordine: 1200 = 2⁴ × 3 × 5². 0 e 1 non sono né primi né composti.

Dividere per ogni possibile fattore è troppo lento per numeri grandi, quindi il controllo usa il test di Miller–Rabin. Sceglie una base a e cerca nelle potenze di a una proprietà che ogni primo deve rispettare; un composto di solito la viola e la base che lo rivela è detta testimone. Sotto circa 3,3 × 10²⁴, usare i primi 13 numeri primi come basi rileva ogni composto: lì «primo» è una dimostrazione. Oltre, nessun insieme fisso è dimostrato sufficiente: chi supera 20 basi è indicato come «probabilmente primo», molto affidabile nella pratica ma non dimostrato. «Non primo» è sempre dimostrato.

I fattori primi si trovano per divisioni successive, istantanee fino a 10¹⁵, cioè un milione di miliardi. Oltre, un composto viene riconosciuto ma non scomposto qui. La differenza non è casuale: verificare se un numero è primo è molto più facile che trovarne i fattori e gran parte della cifratura moderna si basa su questo.