[s-phi-nl]

Could you expand "defines Fibonacci numbers as an element of its endomorphism ring Z[x]/(x^2 - x - 1)" in a few more words? Are you saying that Fibonacci numbers are themselves an element of its endomorphism ring (despite not obviously being a morphism)? What does "Z[x]" mean (I have a feeling it is mathematical notation forced into plain text)?

Thanks.

[sbi]

I explained this in a reply below, but this is a linear-algebraic technique. The matrix A = [0 1; 1 1] satisfies the relation A^2 - A - 1 = 0. (In fact, if you think of A as a lag operator, this is the definition of Fibonacci numbers!) You can use this relation to compute products of matrices of the form aA + bI where I is the identity matrix---the comment below has the derivation. This is a bit faster than using matrix multiplication because there are only two coefficients to keep track of.

This might seem like a pointless optimization, but it is actually useful. One advantage is that you don't need to factor the polynomial x^2 - x - 1 or work with square roots. The closed-form for Fibonacci numbers is a bit of a red herring because to work with it exactly, you will end up doing the same kinds of computations anyway. For recurrences of higher degree, factorization might be impossible and this is the only route.

When you're working over a finite field, even if you don't start with a recurrence, there are fast techniques for finding factors of the characteristic polynomial of a sparse matrix (the Berlekamp-Massey algorithm comes to mind).