What is the fastest algorithm to test a full-period multiplier for a Lehmer pseudo-random generator?

Let us consider a Lehmer pseudo-random generator with multiplier a and modulus m.

The following algorithm determine whether a is a full-period multiplier relative to the prime modulus m:

def is_full_period_multiplier(a, m):
    p = 1
    x = a
    while x != 1:
        p += 1
        x = (a * x) % m
    if p == m -1:
        return True
    else:
        return False

```

The complexity is O(m).

Do you know a faster algorithm?