Sistem kriptografi RSA yang diperkenalkan oleh R. Rivest, A. Shamir, dan L. Adleman pada tahun 1978 didasarkan pada sulitnya memfaktorkan bilangan besar. Walaupun mencari dua bilangan prima besar secara acak lalu mengalikannya bukan tugas yang sulit, dengan algoritma tercepat yang tersedia pada awal 1990-an, memfaktorkan bilangan 150 digit yang merupakan hasil kali dua bilangan prima besar akan memerlukan sekitar 50 juta tahun jika dikerjakan oleh 100 juta komputer yang masing-masing menjalankan 10 juta instruksi per detik. Meskipun algoritmanya telah berkembang, memfaktorkan bilangan yang merupakan hasil kali dua bilangan prima besar tetap memerlukan komputasi yang terlampau berat.