Algoritme
Algoritme bisa diklasifikasikan berdasarkan jumlah waktu yang dibutuhkan untuk selesai dibandingkan dengan ukuran inputnya. Ada berbagai varietas: beberapa algoritme selesai dalam waktu linear relatif terhadap ukuran input, beberapa selesai dalam jumlah waktu yang eksponensial atau lebih buruh, dan beberapa berhenti. Sebagai tambahan, beberapa masalah bisa memiliki berbagai algoritme dengan kompleksitas yang berbeda, sementara permasalahan yang lain bisa saja tidak memiliki algoritme atau tidak diketahui algoritmanya yang efisien. Ada juga pemetaan dari beberapa algoritme terhadap permasalahan lain. Karena itu, lebih cocok untuk mengklasifikasikan permasalahan itu sendiri bukannya algoritme menjadi kelas-kelas yang sama berdasarkan kompleksitas dari kemungkinan algoritme terbaik baginya.
Kriptografi
Algoritme kunci-publik didasari pada kesulitan komputasional pada masalah yang beragam. Kesulitan yang paling terkenal ialah [[faktorisasi integer]] (seperti algoritme RSA yang didasari pada masalah yang berhubungan dengan faktor integer), namun masalah [[logaritma diskrit]] juga penting. Banyak kriptanalisis kunci-publik berhubungan dengan algoritme numerikal untuk menyelesaikan masalah komputasional ini, dan beberapa darinya, efisien (contoh dalam waktu pengerjaan). Sebagai contoh, algoritme yang paling dikenal untuk menyelesaikan kriptografi kurva eliptik versi logaritma diskrit sangat menghabiskan banyak waktu ketimbang algoritme yang paling dikenal untuk faktorisasi, paling tidak untuk masalah dengan besar yang lebih kurang sama. Oleh karena itu, segala hal harus sama, untuk mencapai kekuatan menahan serangan yang sama, teknik enkripsi berbasis faktor harus menggunakan kunci yang lebih besar dari teknik kurva eliptik. Untuk alasan ini, kriptosistem kunci-publik yang didasari pada kurva eliptik telah menjadi lebih dikenal sejak penemuannya pada pertengahan tahun 1990an.