>>949
定数時間で解くアルゴリズム。

x^3　-　4*x^2　+　1　=　0の3つの解をz1、z2、z3とすると

一般解はある定数(c1 c2 c3)があって　

4^n - ( c1 * z1^n + c2 * z2^n + c3 * z3^n )で表せる。

3次方程式の解を十分な精度で求めておくアルゴリズムで解決する。