Abstract:
The paper is devoted to a detailed description of an algorithm for constructing strong pseudoprime Carmichael numbers that pass the Miller — Rabin test for many of the first prime bases. Explicit formulas are obtained for calculating all prime moduli $p$ such that a fixed $b$ is a quadratic non-residue modulo $p$. Lower bound estimates of the constructed Carmichael numbers are provided. The software implementation of the proposed algorithm enabled the construction of a 3,055-digit strong Carmichael pseudoprime, which successfully passes the Miller — Rabin test for all integer bases below 2 371. This significantly surpasses previously reported results.
Keywords:strong pseudoprime, Carmichael number, Miller — Rabin test.
Fulltext:
PDF file (628 kB)