# 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) = 2r - 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(pa) by dumb iteration, since rho(p) | rho(pa).

In general, rho(n) with n = p1a1p2a2...pkak... can be computed by taking least common multiples over all rho(piai). 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 231 numbers).