SQuAD'dan Rastgele Soru:

Asal sayıların ortak anahtar şifreleme algoritmalarının oluşturulmasına uygulanabileceği ne zaman keşfedildi?

Cevap:

1970'ler

Alınan cümleler:

1. Herkese açık şekilde asal sayılar ortak anahtar şifreleme algoritmalarının oluşturulması için temel olarak kullanılabileceği açıklandı Ancak, bu vizyon, 1970'lerde paramparça oldu.
2. Asal sayılar, büyük sayıları asal çarpanlarına ayırmanın zorluğu gibi özelliklerden yararlanan ortak anahtar şifrelemesi gibi bilgi teknolojisindeki çeşitli rutinlerde kullanılır.
3. Büyük sayıların asallığını test etmek için deneme bölmeden çok daha verimli algoritmalar tasarlanmıştır.
4. RSA ve Diffie-Hellman anahtar değişimi gibi birkaç ortak anahtar şifreleme algoritması, büyük asal sayılara dayanır (örneğin, RSA için 512 bit asal sayılar sıklıkla kullanılır ve 1024 bit asal sayılar Diffie–Hellman için tipiktir.) .
5. Asal sayılar ayrıca karma tablolar ve sözde rasgele sayı üreteçleri için de kullanılır.
6. Bu asal sayıların bazıları dağıtılmış hesaplama kullanılarak bulunmuştur.
7. Uzun bir süre boyunca, genel olarak sayı teorisi ve özel olarak asal sayıların incelenmesi, asal sayıların kullanımı dışında konuyu çalışmanın kişisel çıkarı dışında hiçbir uygulama olmaksızın, saf matematiğin kanonik örneği olarak görüldü. aşınmayı eşit olarak dağıtmak için dişli dişleri.
8. Deterministik algoritmalar, verilen bir sayının asal olup olmadığını kesin olarak söylemenin bir yolunu sağlar.
9. "Tüm olası algoritmalar" ifadesi, yalnızca bugün bilinen algoritmaları değil, gelecekte keşfedilebilecek herhangi bir algoritmayı da içerir.
10. Örneğin, deneme bölme işlemi deterministik bir algoritmadır, çünkü doğru yapılırsa, her zaman bir asal sayıyı asal ve bileşik bir sayıyı bileşik olarak tanımlayacaktır.
11. Karar problemi olarak ifade edilen, girdinin k'den küçük bir faktöre sahip olup olmadığına karar verme problemidir. Etkili bir tamsayı çarpanlarına ayırma algoritması bilinmemektedir ve bu gerçek, RSA algoritması gibi birkaç modern şifreleme sisteminin temelini oluşturur.
12. Algoritmik problemlerin karmaşıklığına açıkça adanan asıl araştırma başlamadan önce, çeşitli araştırmacılar tarafından çok sayıda temel atıldı.
13. Bu yerel-küresel ilke, asal sayıların sayı teorisine olan önemini bir kez daha vurgulamaktadır.
14. Olasılıksal algoritmalar normalde daha hızlıdır, ancak bir sayının asal olduğunu tam olarak kanıtlamaz.
15. Bununla birlikte, bu problem için en iyi bilinen kuantum algoritması olan Shor'un algoritması, polinom zamanında çalışır.
16. Eratosthenes'e atfedilen Eratosthenes Kalburu, günümüzde bilgisayarlarda bulunan büyük asal sayılar bu şekilde oluşturulmamasına rağmen, asal sayıları hesaplamak için basit bir yöntemdir.
17. Kullanılan algoritma ne olursa olsun, çözümü önemli kaynaklar gerektiriyorsa, bir problem doğası gereği zor olarak kabul edilir.
18. Rastgele bitler kullanan algoritmalara rasgele algoritmalar denir.
19. Bir problem bir algoritma ile çözülebiliyorsa, problemi çözen bir Turing makinesinin var olduğuna inanılır.
20. Carmichael sayıları asal sayılardan önemli ölçüde daha nadirdir, bu nedenle bu test pratik amaçlar için faydalı olabilir.
21. Örneğin, Derrick Norman Lehmer'in 10,006,721'e kadar olan asal sayıların listesi, 1956 gibi geç bir tarihte yeniden basıldı, ilk asal sayı olarak 1 ile başladı.
22. Cobham'ın tezi, bir polinom zaman algoritmasını kabul ederse, bir problemin uygun miktarda kaynakla çözülebileceğini söylüyor.
23. Öklid ayrıca bir Mersenne asalından mükemmel bir sayının nasıl oluşturulacağını da gösterdi.
24. Ocak 2016[güncelleme] itibariyle, bilinen en büyük asal sayı 22.338.618 ondalık basamağa sahiptir.
25. Bu tür sorular, sayıların analitik veya cebirsel yönlerine odaklanarak sayı teorisinin çeşitli dallarının gelişimini teşvik etti.