As andrewla notes, big int operations aren't O(1) in an apples-to-apples comparison. In fact, if you work out all of the math for a Z(5) implementation, this a

As andrewla notes, big int operations aren't O(1) in an apples-to-apples comparison. In fact, if you work out all of the math for a Z(5) implementation, this approach is essentially the same as the fast matrix exponentiation approach from the article. As I recall, they differ only by an application of some Fibbonaci identity (because of these identities, there are many equivalent recurrence relations).