Strong Pseudoprimes vs. Euler Pseudoprimes: The Connection

There are two important connections between strong pseudoprimes and Euler pseudoprimes:

• If \( n \) is a strong pseudoprime to base \( b \), then it is also an Euler pseudoprime to the same base.
• If \( n \) is an odd composite number such that \( n \equiv 3 \pmod{4} \), then any Euler pseudoprime to base \( b \) is also a strong pseudoprime to that base.

In other words, under certain conditions, strong pseudoprimes and Euler pseudoprimes are one and the same.

This is useful because the Euler test is much simpler (and computationally cheaper) than the strong pseudoprime test. So, when \( n \equiv 3 \pmod{4} \), I can leverage the Euler test to determine if a number is a strong pseudoprime, cutting down on unnecessary calculations.

Note: When \( n \not \equiv 3 \pmod{4} \), there’s no direct correlation between the two concepts. This means some numbers may pass one test but not the other. Every strong pseudoprime is also an Euler pseudoprime, but not vice versa, as the strong pseudoprime test is more stringent. As a result, there are Euler pseudoprimes that fail to meet the strong pseudoprime criteria. Only when \( n \equiv 3 \pmod{4} \) do the two definitions align.

What’s the Difference Between Strong and Euler Pseudoprimes?

Pseudoprimes are composite numbers that mimic prime behavior under certain primality tests. Two key classes of pseudoprimes are:

• Strong pseudoprimes: These satisfy a specific exponential condition derived from the Miller-Rabin test.
• Euler pseudoprimes: These satisfy a weaker condition based on Euler’s criterion.

The key takeaway is that when \( n \equiv 3 \pmod{4} \), these two definitions are indistinguishable.

A Practical Example

The number \( n = 25 \) is a strong pseudoprime to base \( b = 7 \) because we can express \( n-1 = 25 - 1 = 24 \) as:

\[ 24 = 2^s \cdot t = 2^3 \cdot 3 \]

which gives us \( s = 3 \) and \( t = 3 \).

Now, let’s check whether it satisfies at least one of the strong pseudoprimality conditions.

1] The first condition

$$ b^t \equiv 1 \mod n $$

$$ 7^3 \equiv 18 \mod 25 $$

This condition is not met because \( 7 \neq 18 \).

2] The second condition

$$ b^{2^r t} \equiv -1 \mod n $$

$$ 7^{2^r \cdot 3} \mod 25 $$

We now check whether there exists at least one \( r \) in the range \( 0 \leq r \leq s = 3 \) such that the congruence holds as \(-1\).

$$ r = 0 \rightarrow 7^{2^0 \cdot 3} = 7^3 = 7 \not \equiv -1 \mod 25 $$

$$ r = 1 \rightarrow 7^{2^1 \cdot 3} = 7^6 = 24 \equiv -1 \mod 25 $$

Since the condition is satisfied for \( r = 1 \), we conclude:

$$ 24 \equiv -1 \mod 25 $$

Thus, \( 7^6 \) is congruent to \(-1\) modulo \( n=25 \).

Since \( 25 \) is composite (\( 25 = 5 \cdot 5 \)) but still passes the strong pseudoprimality test for base \( 7 \), we conclude that 25 is a strong pseudoprime to base 7.

Now, let’s determine whether \( n = 25 \) is also an Euler pseudoprime to base \( b = 7 \).

For this, it must satisfy the following condition:

\[ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \pmod{n} \]

\[ 7^{(25-1)/2} = 7^{12} \equiv \left( \frac{7}{25} \right) \pmod{25} \]

On the left-hand side, \( 7^{12} \) is congruent to 1 modulo 25:

$$ 7^{12} \equiv 1 \pmod{25} $$

On the right-hand side, we have the Jacobi symbol, which can be rewritten as:

$$ \left( \frac{7}{25} \right) = \left( \frac{7}{5} \right) \cdot \left( \frac{7}{5} \right) $$

Since both 7 and 5 are odd primes, this is simply the product of two Legendre symbols.

Applying Euler’s criterion to \( \left( \frac{7}{5} \right) \):

\[ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} \]

\[ \left(\frac{7}{5}\right) \equiv 7^{\frac{5-1}{2}} \pmod{5} \]

\[ \left(\frac{7}{5}\right) \equiv 7^2 \pmod{5} \]

\[ \left(\frac{7}{5}\right) \equiv 49 \pmod{5} \]

\[ \left(\frac{7}{5}\right) \equiv 4 \pmod{5} \]

Since \( 4 \equiv -1 \mod 5 \), it follows that:

\[ \left(\frac{7}{5}\right) \equiv -1 \pmod{5} \]

Thus, the Jacobi symbol evaluates to 1, as it is the product of \(-1\) and \(-1\):

$$ \left( \frac{7}{25} \right) = \left( \frac{7}{5} \right) \cdot \left( \frac{7}{5} \right) = (-1 ) \cdot (-1) = 1 $$

Since both sides of the condition are equal to 1, we have:

\[ 7^{(25-1)/2} = 7^{12} = 1 \equiv \left( \frac{7}{25} \right) \pmod{25} \]

\[ 7^{(25-1)/2} = 7^{12} = 1 \equiv 1 \pmod{25} \]

Since the Euler pseudoprimality condition is satisfied, we conclude that \( n=25 \) is also an Euler pseudoprime to base \( b = 7 \).

Example 2

Let's take \( n = 341 \) as an example.

This number is composite since \( 341 = 11 \times 31 \). It is odd and satisfies the congruence \( n \equiv 3 \pmod{4} \).

$$ 341 \equiv 3 \pmod{4} $$

In this particular case, if \( n \) is an Euler pseudoprime to a given base, then it is also a strong pseudoprime to that same base.

I'll choose base \( b = 2 \) since 2 and 341 are coprime, meaning \( \gcd(2,341) = 1 \).

Is 341 an Euler pseudoprime?

Let's check whether 341 qualifies as an Euler pseudoprime in base 2.

\[ 2^{(341-1)/2} \equiv \left( \frac{2}{341} \right) \pmod{341} \]

\[ 2^{170} \equiv \left( \frac{2}{341} \right) \pmod{341} \]

\[ (2^{85})^2 \equiv \left( \frac{2}{341} \right) \pmod{341} \]

\[ (-1)^2 \equiv \left( \frac{2}{341} \right) \pmod{341} \]

\[ 1 \equiv \left( \frac{2}{341} \right) \pmod{341} \]

Next, we compute the Jacobi symbol and find that \( \left( \frac{2}{341} \right) = 1 \).

\[ 1 \equiv 1 \pmod{341} \]

Since \( 2^{170} \equiv 1 \pmod{341} \), the Euler pseudoprime condition holds.

\[ 2^{170} \equiv 1 \pmod{341} \]

Thus, 341 is an Euler pseudoprime in base \( b = 2 \).

Is 341 also a strong pseudoprime to the same base?

Now, let's check whether 341 is also a strong pseudoprime to base 2.

We express \( 341 - 1 \) as \( 340 = 2^2 \cdot 85 \), giving us \( d = 85 \) and \( s = 2 \).

\[ 2^{85} \mod 341 \]

Using modular arithmetic, we find:

\[ 2^{85} \equiv -1 \pmod{341} \]

Since we obtained \( -1 \), the strong pseudoprime condition is satisfied, meaning 341 is also a strong pseudoprime to base \( b = 2 \).

In conclusion, the number \( 341 \) meets both criteria: it is both a strong pseudoprime and an Euler pseudoprime in base \( 2 \).

This example demonstrates that when \( n \equiv 3 \pmod{4} \), being an Euler pseudoprime is equivalent to being a strong pseudoprime in base \( b \).

Proof

If a number is a strong pseudoprime, then it is also an Euler pseudoprime in the same base

Since \( n \) is a strong pseudoprime, one of the following conditions must hold:

A] Case 1: \( b^t \equiv \pm 1 \pmod{n} \)

In this case, we have the following relation:

$$ b^{(n-1)/2} \equiv \pm 1 \pmod{n} $$

If \( b^t \equiv 1 \pmod{n} \), this property extends to every prime factor \( p \) of \( n \):

$$ b^t \equiv 1 \pmod{p} $$

This means that the multiplicative order of \( b \) modulo \( p \), denoted \( \operatorname{Gss}(p, b) \), divides \( t \) and is also a divisor of \( (p-1)/2 \).

By Euler’s criterion, we obtain \( \left( \frac{b}{p} \right) = 1 \), which implies \( \left( \frac{b}{n} \right) = 1 \). This confirms that \( n \) is an Euler pseudoprime.

B] Case 2: There exists an \( r < s \) such that \( b^{t \cdot 2^r} \equiv -1 \pmod{n} \)

Taking a prime divisor \( p \) of \( n \), we use the given property \( b^{t \cdot 2^r} \equiv -1 \pmod{p} \), which implies:

The multiplicative order of \( b \) modulo \( p \) takes the form \( \operatorname{Gss}(p,b) = 2^{r+1} s \), where \( s \) is odd.

As a result, we can write \( p \equiv 1 \pmod{2^{r+1}} \), meaning \( p = 2^{r+1} q + 1 \), which leads to the relation:

$$ \left( \frac{b}{p} \right) = (-1)^q $$

Since \( s \) is odd, we conclude that:

$$ \left( \frac{b}{p} \right) = (-1)^q $$

C] General case for \( n \)

Expressing \( n \) as the product of its prime factors \( p_i \) with exponents \( h_i \), we expand \( n \) modulo \( 2^{r+1} \), obtaining:

$$ n \equiv 1 \pmod{2^{r+1}} $$

This implies that the sum \( \sum_{i=1}^{m} h_i d_i \) is even, leading to the conclusion that the Jacobi symbol satisfies:

$$ \left( \frac{b}{n} \right) = 1 $$

By definition, this confirms that \( n \) is an Euler pseudoprime, completing the proof.

Thus, we have demonstrated that in both cases—whether \( b^t \equiv 1 \) or \( b^{t \cdot 2^r} \equiv -1 \)—the strong pseudoprime condition automatically implies the Euler pseudoprime condition.

If \( n \equiv 3 \mod 4 \), then an Euler pseudoprime is also a strong pseudoprime

Now, I’ll prove that if \( n \equiv 3 \pmod{4} \), then:

\[ n \text{ is a strong pseudoprime to base } b \iff n \text{ is an Euler pseudoprime to base } b \]

The proof consists of two parts:

1] If \( n \) is an Euler pseudoprime, then it’s also a strong pseudoprime

If \( n \) is an Euler pseudoprime to base \( b \), then it must also be a strong pseudoprime to base \( b \).

By definition of an Euler pseudoprime:

\[ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \pmod{n} \]

Since \( n \equiv 3 \pmod{4} \), we use a property of the Jacobi symbol \( \left( \frac{b}{n} \right) \), which can only take values \( \pm 1 \):

\[ b^{(n-1)/2} \equiv \pm 1 \pmod{n} \]

This is exactly the condition for \( n \) to be a strong pseudoprime. Since \( n - 1 = 2^1 d \) with \( d = (n-1)/2 \), it follows that \( b^d \equiv \pm 1 \pmod{n} \), proving the claim.

2] If \( n \) is a strong pseudoprime, then it’s also an Euler pseudoprime

By definition, if \( n \) is a strong pseudoprime, then:

\[ b^d \equiv \pm 1 \pmod{n} \]

I need to show that this implies:

\[ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \pmod{n} \]

Since \( n \equiv 3 \pmod{4} \), we write \( n - 1 = 2^1 d \) with \( d = (n-1)/2 \).

\[ \left( \frac{b}{n} \right) = \left( \frac{b^d}{n} \right) \]

From properties of the Jacobi symbol, we know \( \left( \frac{b^d}{n} \right) \) can only take values \( \pm 1 \).

\[ \left( \frac{b^d}{n} \right) = \pm 1 \]

This confirms that \( n \) is also an Euler pseudoprime.

Thus, I have proven that when \( n \equiv 3 \pmod{4} \), the two definitions are equivalent.