Test di primalità di Adleman-Pomerance-Rumely
# 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}).$
