Test di primalità di Adleman-Pomerance-Rumely

Nella teoria computazionale dei numeri, il test di primalità di Adleman-Pomerance-Rumely è un algoritmo per determinare se un numero è primo. Diversamente da altri algoritmi più efficienti per questo scopo, esso evita l'uso di numeri causali, perciò è un test di primalità deterministico. Prende il nome dai suoi scopritori, Leonard Adleman, Carl Pomerance e Robert Rumely. Il test implica l'aritmetica nei campi ciclotomici.

Fu migliorato in seguito da Henri Cohen e Hendrik Willem Lenstra e chiamato APRT-CL (o APRCL). È usato spesso con UBASIC sotto il nome APRT-CLE (APRT-CL esteso) e può testare la primalità di un intero n nel tempo:

$O((\ln n{)}^{c\ln \ln \ln n}).$

Bibliografia

• Template:Cita testo
• Template:Cita testo
• Template:Cita libro

Collegamenti esterni

• Template:Cita web
• Template:En Una applet di fattorizzazione che usa APR-CL in certe condizioni (codice sorgente incluso)
• Template:En Pari/GP usa conditionalmente APR-CL nella sua implementazione di isprime().