Test de primărie Adleman-Pomerance-Rumely
Salt la navigare Salt la căutare
În teoria computațională a numerelor , testul de primărie Adleman-Pomerance-Rumely este un algoritm pentru a determina dacă un număr este prim . Spre deosebire de alți algoritmi mai eficienți în acest scop, acesta evită utilizarea numerelor cauzale, deci este un test de primalitate determinist . Este numit după descoperitorii săi, Leonard Adleman , Carl Pomerance și Robert Rumely . Testul implică aritmetica în câmpurile ciclotomice .
Ulterior a fost îmbunătățit de Henri Cohen și Hendrik Willem Lenstra și denumit APRT-CL (sau APRCL). Este adesea folosit cu UBASIC sub numele APRT-CLE (APRT-CL extins) și poate testa primalitatea unui număr întreg n în timp:
Bibliografie
- Leonard M. Adleman , Carl Pomerance și Robert S. Rumely , Despre diferențierea numerelor prime de numerele compuse , în Annals of Mathematics , vol. 117, nr. 1, 1983, 173–206, DOI : 10.2307 / 2006975 .
- Henri Cohen și Hendrik W., Jr. Lenstra , Primality testing și Jacobi sume , în Matematica calculelor , vol. 42, n. 165, 1984, 297-330, DOI : 10.2307 / 2007581 .
- Hans Riesel , Prime Numbers and Computer Methods for Factorization , Birkhauser, 1994, pp. 131–136 , ISBN 0-8176-3743-5 .
linkuri externe
- ( EN ) APR și APR-CL , pe primes.utm.edu .
- ( EN ) Un applet de factoring care utilizează APR-CL în anumite condiții (cod sursă inclus)
- ( EN ) Pari / GP folosește condiționat APR-CL în implementarea sa isprime ().
