Asal sayı
Hesaplamalı yöntemler > Asallık testi ile asallığın kanıtlanması

Bir  n sayısının asal olup olmadığını belirlemek amacıyla kullanılan en gelişmiş modern testlerden bazıları, yanlış bir sonuç üretme ihtimali olan olasılıksal (veya Monte Carlo) algoritmalarıdır. Örneğin, bir  p sayısı için Solovay–Strassen asallık testi uygulamasında,  2 ile  p-2 arasından rastgele seçilen bir  a sayısı üzerinden,  a^{(p-1)/2}\pm 1 ifadesinin  p tarafından bölünebilirliği modüler üs alma aracılığıyla denetlenir. Bu durumda, algoritma pozitif yanıt verir; aksi takdirde, negatif yanıt verir.  p sayısı gerçekten asal ise, algoritma her zaman pozitif yanıt verir; fakat  p bileşik bir sayı ise, pozitif yanıt verme olasılığı en fazla 1/2, negatif yanıt verme olasılığı ise en az 1/2'dir.
Bu deneyin aynı sayı üzerinde  n defa yinelenmesi halinde, bir bileşik sayının her seferinde bu deneyden başarıyla geçme ihtimali en çok  1/2^{n} olarak belirlenir. Deneylerin sayısı arttıkça, bu ihtimal üssel olarak azaldığından, yinelenen deneyi geçen bir sayının asal olduğuna ilişkin yüksek bir güven seviyesi (fakat kesin bir kanıt değil) elde edilir. Diğer taraftan, eğer deney en az bir kere dahi başarısızlıkla sonuçlanırsa, bu durumda söz konusu sayının mutlaka bileşik olduğu kesinleşir.
Bu şekilde bir testi geçmeyi başaran bileşik sayılara sanki asal (İng. pseudoprime) adı verilir.
Diğer taraftan, bazı algoritmaların sonuçlarının daima doğru olacağına dair bir garanti bulunmaktadır. Bu durumun bir örneği deneme bölme yöntemidir. Kesin doğru çıktı sağlayan algoritmalar, AKS asallık testi gibi deterministik (rastgele olmayan) algoritmaları,
ve algoritmanın nihai yanıtını etkilemeyen rastgele seçimler yapan, örneğin bazı elips eğri asallık kanıtlama çeşitlerindeki gibi Las Vegas algoritmasını kapsar.
Elips eğri metodu, bir sayının asallığı konusunda bir karara vardığında, kolaylıkla doğrulanabilir bir asallık sertifikası temin eder.
Pratik uygulamalarda, garantili doğruluk sağlayan asallık testleri içinde, elips eğri asallık testi en hızlı olanıdır; ancak, bu testin çalışma zamanı analizi, katı ispatlara değil, sezgisel argümanlara dayanır. Matematiksel olarak zaman karmaşıklığı ispatlanmış AKS asallık testi mevcut olmakla birlikte, uygulamada elips eğri asallığını kanıtlamadan daha yavaş işler. Bu metodlar, rastgele sayılar üretilip test edilerek ve asal olan bir sayı bulunana dek büyük rastgele asal sayılar üretmek için kullanılabilir; bu süreçte, bir hızlı olasılıksal test, garantili doğruluk sağlayan bir algoritma ile kalan sayıların asallığının doğrulanmasından önce, çoğu bileşik sayıyı çabucak elemine etme işlevi görür.
Aşağıda sunulan tablo, mevcut testlerden seçilmiş olanları sıralamaktadır. Bu testlerin çalışma zamanları, incelenmek üzere olan sayıyı temsil eden  n ve olasılıksal algoritmalar için gerçekleştirilen testlerin sayısını ifade eden  k ile ilişkilendirilmiştir. Ek olarak,  \varepsilon , keyfi olarak belirlenebilen küçük bir pozitif değeri simgeler ve log, belirli bir tabana atıfta bulunmaksızın logaritmayı işaret eder. Büyük O gösterimi, her bir zaman kısıtının, boyutsuz birimlerden zaman birimlerine çevrilebilmesi için bir sabit faktör ile çarpılması gerektiğini belirtir; bu faktör, algoritmanın uygulandığı bilgisayarın türü gibi uygulama ayrıntılarına bağlıdır, fakat  n ve  k girdi parametrelerine bağlı olmaz.
| Test | Geliştirildiği yıl | Tip | Çalışma süresi | Notlar | Kaynaklar |
| --- | --- | --- | --- | --- | --- |
| AKS asallık testi | 2002 | deterministik |  O((\log n)^{6+\varepsilon }) |  |  |
| Elips eğrisi asallık kanıtlama | 1986 | Las Vegas |  O((\log n)^{4+\varepsilon }) sezgisel olarak |  |  |
| Baillie–PSW asallık testi | 1980 | Monte Carlo |  O((\log n)^{2+\varepsilon }) |  |  |
| Miller–Rabin asallık testi | 1980 | Monte Carlo |  O(k(\log n)^{2+\varepsilon }) | hata olasılığı  4^{-k} |  |
| Solovay–Strassen asallık testi | 1977 | Monte Carlo |  O(k(\log n)^{2+\varepsilon }) | hata olasılığı  2^{-k} |  |