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

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).