Güçlü muhtemel primellerin primalliğini kanıtlama

Miller-Rabin testinin olasılıksal versiyonunu kullanarak, orta büyüklükte (200-300 haneli) olası primlerin bir listesini oluşturdum. Ama muhtemel yeterince iyi değil! Bu numaralar 'u bilmem gerekiyor. Daha verimli primalite kanıtlama algoritmalarından birini uygulayan, tercihen Python'da sarılmış veya sarılabilir bir kütüphane var mı? Ben nerede bulabileceğimiGüçlü muhtemel primellerin primalliğini kanıtlama

Alternatif bilen var bir net, detaylı ve ön bilgi büyük bir üstlenmez ECPP (ya da benzer hızlı algoritma) ait tam açıklama?

Güncelleme: Bir başka test olan APRT-CLE'in bir ilkel olduğunu kanıtlayan bir Java implementation buldum. Bir atom işlemcisi üzerinde 10 dakikadan daha kısa bir sürede 291 basamaklı bir asal adayı doğruladı. Hala daha hızlı bir şey için umut, ama bu umut verici bir başlangıç gibi görünüyor.

kaynak

2011-01-20 senderle

ECPP'nin açık, ayrıntılı veya eksiksiz olmayan veya önceden çok fazla bilgi sahibi olmayan açıklamalarını okudunuz mu? "Ön bilgi için" standardınızın ne olabileceği hakkında hiçbir fikrimiz yok. Şimdiye kadar denedikleriniz hakkında biraz bilgi verin. –

Bir python kitaplığı istediğimi görüyorum, ancak Java yöntemine göz atmayı düşündünüz mü http://download.oracle.com/javase/1.4.2/docs/api/java/math/BigInteger.html#isProbablePrime(int) ? Ayrıca Miller-Rabin algoritmasını da uyguladıklarını düşünüyorum ve kişisel deneyimimden 500 basamaklı numaralara kadar oldukça hassas. –

Aslında, python'da uygulanan Miller-Rabin algoritmasını çoktan aldım - kolay peasy ve şaşırtıcı derecede hızlı. Ama biraz daha kesin istiyorum. (Ya da nasıl göründüğünüze bağlı olarak sonsuz derecede daha fazla.) – senderle

Güvenilir bir polinom primalite testi veren bir algoritma olarak, AKS'u düşünün. Bir older SO article referanslama uygulamaları ve algoritmanın sunumları vardır.

kaynak

2011-01-20 20:58:09

İlginç, buna bir bakacağım. Anlayışım en hızlı test değil, belki de boyutumdaki numaralar için yeterince hızlı. Teşekkürler! – senderle

@senderle: bunun bir yaklaşım olmadığı ve kanıtlanmamış ama geniş kapsamlı varsayımlara dayanmadığı (Riemann hipotezi gibi) tamamen güvenilir olan tek testin bu olduğu benim anlayışımdır.). –

@Martin v. Löwis: Tartışmalayıcı olmamakla birlikte [wikipediaya katılmıyorum] (http://en.wikipedia.org/wiki/AKS_primality_test): "ECPP ve APR, verilen bir sayının asal olduğunu kesin olarak kanıtlıyor veya onaylamıyor, fakat tüm girdiler için polinom zaman sınırlarına sahip olduğu bilinmemektedir. " Yine de wikipedia yanlış olduğu bilinmektedir. – senderle

Pari/GP kitaplığı ve dilinin, ilkelliği kanıtlamak için APR-CL kullandığını buldum. Bu, aslında bu boyut aralığındaki sayıların tercih edilen algoritmasıdır. GP, bir atom işlemcide 20 saniyenin altında 291 basamaklı bir adayı destekliyor. Bu, ihtiyaçlar için yeterli ve ctypes kullanarak erişebileceğim bir c kütüphanesi ile geliyor.

import ctypes 

def pari_isprime(self, n): 
    try: pari = ctypes.cdll.LoadLibrary("libpari.so") 
    except OSError: 
     print "pari_isprime: couldn't load libpari!" 
     exit() 
    int(n) 
    pari.pari_init(4000000, 2) 
    ret = bool(pari.isprime(pari.gp_read_str(str(n)))) 
    pari.pari_close() 
    return ret

instant modülünü de kullanabilirim.

yukarıda

from instant import inline 

runpari_code = """ 
PyObject* runpari(PyObject *args) { 
    pari_init(40000000, 2); 
    char *pari_code; 
    char *outstr; 

    if (!PyArg_Parse(args, "s", &pari_code)) { return NULL; } // instant uses old-style args; for a module, use PyArg_ParseTuple 
    outstr = GENtostr(gp_read_str(pari_code)); 
    pari_close(); 
    return Py_BuildValue("s", outstr); 
} 
""" 
runpari = inline(runpari_code, system_headers=['pari/pari.h'], libraries=['pari'])

da uygun bir CPython uzantısı esas olarak kullanılabilir: Burada Pari en ayrıştırıcı aracılığıyla bir dize çalışır ve sonucu bir dize olarak döndürür basit c fonksiyon.

kaynak

2011-01-22 22:11:22 senderle

Güçlü muhtemel primellerin primalliğini kanıtlama

cevap

İlgili konular