Neue Rekorde von den größten Primzahlen werden oft über das Internet-Projekt
GIMPS(Greate Internet Mersenne Prime Search) erreicht. Eine Mersenne-Primzahl ist von der Form Mp :=
2p - 1, wobei p eine Primzahl sein muss. Dann kann der
Lucas-Lehmer-Test verwendet werden, um den Endwert einer Zahlenfolge zu
berechnen:
x1 = 4
xn+1 = xn2 - 2 mod Mp
xp-1 = 0 mod Mp wenn Primzahl, sonst zusammengesetzt
Die Komplexität ist (abgesehen vom anfänglichen Primtest auf p) von der Ordnung
O(p * log2(p)).
Falls Mp zusammengesetzt, dann müssen Teiler die Form k * p +
1 haben, aber Test über Faktorisierung dauert länger.