Pertanyaan Acak dari SQuAD:

Kapan ditemukan bahwa bilangan prima dapat diterapkan pada pembuatan algoritma kriptografi kunci publik?

Menjawab:

tahun 1970-an

Kalimat yang diambil:

1. Namun, visi ini hancur pada 1970-an, ketika mengumumkan bahwa bilangan prima dapat digunakan sebagai dasar untuk pembuatan algoritma kriptografi kunci publik.
2. Bilangan prima digunakan dalam beberapa rutinitas dalam teknologi informasi, seperti kriptografi kunci publik, yang memanfaatkan sifat-sifat seperti kesulitan memfaktorkan bilangan besar ke dalam faktor primanya.
3. Algoritma yang jauh lebih efisien daripada pembagian percobaan telah dirancang untuk menguji primalitas bilangan besar.
4. Beberapa algoritma kriptografi kunci publik, seperti RSA dan pertukaran kunci Diffie–Hellman, didasarkan pada bilangan prima yang besar (misalnya, bilangan prima 512-bit sering digunakan untuk RSA dan bilangan prima 1024-bit adalah tipikal untuk Diffie–Hellman.) .
5. Bilangan prima juga digunakan untuk tabel hash dan generator nomor pseudorandom.
6. Beberapa bilangan prima ini telah ditemukan menggunakan komputasi terdistribusi.
7. Untuk waktu yang lama, teori bilangan secara umum, dan studi tentang bilangan prima pada khususnya, dipandang sebagai contoh kanonik matematika murni, tanpa aplikasi di luar kepentingan pribadi mempelajari topik tersebut dengan pengecualian penggunaan bilangan prima. gigi gir untuk mendistribusikan keausan secara merata.
8. Algoritma deterministik menyediakan cara untuk mengetahui dengan pasti apakah suatu bilangan prima atau tidak.
9. Ungkapan "semua algoritma yang mungkin" mencakup tidak hanya algoritma yang dikenal saat ini, tetapi algoritma apa pun yang mungkin ditemukan di masa depan.
10. Misalnya, pembagian percobaan adalah algoritma deterministik karena, jika dilakukan dengan benar, akan selalu mengidentifikasi bilangan prima sebagai prima dan bilangan komposit sebagai komposit.
11. Diungkapkan sebagai masalah keputusan, itu adalah masalah memutuskan apakah input memiliki faktor kurang dari k. Tidak ada algoritma faktorisasi bilangan bulat yang efisien yang diketahui, dan fakta ini membentuk dasar dari beberapa sistem kriptografi modern, seperti algoritma RSA.
12. Sebelum penelitian aktual yang secara eksplisit dikhususkan untuk kompleksitas masalah algoritmik dimulai, banyak fondasi diletakkan oleh berbagai peneliti.
13. Prinsip lokal-global ini sekali lagi menggarisbawahi pentingnya bilangan prima bagi teori bilangan.
14. Algoritma probabilistik biasanya lebih cepat, tetapi tidak sepenuhnya membuktikan bahwa suatu bilangan prima.
15. Namun, algoritma kuantum yang paling terkenal untuk masalah ini, algoritma Shor, berjalan dalam waktu polinomial.
16. Saringan Eratosthenes, dikaitkan dengan Eratosthenes, adalah metode sederhana untuk menghitung bilangan prima, meskipun bilangan prima besar yang ditemukan saat ini dengan komputer tidak dihasilkan dengan cara ini.
17. Suatu masalah dianggap sulit secara inheren jika solusinya membutuhkan sumber daya yang signifikan, apa pun algoritme yang digunakan.
18. Algoritma yang menggunakan bit acak disebut algoritma acak.
19. Diyakini bahwa jika suatu masalah dapat diselesaikan dengan suatu algoritma, ada mesin Turing yang menyelesaikan masalah tersebut.
20. Namun, bilangan carmichael secara substansial lebih jarang daripada bilangan prima, jadi tes ini dapat berguna untuk tujuan praktis.
21. Misalnya, daftar bilangan prima Derrick Norman Lehmer hingga 10.006.721, dicetak ulang hingga tahun 1956, dimulai dengan 1 sebagai bilangan prima pertamanya.
22. Tesis Cobham mengatakan bahwa masalah dapat diselesaikan dengan jumlah sumber daya yang layak jika mengakui algoritma waktu polinomial.
23. Euclid juga menunjukkan bagaimana membangun bilangan sempurna dari bilangan prima Mersenne.
24. Pada Januari 2016[pembaruan], bilangan prima terbesar yang diketahui memiliki 22.338.618 angka desimal.
25. Pertanyaan seperti itu mendorong perkembangan berbagai cabang teori bilangan, dengan fokus pada aspek analitik atau aljabar bilangan.