Działanie mod M w każdej iteracji zapewnia, że wszystkie pośrednie wyniki są co najwyżej -bitowe (w innym przypadku liczba bitów byłaby dublowana w każdej iteracji).
Złożoność czasowa W powyższym algorytmie podczas każdej iteracji wykonywane są dwie kosztowne operacje: mnożenie s × s i operacja modulo mod M. Operacja mod M może być wykonywana szczególnie efektywnie na standardowych dwójkowych systemach poprzez dokonanie następującej obserwacji
Mówi ona, że najmniej znaczące bity spośród plus pozostałe bity są równoważne modulo Równoważność może być stosowana powtarzalnie do momentu co najwyżej bitów reszty. W tym postępowaniu reszta po wykonaniu dzielenia przez liczbę Mersenne’a jest obliczona bez używania dzielenia. Na przykład:
Ponadto, ponieważ s × s nigdy nie przekroczy ta prosta technika zbiega w co najwyżej 1 -bitowy dodatku (ewentualnie przeprowadza z -tego bitu w pierwszy bit), co może być wykonane w liniowym czasie. Algorytm ten posiada wyjątkowy przypadek. Daje dla mnożenia modulo zamiast poprawnej wartości 0. Jednak ten przypadek jest łatwy do wykrycia i naprawienia.
Przykłady Liczba Mersenne’a M3 = 7 jest pierwsza. Test Lucasa-Lehmera sprawdza to w następujący sposób.