Why 561 Passes Fermat's Test

Published December 17, 2024 · Revised July 24, 2026

The Fermat primality test fails on Carmichael numbers – composites that pass for every coprime base. Miller-Rabin avoids that universal blind spot by inspecting the squaring chain that leads to Fermat’s result; Rabin and Monier independently proved that at most one quarter of the bases are strong liars for any odd composite. The fixed Baillie–PSW procedure combines a base-2 strong test with a Lucas test. It has no known counterexample, but that empirical record is not a proof.

Is 561 prime? Trial division says no ( ). But check : you get 1, exactly what a prime would give. Try : also 1. Try any base coprime to 561: always 1. Every test of this form says 561 is prime.

561 is the smallest number with this property. It passes Fermat’s congruence for every base coprime to it, so repeating that test cannot resolve the error.

# Background

Given an arbitrary integer , how do you decide whether it’s prime?

The stakes are not abstract. RSA key generation requires finding two large primes and , often 1024 bits each for a 2048-bit modulus. Finite-field Diffie–Hellman systems also rely on suitable primes. Most deployed elliptic-curve systems use standardized fields instead of generating fresh primes per key, so primality testing is therefore part of key and parameter generation rather than every public-key operation.

# Trial division

The oldest approach: to test whether is prime, try dividing it by every integer from 2 up to . If none divide evenly, is prime.

This works because if with , then . So we only need to check potential factors up to the square root. After checking 2, even divisors can be skipped. Testing only primes removes more work; the Sieve of Eratosthenes can generate them for moderate bounds.

The complexity is divisions. For a 10-digit number, that is roughly 100,000 divisions – fast on current hardware. For a 300-digit number (a typical RSA prime), has 150 digits. There are approximately candidate divisors. At divisions per second, this would take about seconds. The universe is approximately seconds old.

The issue is that is exponential in the bit-length of . If has bits, then , and we need divisions. A polynomial-time algorithm would need operations for some constant . Trial division is correct and deterministic, but for cryptographic sizes it is computationally infeasible. This is not a constant-factor problem that faster hardware will solve. The gap is exponential.

# The probabilistic trade

The gap between cryptographic input sizes and trial division motivates randomized testing: accept a bounded probability of a false-prime answer.

A probabilistic primality test gives one of two answers: “definitely composite” or “probably prime.” In the language of randomized algorithms, this is a Monte Carlo algorithm: it always terminates in bounded time, but the answer might be wrong.The contrast is a Las Vegas algorithm, which always gives the correct answer but whose runtime is a random variable. ECPP (discussed below) is closer to the Las Vegas model: it always produces a correct certificate, but finding one can take unpredictable time. The naming is a gambling joke from the 1970s. The “probably” comes with a quantifiable error bound. An engineering system may accept a bound such as as negligible, but it remains different from a proof.

There are several probability spaces here:

• for one fixed odd composite, at most of Miller–Rabin bases are strong liars;
• choosing independent uniform bases therefore gives worst-case error at most for that candidate;
• drawing candidates from a random key-generation process supports sharper average-case bounds, but those depend on that distribution;
• a primality certificate is deterministic evidence and has no randomized false-prime probability.

The challenge is building a test with: (1) an error probability that decreases exponentially with the number of iterations, and (2) no blind spots: no class of composites that always fools the test regardless of how many iterations you run.

The first condition is achievable: run the test multiple times with independent random choices, and error probabilities multiply (shrinking exponentially). The Fermat test fails the second condition because Carmichael numbers form a universal blind spot for coprime bases.

# The modular setting

The tests below work with remainders rather than the full integers. The notation

means that divides , so and have the same remainder after division by . Addition and multiplication preserve this equivalence, which lets an implementation reduce after every operation instead of constructing an enormous power first.

The distinction between prime and composite moduli is structural. If is prime, every nonzero residue modulo has a multiplicative inverse; the residues form the field . For composite , some nonzero residues have no inverse and zero divisors can appear. The condition says that the chosen base is invertible modulo . Fermat, Miller–Rabin, and Lucas tests probe increasingly specific consequences of that prime-field structure.

# Fermat’s Little Theorem

In 1640, Pierre de Fermat stated a theorem that later became a basis for primality tests:

for any prime and integer not divisible by .

Consider the nonzero residues modulo . Multiplying each by (with ) permutes this set: the map is a bijection on . Therefore:

The left side is and the right side is . Since is prime, is invertible mod , giving .

The contrapositive gives us a primality test: if for some coprime to , then is definitely composite.

# The Fermat Primality Test

This observation leads to a probabilistic test:

1. Pick a random base with
2. Compute
3. If the result is not 1, is composite
4. If the result is 1, is probably prime

Step 2 uses modular exponentiation by repeated squaring, which runs in multiplications mod , each costing with schoolbook multiplication. Total: . The running time is polynomial in the bit length rather than exponential in it.

Note an asymmetry: the test can prove compositeness (if , is definitely composite) but can only suggest primality (if , might be prime). The test has no false-composite answers; its one-sided error is a false probable-prime answer.

The limitation is that some composite numbers pass this test.

# Pseudoprimes

A composite number is called a Fermat pseudoprime to base if .

For example, is a pseudoprime to base 2:

Why does this happen? The order of 2 modulo 11 is 10 (by Fermat’s little theorem, ), and the order of 2 modulo 31 is 5 (since ). Since and , we get modulo both 11 and 31, hence modulo by the Chinese Remainder Theorem.

This means the Fermat test with base 2 incorrectly identifies 341 as “probably prime.”

The base-2 pseudoprimes below 1000 are 341, 561, and 645. There are 245 below , but their rarity is deceptive.12 It might suggest that testing multiple bases would catch all composites: if is a pseudoprime to base 2, surely it fails for base 3? Often yes. 341 fails for base 3. But 561, as the opening promised, does not fail for any base coprime to it.

# Carmichael Numbers

A composite number that is a pseudoprime to every base coprime to it is called a Carmichael number – and 561 is the smallest.15Vaclav Simerka found several examples in 1885, publishing in Casopis pro pestovani mathematiky a fysiky, a Czech-language journal with limited circulation outside Bohemia. His priority was recovered over a century later by Kral, Loebl, and Matousek (2001). In 1899, Alwin Korselt characterized them: a composite is a Carmichael number if and only if:

1. The number is square-free (no repeated prime factors)
2. For every prime dividing , we have

Korselt knew of no examples. In 1910, Robert D. Carmichael independently discovered 561. Why does it work? , and:

• divides 560
• divides 560
• divides 560

The Fermat test fails completely on Carmichael numbers: no choice of base (coprime to ) will reveal their compositeness. For the Fermat test, Carmichael numbers are an unconditional blind spot. No amount of repetition helps.

Reproduce this figure

Korselt’s criterion has an intuitive interpretation: it says that “pretends” to be prime by having its prime factors’ orders all divide . The Chinese Remainder Theorem then forces for all coprime to . The deception is structural, not coincidental.

# How many exist?

For decades, mathematicians wondered whether there are infinitely many Carmichael numbers. In 1994, Alford, Granville, and Pomerance proved there are:6 for sufficiently large , the count up to exceeds . That exponent is a proved lower bound, not an estimate of the true density.

# Solovay-Strassen: The First Probabilistic Test

Carmichael numbers force a choice: find a stronger necessary condition for primality, or accept that the Fermat test has an unconditional blind spot. In 1977, Robert Solovay and Volker Strassen found one.1 Their test compares modular exponentiation with quadratic-residue information through the Euler criterion.

Lemma (Euler criterion). For an odd prime and :

where is the Legendre symbol ( if is a quadratic residue mod , otherwise).

Proof sketch. Since is cyclic of order , we have , so is a square root of 1, hence . Write for a generator . Then . When is even, this is , so is a quadratic residue. When is odd, (the unique element of order 2), so is a non-residue.

The Solovay-Strassen test: pick a random , compute both and the Jacobi symbol (which can be computed in by reciprocity, without knowing the factorization of ). If they disagree, is composite.

Why this breaks the Carmichael barrier: a Carmichael number satisfies for all coprime to , but this does not force . The Jacobi symbol factors multiplicatively over the prime factors of , while the power does not decompose the same way. Solovay and Strassen proved that for any composite , at least half of all bases in are witnesses – the Euler criterion fails for them. This gives a error bound per round, worse than Miller-Rabin’s but sufficient to bypass Carmichael numbers entirely.

# Why Primes Are Algebraically Special

The Fermat test checks one property of primes: . Miller’s test checks additional structure in the squaring chain: not just what the final value is, but how it got there. Fermat asks “is the answer 1?” Miller asks “what is the square root of that 1?” In a prime field, the only square roots of 1 are . In a composite ring, there can be others, and finding one proves compositeness. To understand why, we need a fact about the multiplicative group modulo a prime.

When is prime, under multiplication is a cyclic group of order . Every element is a power of some generator . A consequence: the equation has exactly two solutions: and . This is because , and in a field, each factor has at most one root.

For composite , is not cyclic in general – by the Chinese Remainder Theorem, it decomposes as a product of the groups for each prime factor. This product structure creates extra square roots of unity: elements with but . For example, , but .

These non-trivial square roots cannot exist modulo a prime but can exist modulo composites. Miller’s test detects such a root when it occurs in the squaring chain.

# Strong Pseudoprimes and Miller’s Test

In 1976, Gary Miller observed that we can strengthen the Fermat test by exploiting the algebraic structure above.2

Write where is odd. For a prime and base coprime to , one of the following must hold:

or

Why must one of these hold? Start from Fermat: . Now consider the squaring chain:

The last term is 1. Each term is the square of the previous. Working backwards from : if , then is a square root of 1 modulo . In a field (which is, since is prime), the polynomial has at most two roots: and . So either the previous term is also 1 (and we continue backwards) or it is (and we stop). Eventually we either reach or find some .

For composite , the ring can contain additional square roots of unity. For example, modulo , we have , although . Miller’s test uses the appearance of such a root as a compositeness witness.

Worked example: , . Recall that 341 passes the Fermat test for base 2. Write , so and . The squaring chain is:

Reproduce this figure

The chain went from 32 to 1 in one squaring. But and (since ). So 32 is a non-trivial square root of 1 modulo 341, a witness that cannot exist modulo a prime. Miller’s test identifies 341 as composite. The Fermat test missed this because it only checks the final value , discarding the information in the intermediate steps.

A composite number that passes this stronger test for base is called a strong pseudoprime to base . Unlike the Fermat test, there are no “strong Carmichael numbers”: no composite passes for all bases.

# The Miller-Rabin Test

In 1980, Michael Rabin made Miller’s test probabilistic and proved the following bound:3 for any composite , at most of bases in are strong liars (bases for which passes the strong test). Louis Monier independently proved the same bound the same year.

Theorem (Rabin and Monier, 1980).3 If is an odd composite, the number of strong liars in is at most .

Proof idea. Write and factor into prime powers. By the Chinese Remainder Theorem, a passing base must make the same squaring-chain condition hold in every prime-power component: either the initial value is 1 everywhere, or all components reach at the same stage. Counting the compatible residue classes across those components gives Monier’s exact liar formula and Rabin’s one-quarter bound. The counting is subtler than saying “the strong liars form a subgroup”: in general, the passing set need not be closed under multiplication.

This is the proof boundary used by the rest of the article: the square-root mechanism is derived above, while the exact residue-class count and the one-quarter theorem are imported from Rabin and Monier.

This means:

• Each iteration has at most probability of being fooled
• After iterations with independent random bases, the error probability is at most
• With 40 iterations, the worst-case bound is , about

The candidate-generation probability space admits sharper results. Damgård, Landrock, and Pomerance11 analyze a loop that repeatedly draws uniform odd -bit candidates until one passes Miller–Rabin rounds, and bound the probability that the returned candidate is composite. Their examples include and . These are not conditional error bounds for a uniformly drawn odd composite, and they depend on the stated candidate-generation process.

Unlike the Fermat test, Miller-Rabin has no Carmichael-style universal blind spot. For every odd composite, including every Carmichael number, at least three quarters of the candidate bases are witnesses.

# Implementation

Modular exponentiation by repeated squaring makes each round efficient. Here is a complete Miller-Rabin test in Python:

import secrets
def is_probable_prime(n, k=40):
    """Miller-Rabin with k rounds. False = composite, True = probably prime."""
    if n < 2: return False
    if n < 4: return True
    if n % 2 == 0: return False
    # Write n - 1 = 2^s * d with d odd
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = 2 + secrets.randbelow(n - 3)
        x = pow(a, d, n)          # a^d mod n
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)      # square mod n
            if x == n - 1:
                break
        else:
            return False           # composite witness found
    return True

Python’s built-in three-argument pow(a, d, n) performs modular exponentiation without first materializing , so the example remains practical for large inputs. secrets is used because the worst-case calculation assumes bases are sampled independently and uniformly; random is a deterministic simulation generator, not a cryptographic source. Forty rounds give an 80-bit worst-case bound. Real key-generation standards choose test counts from the candidate size, candidate source, desired strength, and whether a Lucas test follows; 40 is a pedagogical default, not a universal production rule.

The for/else construct is Python-specific: the else clause executes only if the inner for loop completes without break, meaning none of the squarings produced , so is a witness to compositeness.

# Deterministic Variants

# Miller’s test under GRH

Miller’s original 1976 test was deterministic, conditional on the extended Riemann hypothesis for relevant Dirichlet -functions.2 Miller established a polynomial witness bound; the explicit statement that a composite has a witness below follows from Bach’s later bounds.16 Testing all bases below that limit gives a deterministic polynomial-time test conditional on the hypothesis.

This form of the extended or generalized Riemann hypothesis remains unproved.

# Known deterministic witness sets

Even without ERH, exhaustive computation has established that specific small sets of bases suffice for bounded ranges. These results turn Miller-Rabin into a deterministic test for numbers below each bound:

Bound on	Sufficient bases

The last row is a convenient seven-base result for unsigned 64-bit integers; the entries need not themselves be prime. The set comes from Jim Sinclair’s exhaustive computation, summarized with implementation discussion on MathOverflow. It makes Miller–Rabin deterministic on that bounded domain when the algorithm handles a listed base outside correctly, including the case where its residue modulo is zero. It should not be projected onto current library implementations without checking their source: for example, Go’s math/big uses a different combination of small-prime filtering, pseudorandom Miller–Rabin rounds, and a Lucas test.

Source boundary for the deterministic-base table

The first two rows are classical strong-pseudoprime thresholds. The seven-base 64-bit row is a published computational result rather than a value generated by this post; the linked MathOverflow record identifies the computation and its provenance.

The smallest strong pseudoprime to base 2 is 2047 – which is why base alone suffices below that threshold.

# BPSW: a fixed probable-prime test

Randomized Miller–Rabin can drive a proved error bound down by adding independent rounds. The Baillie–PSW test, introduced through work by Robert Baillie,4 Carl Pomerance, John Selfridge, and Samuel Wagstaff,5 instead fixes two complementary checks:

1. A Miller-Rabin test to base 2
2. A strong Lucas probable prime test (with a specific parameter selection method)

A composite that slips through the base-2 strong test often fails the Lucas test. The two components probe different recurrence structures, but their pseudoprime sets are not proved independent or disjoint. BPSW is therefore a deterministic procedure that returns a probable-prime result, not a randomized algorithm with a bound that can be multiplied across rounds.

The Lucas test works in a different algebraic setting. Given parameters and with discriminant , define

If and are the roots of , then

These formulas explain why a quadratic extension enters. For an odd prime not dividing , with Jacobi symbol , the two roots are not in , but the Frobenius map swaps them in . Hence and , which forces .

The strong Lucas test keeps the path to that zero. More generally write

with odd. A prime must satisfy

This is the Lucas analogue of retaining Miller–Rabin’s squaring chain rather than checking only its endpoint. Selfridge’s parameter rule tries until , then takes and . A nontrivial found during this search is already a factor witness.

The distinct Miller–Rabin and Lucas structures explain why the pair is empirically effective, but do not prove that the fixed pair accepts no composite.

No BPSW counterexample is known. The original 1980 paper offered a $30 reward for one.5 In 2021, Baillie, Fiori, and Wagstaff14 offered $2,000 for a counterexample to a strengthened variant. The bounty and the size of searched ranges are useful empirical evidence, not a correctness theorem.

BPSW requires one base-2 strong test and one Lucas computation, giving it a fixed computational profile. Libraries vary in their exact variant and in whether they add randomized Miller–Rabin rounds.

# Beyond Miller-Rabin

Randomized Miller–Rabin and fixed probable-prime procedures such as BPSW do not produce proofs. For primality certificates, mathematical proofs, or auditable records, we need a test that proves primality unconditionally.

# AKS: unconditional polynomial time

In 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena proved that primality is in P:7The preprint circulated in August 2002. The journal publication in Annals of Mathematics appeared in 2004. Dates in citations refer to journal publication; “2002” in prose refers to when the result became known. there exists a deterministic polynomial-time algorithm that decides primality without any unproven hypothesis. AKS was the first test that is simultaneously general (works for all integers), polynomial-time, deterministic, and unconditionally correct. Trial division is deterministic and correct but exponential in input length; Miller–Rabin is fast but randomized unless paired with a bounded-domain witness theorem or an unproved hypothesis; ECPP produces checkable proofs but its practical running-time analysis is heuristic.

Kayal and Saxena were BTech students of Agrawal at IIT Kanpur. The preprint circulated in August 2002 and prompted early variants by Berrizbeitia and Bernstein; later work, including Lenstra–Pomerance, improved the complexity bound.

The original algorithm runs in time. Lenstra and Pomerance8 improved this to in 2005. The key idea starts from a classical observation: if is prime, then the polynomial identity

holds in for all (this is essentially the Frobenius endomorphism). For composite , this identity generally fails. But checking it directly requires working with a polynomial of degree – which is as expensive as trial division.

AKS’s insight is to choose such that the multiplicative order , then check the identity modulo : verify in . The polynomials then have degree at most .

The key implication uses all of these conditions: the order bound on ; failure of the perfect-power test; absence of a factor at most ; and for . The proof constructs a group of residues in generated by and obtains incompatible lower and upper bounds on unless is prime. The total number of checks is polynomial in .

The group-size contradiction is an imported correctness result here. The article states the conditions it consumes and the mechanism of the proof, but does not reconstruct the lower and upper bounds on .

AKS is not used in ordinary primality-testing pipelines. Bounded deterministic Miller–Rabin, randomized probable-prime tests, and ECPP are much faster on the input sizes engineers actually encounter. AKS is often called a “galactic algorithm”: its polynomial guarantee is theoretically decisive, but not a practical speed claim. Its significance is settling the complexity question.

# ECPP: practical primality certificates

Elliptic Curve Primality Proving (ECPP) was developed by Shafi Goldwasser and Joe Kilian in 1986,10 and refined into a practical algorithm by A. O. L. Atkin and Francois Morain in 1993.9 It runs in heuristic time and produces a primality certificate – a compact proof that anyone can verify much faster than it took to produce.

The core idea uses elliptic curves over . Given a point on an elliptic curve modulo , if we can show that the group order has a large prime factor , and certain conditions hold, then either is prime or has a very small factor (which we can check by trial division). The problem then reduces to proving is prime, a smaller instance of the same problem. This recursive structure terminates quickly.

The certificate is an Atkin–Goldwasser–Kilian–Morain certificate: a chain of elliptic curves and points that witnesses primality at each recursive step. Verification runs in polynomial time and does not require trusting the prover’s computation. This is the key distinction from probable-prime tests: ECPP says “here is a proof; check it yourself.”

The elliptic-curve order criterion and the certificate verifier are imported here rather than derived. The reconstructible claim is the evidence boundary: ECPP emits a deterministic certificate whose verification is separate from the heuristic search used to find it.

ECPP has proved general-form primes with tens of thousands of digits. That is a different task from proving primes of special form: Mersenne numbers, for example, admit the deterministic Lucas–Lehmer test.

# Comparison

Test	Type	Complexity	Certainty	Practical use
Trial division	Deterministic		Proven	Small only
Fermat	Probabilistic		Probable (with blind spots)	Not used alone
Solovay-Strassen	Probabilistic		Error	Superseded by Miller-Rabin
Miller-Rabin	Probabilistic		Error	General purpose
BPSW	Fixed probable-prime test		No known counterexample	Fast composite screen
Miller (GRH)	Deterministic (conditional)		Proven if ERH holds	Theoretical
AKS	Deterministic		Proven	Not practical
ECPP	Certificate-producing	heuristic	Proven + certificate	Large general-form proven primes

These tests exploit progressively more algebraic structure. The Fermat test checks an exponent identity in the multiplicative group. Miller–Rabin retains the repeated-squaring path and checks where it can first reach 1.Writing separates the odd part of the exponent from its power-of-two part. The chain follows successive squaring inside the subgroup generated by ; it is not necessarily the whole Sylow 2-subgroup. The Lucas test uses a second-order recurrence. ECPP uses the group structure of elliptic curves.

# How Real Systems Test Primality

This section is version-stamped July 24, 2026 because library pipelines change.

• Go math/big first filters small factors. ProbablyPrime(n) then performs n+1 pseudorandom Miller–Rabin rounds, including a forced base-2 round, followed by an almost-extra-strong Lucas test. With n=0, it performs the fixed base-2-plus-Lucas screen.
• OpenSSL 3.6.3 sieves generated candidates with small-prime residues, then runs random Miller–Rabin rounds: 64 for candidates through 2048 bits and 128 above that. This path does not add a Lucas test.
• GMP 6.3.0’s mpz_probab_prime_p performs trial divisions and a BPSW screen, then runs reps - 24 Miller–Rabin tests when that number is positive.
• FIPS 186-5 permits either repeated Miller–Rabin alone or Miller–Rabin followed by a Lucas test. Counts depend on candidate type, bit length, target error, and which alternative is used. For uniformly random 1024-bit and candidates, Table B.1 specifies four Miller–Rabin-only rounds for a target and five for .

Those small FIPS counts are posterior statements under a random-candidate model, not the same quantity as Rabin’s bound conditional on an arbitrary fixed composite.

The prime number theorem also needs the candidate space stated correctly. Near , an unrestricted integer is prime with probability about . If generation has already forced the candidate odd, the probability is about , so the expected number of odd candidates is , not 710. Small-prime sieving cheaply rejects most of those before a large modular exponentiation.

The numerical claims above – the pseudoprime counts, the 341 squaring chain, the 40-round bound, and the expected odd-candidate count – are checked together with:

Reproduce the numerical checks

verification program uv run verify_numbers.py

# Timing side channels

Candidate generation is normally variable-time: standards and implementations allow early rejection of small-factor composites. That alone does not mean total runtime reveals the accepted prime or makes the final modulus easy to factor. The security question is narrower: can an observer measure cache, branch, or arithmetic behavior that depends on secret candidate values closely enough to recover them?

That threat is real in some environments. Co-located cache attacks have recovered RSA keys from secret-dependent GCD and modular-exponentiation code paths during key generation. Defenses therefore belong at the operations and boundaries the threat model exposes: constant-time big-integer primitives where secret operands matter, avoidance of secret-indexed memory access, isolation from hostile co-tenants, and blinding or hardened library routines where appropriate. “Every rejection takes identical wall time” is neither a general requirement nor how OpenSSL’s search loop is structured.13

# Open Problems

# The BPSW question

The central open problem in practical primality testing: does a BPSW counterexample exist?

Heuristics and extensive computation suggest that a counterexample, if one exists, is rare. Neither kind of evidence determines where the first one must occur.

Baillie, Fiori, and Wagstaff offered a $2,000 bounty for a proof or a counterexample.14 If no counterexample exists, proving this would likely require new techniques in analytic number theory. If one exists, finding it would likely require new techniques in constructive algebra.

BPSW is widely used as a fast fixed screen. No counterexample is known, and there is no proof that none exists.

# References

[1] Solovay, R. & Strassen, V. (1977). “A Fast Monte-Carlo Test for Primality.” SIAM Journal on Computing, 6(1), 84-85. ↩

[2] Miller, G. L. (1976). “Riemann’s Hypothesis and Tests for Primality.” Journal of Computer and System Sciences, 13(3), 300-317. ↩

[3] Rabin, M. O. (1980). “Probabilistic Algorithm for Testing Primality.” Journal of Number Theory, 12(1), 128-138. ↩

[4] Baillie, R. & Wagstaff, S. S. (1980). “Lucas Pseudoprimes.” Mathematics of Computation, 35(152), 1391-1417. ↩

[5] Pomerance, C., Selfridge, J. L. & Wagstaff, S. S. (1980). “The Pseudoprimes to 25 x 10^9.” Mathematics of Computation, 35(151), 1003-1026. ↩

[6] Alford, W. R., Granville, A. & Pomerance, C. (1994). “There Are Infinitely Many Carmichael Numbers.” Annals of Mathematics, 139(3), 703-722. ↩

[7] Agrawal, M., Kayal, N. & Saxena, N. (2004). “PRIMES Is in P.” Annals of Mathematics, 160(2), 781-793. ↩

[8] Lenstra, H. W. & Pomerance, C. (2019). “Primality Testing with Gaussian Periods.” Journal of the European Mathematical Society, 21(4), 1229–1269. (Manuscript circulated 2005.) ↩

[9] Atkin, A. O. L. & Morain, F. (1993). “Elliptic Curves and Primality Proving.” Mathematics of Computation, 61(203), 29-68. ↩

[10] Goldwasser, S. & Kilian, J. (1986). “Almost All Primes Can Be Quickly Certified.” Proceedings of the 18th STOC, 316-329. ↩

[11] Damgård, I., Landrock, P. & Pomerance, C. (1993). “Average Case Error Estimates for the Strong Probable Prime Test.” Mathematics of Computation, 61(203), 177-194. ↩

[12] Pomerance, C. (1981). “On the Distribution of Pseudoprimes.” Mathematics of Computation, 37(156), 587-593. ↩

[13] Cabrera Aldaya, A., Pereida García, C., Alvarez Tapia, L. M., & Brumley, B. B. (2019). “Cache-Timing Attacks on RSA Key Generation.” IACR Transactions on Cryptographic Hardware and Embedded Systems 2019(4), 213–242. ↩

[14] Baillie, R., Fiori, A. & Wagstaff, S. S. (2021). “Strengthening the Baillie-PSW Primality Test.” Mathematics of Computation, 90(330), 1931-1955. ↩

[15] Kral, D., Loebl, M. & Matousek, J. (2001). “Simerka as a predecessor of Carmichael.” Expositiones Mathematicae, 19(4), 377–381. ↩

[16] Bach, E. (1990). “Explicit Bounds for Primality Testing and Related Problems.” Mathematics of Computation, 55(191), 355–380. ↩

← A Difference Table Is a Discrete Derivative Regions for Set Inclusion →