In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and
(where mod refers to the modulo operation).
The motivation for this definition is the fact that all prime numbers p satisfy the above equation which can be deduced from Fermat's little theorem. Fermat's theorem asserts that if p is prime, and coprime to a, then ap−1 ≡ 1 (mod p). Suppose that p>2 is prime, then p can be expressed as 2q + 1 where q is an integer. Thus, a(2q+1) − 1 ≡ 1 (mod p), which means that a2q − 1 ≡ 0 (mod p). This can be factored as (aq − 1)(aq + 1) ≡ 0 (mod p), which is equivalent to a(p−1)/2 ≡ ±1 (mod p).
The equation can be tested rather quickly, which can be used for probabilistic primality testing. These tests are twice as strong as tests based on Fermat's little theorem.
Every Euler pseudoprime is also a Fermat pseudoprime. It is not possible to produce a definite test of primality based on whether a number is an Euler pseudoprime because there exist absolute Euler pseudoprimes, numbers which are Euler pseudoprimes to every base relatively prime to themselves. The absolute Euler pseudoprimes are a subset of the absolute Fermat pseudoprimes, or Carmichael numbers, and the smallest absolute Euler pseudoprime is 1729 = 7×13×19.
The slightly stronger condition that
where n is an odd composite, the greatest common divisor of a and n equals 1, and (a/n) is the Jacobi symbol, is the more common definition of an Euler pseudoprime. See, for example, page 115 of the book by Koblitz listed below, page 90 of the book by Riesel, or page 1003 of. [1] A discussion of numbers of this form can be found at Euler–Jacobi pseudoprime. There are no absolute Euler–Jacobi pseudoprimes. [1] : p. 1004
A strong probable prime test is even stronger than the Euler-Jacobi test but takes the same computational effort. Because of this advantage over the Euler-Jacobi test, prime-testing software is often based on the strong test.
function EulerTest(k) a = 2 if k == 1 then return falseelseif k == 2 then return trueelse m = modPow(a,(k-1)/2,k) if (m == 1) or (m == k-1) thenreturn trueelsereturn falseendendend
n | Euler pseudoprimes to base n |
1 | 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 115, 117, 119, 121, 123, 125, 129, 133, 135, 141, 143, 145, 147, 153, 155, 159, 161, 165, 169, 171, 175, 177, 183, 185, 187, 189, 195, 201, 203, 205, 207, 209, 213, 215, 217, 219, 221, 225, 231, 235, 237, 243, 245, 247, 249, 253, 255, 259, 261, 265, 267, 273, 275, 279, 285, 287, 289, 291, 295, 297, 299, ... (all odd composites) |
2 | 341, 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 5461, 6601, 8321, 8481, ... |
3 | 121, 703, 1541, 1729, 1891, 2465, 2821, 3281, 4961, 7381, 8401, 8911, ... |
4 | 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ... |
5 | 217, 781, 1541, 1729, 5461, 5611, 6601, 7449, 7813, ... |
6 | 185, 217, 301, 481, 1111, 1261, 1333, 1729, 2465, 2701, 3421, 3565, 3589, 3913, 5713, 6533, 8365, ... |
7 | 25, 325, 703, 817, 1825, 2101, 2353, 2465, 3277, 4525, 6697, 8321, ... |
8 | 9, 21, 65, 105, 133, 273, 341, 481, 511, 561, 585, 1001, 1105, 1281, 1417, 1541, 1661, 1729, 1905, 2047, 2465, 2501, 3201, 3277, 3641, 4033, 4097, 4641, 4681, 4921, 5461, 6305, 6533, 6601, 7161, 8321, 8481, 9265, 9709, ... |
9 | 91, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ... |
10 | 9, 33, 91, 481, 657, 1233, 1729, 2821, 2981, 4187, 5461, 6533, 6541, 6601, 7777, 8149, 8401, ... |
11 | 133, 305, 481, 645, 793, 1729, 2047, 2257, 2465, 4577, 4921, 5041, 5185, 8113, ... |
12 | 65, 91, 133, 145, 247, 377, 385, 1649, 1729, 2041, 2233, 2465, 2821, 3553, 6305, 8911, 9073, ... |
13 | 21, 85, 105, 561, 1099, 1785, 2465, 5149, 5185, 7107, 8841, 8911, 9577, 9637, ... |
14 | 15, 65, 481, 781, 793, 841, 985, 1541, 2257, 2465, 2561, 2743, 3277, 5185, 5713, 6533, 6541, 7171, 7449, 7585, 8321, 9073, ... |
15 | 341, 1477, 1541, 1687, 1729, 1921, 3277, 6541, 9073, ... |
16 | 15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8481, 8695, 8911, 9061, 9131, 9211, 9605, 9919, ... |
17 | 9, 91, 145, 781, 1111, 1305, 1729, 2149, 2821, 4033, 4187, 5365, 5833, 6697, 7171, ... |
18 | 25, 49, 65, 133, 325, 343, 425, 1105, 1225, 1369, 1387, 1729, 1921, 2149, 2465, 2977, 4577, 5725, 5833, 5941, 6305, 6517, 6601, 7345, ... |
19 | 9, 45, 49, 169, 343, 561, 889, 905, 1105, 1661, 1849, 2353, 2465, 2701, 3201, 4033, 4681, 5461, 5713, 6541, 6697, 7957, 8145, 8281, 8401, 9997, ... |
20 | 21, 57, 133, 671, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2761, 3201, 5461, 5473, 5713, 5833, 6601, 6817, 7999, ... |
21 | 65, 221, 703, 793, 1045, 1105, 2465, 3781, 5185, 5473, 6541, 7363, 8965, 9061, ... |
22 | 21, 69, 91, 105, 161, 169, 345, 485, 1183, 1247, 1541, 1729, 2041, 2047, 2413, 2465, 2821, 3241, 3801, 5551, 7665, 9453, ... |
23 | 33, 169, 265, 341, 385, 481, 553, 1065, 1271, 1729, 2321, 2465, 2701, 2821, 3097, 4033, 4081, 4345, 4371, 4681, 5149, 6533, 6541, 7189, 7957, 8321, 8651, 8745, 8911, 9805, ... |
24 | 25, 175, 553, 805, 949, 1541, 1729, 1825, 1975, 2413, 2465, 2701, 3781, 4537, 6931, 7501, 9085, 9361, ... |
25 | 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ... |
26 | 9, 25, 27, 45, 133, 217, 225, 475, 561, 589, 703, 925, 1065, 2465, 3325, 3385, 3565, 3825, 4741, 4921, 5041, 5425, 6697, 8029, 9073, ... |
27 | 65, 121, 133, 259, 341, 365, 481, 703, 1001, 1541, 1649, 1729, 1891, 2465, 2821, 2981, 2993, 3281, 4033, 4745, 4921, 4961, 5461, 6305, 6533, 7381, 7585, 8321, 8401, 8911, 9809, 9841, 9881, ... |
28 | 9, 27, 145, 261, 361, 529, 785, 1305, 1431, 2041, 2413, 2465, 3201, 3277, 4553, 4699, 5149, 7065, 8321, 8401, 9841, ... |
29 | 15, 21, 91, 105, 341, 469, 481, 793, 871, 1729, 1897, 2105, 2257, 2821, 4371, 4411, 5149, 5185, 5473, 5565, 6097, 7161, 8321, 8401, 8421, 8841, ... |
30 | 49, 133, 217, 341, 403, 469, 589, 637, 871, 901, 931, 1273, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 4081, 4097, 5729, 6031, 6061, 6097, 6409, 6817, 7657, 8023, 8029, 8401, 9881, ... |
n | Least EPSP | n | Least EPSP | n | Least EPSP | n | Least EPSP |
1 | 9 | 33 | 545 | 65 | 33 | 97 | 21 |
2 | 341 | 34 | 21 | 66 | 65 | 98 | 9 |
3 | 121 | 35 | 9 | 67 | 33 | 99 | 25 |
4 | 341 | 36 | 35 | 68 | 25 | 100 | 9 |
5 | 217 | 37 | 9 | 69 | 35 | 101 | 25 |
6 | 185 | 38 | 39 | 70 | 69 | 102 | 133 |
7 | 25 | 39 | 133 | 71 | 9 | 103 | 51 |
8 | 9 | 40 | 39 | 72 | 85 | 104 | 15 |
9 | 91 | 41 | 21 | 73 | 9 | 105 | 451 |
10 | 9 | 42 | 451 | 74 | 15 | 106 | 15 |
11 | 133 | 43 | 21 | 75 | 91 | 107 | 9 |
12 | 65 | 44 | 9 | 76 | 15 | 108 | 91 |
13 | 21 | 45 | 133 | 77 | 39 | 109 | 9 |
14 | 15 | 46 | 9 | 78 | 77 | 110 | 111 |
15 | 341 | 47 | 65 | 79 | 39 | 111 | 55 |
16 | 15 | 48 | 49 | 80 | 9 | 112 | 65 |
17 | 9 | 49 | 25 | 81 | 91 | 113 | 21 |
18 | 25 | 50 | 21 | 82 | 9 | 114 | 115 |
19 | 9 | 51 | 25 | 83 | 21 | 115 | 57 |
20 | 21 | 52 | 51 | 84 | 85 | 116 | 9 |
21 | 65 | 53 | 9 | 85 | 21 | 117 | 49 |
22 | 21 | 54 | 55 | 86 | 65 | 118 | 9 |
23 | 33 | 55 | 9 | 87 | 133 | 119 | 15 |
24 | 25 | 56 | 33 | 88 | 87 | 120 | 77 |
25 | 217 | 57 | 25 | 89 | 9 | 121 | 15 |
26 | 9 | 58 | 57 | 90 | 91 | 122 | 33 |
27 | 65 | 59 | 15 | 91 | 9 | 123 | 85 |
28 | 9 | 60 | 341 | 92 | 21 | 124 | 25 |
29 | 15 | 61 | 15 | 93 | 25 | 125 | 9 |
30 | 49 | 62 | 9 | 94 | 57 | 126 | 25 |
31 | 15 | 63 | 341 | 95 | 141 | 127 | 9 |
32 | 25 | 64 | 9 | 96 | 65 | 128 | 49 |
In number theory, a Carmichael number is a composite number , which in modular arithmetic satisfies the congruence relation:
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
Fermat's little theorem states that if p is a prime number, then for any integer a, the number is an integer multiple of p. In the notation of modular arithmetic, this is expressed as
In number theory, Euler's theorem states that, if n and a are coprime positive integers, and is Euler's totient function, then a raised to the power is congruent to 1 modulo n; that is
In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form
In number theory, an odd integer n is called an Euler–Jacobi probable prime to base a, if a and n are coprime, and
In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.
In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite (called pseudoprimes), the condition is generally chosen in order to make such exceptions rare.
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.
The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test.
In number theory, a Wieferich prime is a prime number p such that p2 divides 2p − 1 − 1, therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides 2p − 1 − 1. Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's Last Theorem, at which time both of Fermat's theorems were already well known to mathematicians.
The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967 (see Theorem E in the paper). This test has been largely superseded by the Baillie–PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. The Solovay–Strassen test is essentially an Euler–Jacobi pseudoprime test.
Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.
A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes".
In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:
In number theory, a Frobenius pseudoprime is a pseudoprime, whose definition was inspired by the quadratic Frobenius test described by Jon Grantham in a 1998 preprint and published in 2000. Frobenius pseudoprimes can be defined with respect to polynomials of degree at least 2, but they have been most extensively studied in the case of quadratic polynomials.
In mathematics, Pépin's test is a primality test, which can be used to determine whether a Fermat number is prime. It is a variant of Proth's test. The test is named for a French mathematician, Théophile Pépin.
The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines whether a number is composite or is a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff.
A pseudoprime is a probable prime that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.