无理基指数算法

Question

我知道有一个O(logn)算法来计算a^n，其中a是一个整数，n 是一个巨大的整数(可能结果需要模块化另一个素数MOD)。

我想知道是否还有一个O(logn)算法来计算

(a+sqrt(b))^n + (a-sqrt(b))^n (mod MOD)

无理数部分 sqrt(b) 在指数计算中看起来不太好处理。我所能做的就是分别计算 a+sqrt(b) 和 a-sqrt(b) 部分并将它们加在一起然后进行模块化，但是如果 n 很大，容易溢出。有什么想法吗？

Answer 1

您可以通过计算(在 Z_M[x]/⟨x²-b⟩ 中)

(a+x)^n+(a-x)^n mod (M, x^2-b)

您可以再次对幂使用模减半和平方，其中中间结果现在是线性多项式(模整数)。其实，你只需要一个幂，结果就是常数系数的两倍。

---

或者，这些幂组合是2阶线性递归的解

u[n+2]-2*a*u[n+1]+(a^2-b)*u[n]

在哪里

u[0]=2 and u[1]=2*a

这样您就可以使用此递归的系统矩阵的快速矩阵求幂，再次获得 O(log(n)) 算法(忽略位大小)。

---

示例:根据评论，取 a=3、b=8、n=2(和整数模 M=10^9+7，示例不够大，不重要)

在第一个变体中，计算 u[n]=(a+x)^n mod (M, x^2-b)，所以

u[0]=1
u[1]=3+x
u[2]=(3+x)^2 mod (x^2-8)=9+6x+8=17+6x

而常数项的两倍是2*17=34

在第二个变体中，递归是(2*a=6，a^2-b=1)

u[n+2]-6*u[n+1]+u[n]=0

所以第一个序列元素是

u[0]=2
u[1]=6
u[2]=6*u[1]-u[0]=34