🔢 mathematics

Ours go to 211: Euler pseudoprimes to 47 prime bases (from Carmichael numbers)

This paper classifies Carmichael numbers to develop a fast algorithm for generating composite Euler pseudoprimes, ultimately discovering a record-breaking example that passes the Solovay-Strassen primality test for the first 47 prime bases up to 211.

Original authors: Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange, Benne de Weger

Published 2026-02-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange, Benne de Weger

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a security guard at a high-security bank (a computer system using encryption like RSA). Your job is to check if a visitor claiming to be a "Prime Number" (a special, indivisible number essential for security) is actually telling the truth.

To do this, you have a special test called the Solovay-Strassen test. You ask the visitor a series of questions based on different "bases" (think of these as different security codes). If the visitor is a real Prime, they will answer correctly every time. If they are a fake (a composite number), they usually fail the test.

However, there are master forgers called Pseudoprimes. These are composite numbers that are so good at lying that they can answer "Yes" to your security questions even though they aren't primes. The more questions you ask, the harder it is for them to keep up the act.

The Problem: The Master Forgers

The authors of this paper, a team of mathematicians, wanted to find the ultimate master forger. They wanted to find a composite number that could fool the security test for as many different codes (bases) as possible.

They discovered that the best forgers come from a specific family of numbers called Carmichael Numbers. These are numbers that are so deceptive they pass the basic "Fermat test" for every possible code. But the authors wanted to go further: they wanted numbers that pass the more advanced "Euler test" for many specific codes.

The Strategy: Building a Super-Forger

Instead of looking for these numbers one by one (which is like looking for a needle in a haystack), the authors realized they could build them.

Think of it like building a Lego castle.

The Bricks: They started with small, reliable "atomic" Carmichael numbers (the basic bricks).
The Blueprint: They developed a set of rules (a classification system) to figure out which bricks could be snapped together. They found that if you combine two specific types of bricks (called "Class A"), the resulting structure is much more likely to be a super-deceptive number.
The Assembly Line: They wrote a fast computer algorithm to multiply these numbers together.
- First, they multiplied two bricks to make a slightly bigger forger.
- Then, they multiplied those bigger forgers together to make even bigger ones.
- They kept stacking them, layer by layer, creating numbers with hundreds of digits.

The Analogy: The "Imposter" Party

Imagine a party where everyone is trying to pretend they are a specific type of VIP (a Prime Number).

Normal People (Composites): They get caught immediately when asked a simple question.
Carmichael Numbers: They are good actors. They can answer almost any question correctly.
The Authors' Goal: They wanted to find the actor who could answer every question correctly, even the hardest ones asked by the top 47 VIPs.

The authors realized that if you take two actors who are good at answering questions 1 through 37, and you "marry" them (multiply them), their "child" (the new number) is likely to be good at answering questions 1 through 40 or 41. By carefully choosing which actors to marry, they created a lineage of imposters that got better and better at lying.

The Result: The Ultimate Imposter

Using their method, the team found a number so deceptive that it passed the security test for the first 47 prime bases.

To put this in perspective:

The test checks if a number is prime by asking it questions based on the numbers 2, 3, 5, 7, 11, 13, etc.
The number they found successfully lied to the test for all of these bases, all the way up to the 47th prime number, which is 211.

This number is a "composite" (it can be divided), but it is so perfectly constructed that it looks exactly like a prime number to the standard tests used in cryptography. It survived 47 rounds of interrogation without slipping up.

Why Does This Matter?

You might ask, "Why do we want to find fake numbers?"

Security: It helps us understand how strong our encryption really is. If a hacker can generate these "super-forgers," they could trick systems into accepting fake keys, breaking the security.
Math: It shows us the limits of our tests. It proves that while probabilistic tests (tests that check a few random bases) are usually safe, they aren't perfect.
The "Luck" Factor: The paper notes that the Solovay-Strassen test has a 50% chance of catching a liar in one go, while the Miller-Rabin test has a 75% chance. The authors' number was so good it survived 47 rounds of a 50/50 coin flip, which is statistically incredibly rare (like flipping heads 47 times in a row).

Summary

In simple terms, these mathematicians built a "Frankenstein's Monster" of numbers. They took small, deceptive numbers and glued them together using a clever recipe. The result was a massive, composite number that is so convincing it fooled the most common prime-checking tests for 47 different attempts, reaching a record-breaking level of deception.

1. Problem Statement

The paper addresses the challenge of constructing Euler pseudoprimes that survive the Solovay-Strassen primality test for a large number of consecutive prime bases.

Context: Public-key cryptosystems (like RSA) rely on generating large prime numbers. Since deterministic primality testing is computationally expensive, probabilistic tests like Solovay-Strassen or Miller-Rabin are used.
The Threat: If an adversary can supply a composite number (a pseudoprime) that passes these tests for many bases, they can compromise the system.
The Goal: The authors aim to find composite numbers $n$ that satisfy the Euler criterion $\left(\frac{a}{n}\right) \equiv a^{(n-1)/2} \pmod n$ for the maximum possible number of consecutive prime bases starting from 2.
Comparison: While Miller-Rabin has a failure probability of at most $1/4$ per base, Solovay-Strassen has a failure probability of at most $1/2$ . The authors seek to push the boundaries of how many bases a composite number can "fool" in the Solovay-Strassen test.

2. Methodology

The authors employ a multi-stage approach combining theoretical classification, filtering, and iterative multiplication.

A. Classification of Carmichael Numbers

The authors identify Carmichael numbers as the primary candidates for Euler pseudoprimes because they are Fermat pseudoprimes for all bases coprime to $n$ . They introduce a classification system based on the Carmichael lambda function $\lambda(n)$ and the index $i(n) = (n-1)/\lambda(n)$ :

Class A: $i(n)$ is even. These numbers have the maximum possible number of Euler liars ( $\frac{1}{2}\phi(n)$ ). All liars have a Jacobi symbol of $+1$ .
Class B: $i(n)$ is odd. These are further subdivided into B1 and B2 based on the 2-adic valuation of the prime factors. Class B generally has fewer Euler liars than Class A.
Key Insight: To maximize the number of surviving bases, the authors focus almost exclusively on Class A Carmichael numbers.

B. The Multiplication Strategy

The core algorithm relies on the multiplicative property of the Jacobi symbol.

Atomic Pseudoprimes: The authors start with "atomic" Carmichael numbers (those not formed by the product of other Carmichael numbers) that survive up to a certain base $a$ (specifically $a \ge 37$ ) and have no small prime factors (smallest factor $> 150$ ).
Iterative Construction: They multiply two existing Euler pseudoprimes, $n_1$ and $n_2$ , to create a larger composite $n = n_1 n_2$ .
The "Same Base" Heuristic: The authors prove (Lemma 13) that if $n_1$ $n_{1}$ and $n_2$ $n_{2}$ are both in Class A and survive up to the same prime base $a$ $a$ , their product $n$ $n$ (if it remains a Carmichael number in Class A) will automatically survive up to the next prime base $b$ $b$ .
- Reasoning: For bases $\le a$ , both $n_1$ and $n_2$ have Jacobi symbol $+1$ , so the product is $+1$ . For the next base $b$ , both $n_1$ and $n_2$ have Jacobi symbol $-1$ (since they fail at $b$ individually), so the product is $(-1) \times (-1) = +1$ , allowing the composite to pass.
Filtering: To ensure efficiency and correctness, the algorithm filters inputs to ensure:
1. Both factors are in Class A.
2. The product satisfies the necessary conditions to remain in Class A (based on 2-adic valuations of $n-1$ and $\lambda(n)$ ).
3. The product is square-free (a requirement for Carmichael numbers).
4. The smallest prime factor is sufficiently large to avoid immediate failure at small bases.

C. Algorithm Implementation

The authors developed Algorithm 1, which:

Takes two inputs from sets $epsp_{N_1}(a)$ and $epsp_{N_2}(a)$ (sets of pseudoprimes surviving up to base $a$ ).
Checks the 2-adic valuation condition to predict if the product will be Class A.
Verifies the product is a Carmichael number ( $\lambda(n) | n-1$ ).
Checks the Jacobi symbol for the next prime base to determine the new survival limit.
Iterates this process to build larger numbers (e.g., $epsp_4$ , $epsp_8$ , $epsp_{16}$ ).

3. Key Contributions

Theoretical Classification: A rigorous classification of Carmichael numbers into Classes A, B1, and B2, providing exact counts of Euler liars for each class. This proves that Class A is the optimal target for constructing strong pseudoprimes.
Construction Algorithm: A fast, recursive algorithm that multiplies existing Euler pseudoprimes to generate larger ones, leveraging the "double negative" property of Jacobi symbols to extend the range of surviving bases.
Record-Breaking Results: The construction of an Euler pseudoprime that survives the first 47 prime bases (up to 211).
Statistical Analysis: Comprehensive statistics on the distribution of these numbers, including their residue classes modulo 120 (showing a strong bias toward $n \equiv 1 \pmod{120}$ ) and the divisibility properties of $n-1$ .

4. Results

The Record Holder: The authors found a composite number with 1230 bits that survives the Solovay-Strassen test for all prime bases from 2 up to 211.
- This corresponds to the first 47 prime bases.
- The number is a product of multiple smaller Carmichael numbers constructed via their algorithm.
Intermediate Records:
- Products of 2 atomic numbers ( $epsp_2$ ) reached base 139.
- Products of 4 atomic numbers ( $epsp_4$ ) reached base 191.
- Products of 8 atomic numbers ( $epsp_8$ ) reached base 199.
Failure Analysis: The authors observed that as the number of factors increases, the probability of the product failing to be square-free increases significantly due to shared prime factors in the underlying atomic Carmichael numbers. This limited their ability to construct even larger numbers (e.g., $epsp_{32}$ ) without finding new atomic inputs.
Alternative Discovery: The paper briefly introduces Sophie Germinus pseudoprimes (products of $p$ and $2p-1$ where both are prime) as a secondary class of numbers with high numbers of Euler liars ( $\phi(n)/4$ ), though they did not yield better results than the Class A Carmichael products in this study.

5. Significance

Cryptographic Implications: This work demonstrates that probabilistic primality tests, specifically Solovay-Strassen, can be fooled by carefully constructed composites for a surprisingly large number of bases. While Miller-Rabin is generally preferred due to its lower failure rate ( $1/4$ vs $1/2$ ), this research highlights the theoretical limits of probabilistic testing under adversarial conditions.
Algorithmic Efficiency: The paper provides a blueprint for efficiently generating "hard" pseudoprimes. The strategy of multiplying numbers that fail at the same base to create a number that passes that base is a powerful heuristic for constructing counterexamples to primality tests.
Mathematical Insight: The classification of Carmichael numbers by the parity of their index and 2-adic valuations offers new structural insights into the distribution of Euler liars, confirming that Class A numbers are the "best" candidates for this specific cryptographic weakness.

In summary, the paper successfully pushes the boundary of known Euler pseudoprimes to 47 bases by combining number-theoretic classification with a recursive multiplication algorithm, proving that composite numbers can be engineered to mimic primes with high fidelity for a significant range of bases.