**
**

# Pseudoprimes

main page
database
statistics
verification
## The rho function

### Definition

Let q be an odd number greater than 1.

**rho(q)** denotes the order of 2 in the multiplicative group modulo q. In the

*Mathematica* symbolic programming language:

rho[q_?OddQ] := MultiplicativeOrder[2, q];

### Mersenne factorizations

An equivalent formulation is that rho(q) is the least r such that q | M(r), where M(r) is the

Mersenne number M(r) = 2

^{r} - 1. For small r < 823, factorizations of M(r) are completely known. Incompletely factored Mersenne numbers and their factorization status are tracked by

Will Edgington.

### Properties

- n is prime or pseudoprime if and only if rho(n) | n-1
- rho(lcm(a, b)) = lcm(rho(a), rho(b))
- for a pseudoprimes n = q · s we have
- q = s
^{-1} mod rho(s)
- s = q
^{-1} mod rho(q)

### Some values

**q** |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
17 |
19 |
21 |
23 |
25 |
27 |
29 |
31 |
... |

**rho(q)** |
2 |
4 |
3 |
6 |
10 |
12 |
4 |
8 |
18 |
6 |
11 |
20 |
18 |
28 |
5 |
... |

**r** |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
... |

**all primes p such that rho(p) = r** |
3 |
7 |
5 |
31 |
(none) |
127 |
17 |
73 |
11 |
23, 89 |
13 |
8191 |
... |

### Computation of rho(q)

If p is prime, then rho(p) is a divisor of p-1. Computing rho(p) is as difficult as factoring p-1.

We compute rho(p

^{a}) by dumb iteration, since rho(p) | rho(p

^{a}).

In general, rho(n) with n = p

_{1}^{a1}p

_{2}^{a2}...p

_{k}^{ak}... can be computed by taking least common multiples over all rho(p

_{i}^{ai}). Again, we see that this is as hard as factoring n.

Using a cache of rho values greatly speeds up computation of rho(n) because we practically never have to completely factor n. We have enumerated the rho values of all 32-bit odd numbers in a 8GB database (4 bytes times 2

^{31} numbers).