Algoritma Shor adalah algoritma kuantum yaitu
merupakan suatu algoritma yang berjalan pada komputer kuantum yang berguna
untuk faktorisasi bilangan bulat. Algoritma Shor dirumuskan pada tahun 1994.
Inti dari algoritma ini merupakan bagaimana cara menyelesaikan faktorisasi
terhadap bilanga interger atau bulat yang besar.
Efisiensi algoritma Shor adalah karena efisiensi
kuantum Transformasi Fourier , dan modular eksponensial. Jika sebuah komputer
kuantum dengan jumlah yang memadai qubit dapat beroperasi tanpa mengalah
kebisingan dan fenomena interferensi kuantum lainnya, algoritma Shor dapat
digunakan untuk memecahkan kriptografi kunci publik skema seperti banyak
digunakan skema RSA. Algoritma Shor terdiri dari dua bagian:
- Penurunan yang bisa dilakukan pada komputer
klasik, dari masalah anjak untuk masalah ketertiban -temuan.
- Sebuah algoritma kuantum untuk memecahkan
masalah order-temuan.