Apa itu Prima?

Contoh 29.18 (Penerapan pada persandian)

Teorema Fermat membuat pemangkatan modulo $n$ dapat dibalik ketika eksponennya dipilih dengan tepat — dan itulah jantung sistem sandi RSA. Dengan $p, q$ bilangan prima besar dan $n = pq$, orang menerbitkan $n$ dan sebuah eksponen $e$; penyandiannya $x \mapsto x^e \bmod n$. Pembacaan sandinya menuntut eksponen $d$ dengan $ed \equiv 1 \pmod{(p-1)(q-1)}$, yang hanya dapat dihitung oleh orang yang tahu $p$ dan $q$ — lagi pula memperoleh kembali $p, q$ dari $n$ berarti memfaktorkan bilangan yang panjangnya ratusan angka, dan tak ada algoritme yang diketahui melakukannya dalam waktu yang masuk akal.