Büyük Asal Sayı Nasıl Oluşturulur | Quanta Dergisi

Asal sayılar aldatıcı şeylerdir. Okulda bunların 1'den ve kendisinden başka çarpanı olmayan sayılar olduğunu ve matematikçilerin binlerce yıldır sonsuz sayıda sayının var olduğunu bildiklerini öğreniyoruz. Komuta üzerine bir tane üretmek sanki zor olacakmış gibi görünmüyor.

Ama bu. Rastgele büyük asal sayıların oluşturulması oldukça karmaşıktır. Temel olarak her ikisinin de dezavantajları olan iki hesaplama seçeneğiniz var. Rastgeleliği kullanabilir ve tahmin ederek bir tane bulabilirsiniz, ancak yöntem tutarsızdır; her seferinde farklı bir asal sayı üretme riskiyle karşı karşıya kalırsınız. Veya daha güvenilir, deterministik bir algoritma kullanabilirsiniz, ancak bu algoritmanın hesaplama maliyeti yüksektir.

Mayıs ayında bilgisayar bilimcilerden oluşan bir ekip gösterdi bir tür hibrit yaklaşımın da işe yarayabileceğini söyledi. Belirli uzunluktaki bir asal sayının çıktısını almak için rastgele ve deterministik yaklaşımları etkili bir şekilde birleştiren ve algoritma birçok kez çalıştırılsa bile aynı sayıyı verme olasılığının yüksek olduğu bir algoritma yayınladılar. Algoritma, rastgelelik ve karmaşıklığı ilginç yollarla birbirine bağlıyor ve aynı zamanda bazı kodlama şemalarının büyük asal sayıların oluşturulmasına dayandığı kriptografi için de yararlı olabilir.

"Her biri farklı uzunlukta bir asal sayı oluşturmaya çalışan bir dizi girişimde bulundular ve girişimlerden birinin işe yaradığını gösterdiler" dedi. Roei Tell, İleri Araştırma Enstitüsü'nde çalışmaya dahil olmayan teorik bir bilgisayar bilimcisi. "Bu, deterministik olarak seçilmiş bir asal sayı üreten, ancak bu süreçte para atmanıza ve rastgele seçimler yapmanıza olanak tanıyan bir yapıdır."

Asal sayılar için etkili bir tarif hazırlamanın zorluğunun derin kökleri vardır. Sahte rastgele algoritmalar üzerinde çalışan Ofer Grossman, "Asal sayıların nasıl dağıtıldığı veya asal sayılardaki boşluklar hakkında gerçekten çok fazla şey bilmiyoruz" dedi. Ve onları nerede bulacağımızı bilmiyorsak, sıfırdan bir asal sayı oluşturmanın kolay bir yolu yoktur.

Zamanla araştırmacılar yukarıda bahsedilen yaklaşımları geliştirdiler. En basit yol sadece tahmin etmektir. Örneğin 1,000 basamaklı bir asal sayı istiyorsanız, 1,000 basamaklı bir sayıyı rastgele seçip kontrol edebilirsiniz. "Eğer asal değilse, bir tane daha denersiniz, bir tane daha ve bir tane bulana kadar bu böyle devam eder" dedi Rahul SanthanamOxford Üniversitesi'nde bilgisayar bilimcisi ve yeni makalenin ortak yazarı. "Çok sayıda asal sayı olduğundan, bu algoritma nispeten az sayıda yinelemeden sonra size yüksek olasılıkla asal olan bir sayı verecektir." Ancak rastgeleliği kullanmak, muhtemelen her seferinde farklı bir sayı elde edeceğiniz anlamına gelir, dedi. Tutarlılığa ihtiyacınız varsa, örneğin büyük asal sayıların varlığına bağlı bir şifreleme güvenlik yöntemi kullanıyorsanız bu bir sorun olabilir.

Diğer yaklaşım ise deterministik bir algoritma kullanmaktır. Bir başlangıç ​​noktası seçebilir ve sayıları asallık açısından sırayla test etmeye başlayabilirsiniz. Eninde sonunda bir tane bulmanız kaçınılmazdır ve algoritmanız sürekli olarak bulduğunuz ilk şeyin çıktısını verecektir. Ancak biraz zaman alabilir: 1,000 basamaklı bir asal sayı arıyorsanız, 2'li bir hesaplama bile⁵⁰⁰ Evrenin yaşından çok daha uzun sürecek adımlar, başarıyı garanti etmek için yeterli değil.

2009 yılında matematikçi ve Fields madalyalı Terence Tao daha iyisini yapmak istedi. Matematikçilere, belirli bir büyüklükteki bir asal sayıyı hesaplamalı bir zaman sınırı içinde bulmak için deterministik bir algoritma bulmaları konusunda meydan okudu.

Bu zaman sınırı polinom zamanı olarak bilinir. Bir algoritma, attığı adımların sayısı polinom fonksiyonundan fazla değilse polinom zamanda bir problemi çözer. n, girişin boyutu. (Bir polinom fonksiyonu, pozitif tamsayı kuvvetlerine yükseltilmiş değişkenlere sahip terimleri içerir; n² veya 4n³.) Asal sayı yapısı bağlamında, n istediğiniz asal sayının basamak sayısını ifade eder. Hesaplamalı olarak konuşursak, bunun maliyeti çok fazla değil: Bilgisayar bilimcileri, algoritmalar tarafından polinom zamanında çözülebilen problemleri kolay olarak tanımlıyorlar. Zor bir problem, aksine, üstel zaman alır; bu, üstel bir fonksiyonla (2 gibi terimler içerir) yaklaşık olarak tahmin edilen bir dizi adım gerektirdiği anlamına gelir.ⁿ).

Onlarca yıldır araştırmacılar rastgelelik ve sertlik arasındaki bağlantıyı araştırıyorlar. Rastgeleliğe izin verirseniz ve her seferinde farklı bir sayı almakla yetinirseniz asal sayı oluşturma probleminin kolay, determinizmde ısrar ederseniz zor olduğu düşünülürdü.

Henüz hiç kimse Tao'nun meydan okumasının üstesinden gelmeyi başaramadı ama yeni çalışma yaklaşıyor. Massachusetts Teknoloji Enstitüsü'ndeki bilgisayar bilimcileri Shafi Goldwasser ve Eran Gat tarafından 2011'de ortaya atılan bir yaklaşımdan büyük ölçüde yararlanılıyor. Rastgeleliğin faydalarından yararlanabilecek ve yüksek olasılıkla her seferinde aynı cevabı üretebilecek, büyük asal sayıları bulmak gibi arama problemleri için matematiksel tarifler olan "psödodeterministik" algoritmaları tanımladılar. Tarifteki rastgele bitlerin verimliliğini kullanacaklar, bu da sonuçta rastgelelikten arındırılacak ve deterministik görünecek.

O zamandan beri araştırmacılar sözde-deterministik algoritmaları araştırıyorlar. 2017 yılında Warwick Üniversitesi'nden Santhanam ve Igor Oliveira (yeni çalışmaya da katkıda bulundular) tarif edilen Rastgeleliği kullanan ve ikna edici derecede deterministik görünen asal sayıların oluşturulmasına yönelik sahte deterministik bir yaklaşım, ancak "alt üstel" zamanda işe yaradı - üstel zamandan daha hızlı, ancak polinom zamanından daha yavaş. Daha sonra 2021'de Tell ve Lijie ChenBerkeley'deki Kaliforniya Üniversitesi'nden bilgisayar bilimcisi, araştırdı Sahte rastgele sayı üreteci (rastgele bir çıktıdan ayırt edilemeyen bir sayı dizisi üreten bir algoritma) oluşturmak için zor bir problemin nasıl kullanılacağı. Chen, "[Biz] sertlik ve sözde rastgelelik arasında yeni bir bağlantı bulduk" dedi.

Parçalar nihayet 2023 baharında bir araya geldi. hesaplama karmaşıklığı üzerine bir eğitim kampı Berkeley'deki Simons Bilgisayar Teorisi Enstitüsü'nde araştırmacılar sorun üzerinde birlikte çalışmaya ve geçmiş sonuçları bir araya getirmeye başladıklarında. Chen, yeni çalışma için Oxford'da bilgisayar bilimcisi ve ortak yazarlardan biri olan Hanlin Ren'in, Chen-Tell sonucunu Santhanam-Oliveira yaklaşımıyla yeni bir şekilde birleştirmeye yönelik ilk fikirlere sahip olduğunu söyledi. Daha sonra tüm ekip yeni makaleyi üretmek için fikirleri daha kapsamlı bir şekilde geliştirdi.

Santhanam, ortaya çıkan sözde-deterministik algoritmanın, polinom zamanında asal sayılar üretmek için geçmiş çalışmalara bakmanın yeni yollarını kullandığını söyledi. Belirli bir uzunluğa sahip bir asal sayının çıktısını almak için rastgelelik kullanıldığı kanıtlanmıştır ve araç, rastgele tahminden daha doğru ve deterministik hesaplamadan daha hesaplama açısından daha verimlidir.

Santhanam, yeni algoritmanın oldukça basit olduğunu ve çok çeşitli arama problemlerine, aslında üyeliğin polinom zamanında belirlenebildiği asal sayılar gibi herhangi bir yoğun sayı alt kümesine uygulanabileceğini söyledi. Ama mükemmel değil. Algoritma sonsuz sayıda giriş uzunluğu için çalışır, ancak tüm rakam uzunluklarını kapsamaz. Hala bazı değerler olabilir n Algoritmanın deterministik olarak bir asal sayı üretmediği bir yerde.

Grossman, "Bu küçük uyarıdan kurtulmak harika olurdu" dedi.

Santhanam, nihai hedefin hiçbir şekilde rastgelelik gerektirmeyen bir algoritma bulmak olduğunu söyledi. Ancak bu arayış hala açık. "Kullanmak istediğimiz şey determinizmdir" dedi.

Ancak aynı zamanda sözde rasgele süreçlerin güçlü araçlar olduğuna ve asal sayılar oluşturma gibi projelerin matematik, bilgisayar bilimi, bilgi teorisi ve diğer alanlardaki fikirleri birbirine bağlamak için bunları kullanmanın yalnızca bir yolu olduğuna da dikkat çekti.

Tell, "Bu harika gözlemlerin başka nereye varacağını düşünmeye çalışmak heyecan verici" dedi.