Găsirea numerelor prime mari ocolitoare

Problema cu utilizarea expresiei lui Chernick $(6k+1)(12k+1)(18k+1)$ iar generalizările sale sunt că numărul este întotdeauna congruent cu 1 mod 3, astfel încât de două ori numărul plus unu este divizibil cu și, prin urmare, nu prim. Nu totul este însă pierdut și metodele de Loh și Niebur „Un nou algoritm pentru construirea de numere mari Carmichael” (care a inspirat celebrul Alford, Granville și Pomerance „Există infinit de multe numere Carmichael” rezultat) poate fi folosit pentru a produce numere Carmichael mari care sunt 2 mod 3 și care au mulți factori (făcându-le potrivite pentru aplicația dvs. abuzivă).

Inspirându-ne de la algoritmul C al lui Loh și Niebur (p. 285), adăugăm mici condiții suplimentare:

1. Alegeți un produs al puterilor prime $\Lambda\leftarrow 2^{h_1}q_2^{h_2}\cdots q_r^{h_r}$ unde $h_i$ sunt toate pozitive și niciunul dintre $q_i$ sunt 3. (Construcția funcționează cel mai bine dacă $q_i$ sunt numere prime mici, deci luând $q_2=5$, $q_3=7$ și așa mai departe este o alegere bună).
2. Testează totul $p(\alpha_1,\ldots,\alpha_r)\leftarrow 2^{\alpha_1}q_2^{\alpha_2}\cdots q_r^{\alpha_r}+1$ cu $0\le \alpha_i\le h_i$ pentru primalitate. Colectarea valorilor de succes într-un set $\mathcal S$ (omitând $\Lambda+1$). Ați putea dori să omiteți primul 3 în cazul în care a avea un prim putativ divizibil cu 3 este puțin evident sau pentru că este o alegere probabilă pentru o bază pentru un test Fermat.
3. Calcula $\prod_{p\in\mathcal S}\pmod\Lambda$ și numiți acest reziduu $s$.
4. Subseturile de testare $\mathcal T\subset\mathcal S$ a cărui cardinalitate are paritate diferită de $\mathcal S$ până când găsim un submult astfel încât $\prod_{p\in\mathcal T}p\equiv s\pmod\Lambda$
5. A stabilit $N=\prod_{p\in\mathcal S\backslash\mathcal T}p$. Acesta va fi un număr Carmichael, va avea un număr impar de factori primi și va fi congruent cu 2 mod 3.

Ar trebui să existe suficientă varietate în alegerile $\mathcal T$ pentru a obține un număr Carmichael de o dimensiune adecvată. Apoi puteți înmulți cu doi și adăugați unul. Deoarece numărul rezultat este congruent cu $3\pmod\Lambda$, nu va fi divizibil cu nicio împărțire prime $\Lambda$ și are șanse mult mai mari decât media de a fi prim (ceea ce este frumos).