Алгоритм по экспоненте с иррациональной базой

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 (и целые числа mod 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

Answer 2

Если вы расширите (a+sqrt(b))^n + (a-sqrt(b))^n ты получаешь

  ( a + nC1 a^(n-1) √b + nC2 a^(n-2) b + nC3 a^(n-3) √b b + ... )
 +( a - nC1 a^(n-1) √b + nC2 a^(n-2) b - nC3 a^(n-3) √b b + ... )
= 2 a  +  0            + 2 nC2 a^(n-2) b  + 0 + ... + 2 nC4 a^(n-4) b^2 + ...

поэтому условия, включающие, возможно, иррациональные части, отменяются. (nC2 и т. д. являются биномиальными коэффициентами).

RHS вышеупомянутого можно рассчитать довольно эффективно, используя целочисленную арифметику, поскольку вы можете связать каждый член в последовательности с предыдущим. Однако есть n/2 слагаемых, поэтому расчет O(n).

Поскольку мы знаем, что результатом будет целое число, мы можем попытаться выполнить возведение в степень путем возведения в квадрат алгоритма, отслеживающего целое число и дробные компоненты. Написать a+sqrt(b) = x + y где x - целое число, а y - дробная часть.

Найдя квадрат этого у нас есть x^2 + 2 x y + y^2, Хотя нас интересует только целочисленная часть, у нас есть некоторые проблемы, поскольку целочисленная часть 2 x y+ y^2, Это вызывает проблемы, поскольку для эффективного вычисления целой части мы будем знать много цифр y, Когда мы приходим к высшим силам, вам нужно больше цифр y чтобы получить целую часть.

Я не думаю, что нормальное умножение с плавающей точкой было бы достаточно, чтобы рассчитать условия для очень больших n,