[aleph_minus_one]

> Is "closed form" here supposed to mean "closed form we can evaluate without needing arbitrary-precision arithmetic"?

You don't need arbitrary-precision arithmetic to evaluate Binet's formula - big integer arithmetic suffices (simply do your calculations in the ring Z[X]/(X^2-X-1) ).

[PollardsRho]

At that point, you'd be better off just using a recursive algorithm like the one in GMP. You're swapping out arbitrary-length for arbitrary-precision.