[hnkain]

You can do it with just integers (ie: in Z[φ]) by noting that φ^n = φFib(n) + Fib(n-1). Equivalently, compute X^n in Z[X] / (X^2-X-1). I have an article on my blog, but it's unfortunately down right now because of some github issue with changing my account to a free one.