Поиск по модулю обратного, если gcd не 1

Question

Я должен найти (p^e-1)/(p-1) mod 1000000007, где p - простое число. , если gcd (p-1,1000000007) не 1, то модульная инверсия (p-1) не определена. Кроме того, (p^e-1) делится на (p-1) (сумма геометрической прогрессии). Также я не могу найти (p^e-1), так как p, e < = 10^18. Так как я считаю (р^е-1)/(р-1) по модулю 1000000007

Answer 1

1000000007 is a prime number, так что если p-1 < 1000000007 НОД всегда будет 1. Если p-1 некоторое кратное 1000000007, то она по определению равна нулю по модулю 1000000007 и поэтому нет обратного определения.

Answer 2

Когда вы делите целые числа, а затем принимая модуль, вы должны обработать простые коэффициенты модуля специальным образом. Рассмотрим, например, 6/3 mod 3. Если бы мы просто попытались написать 6/3 mod 3 = (6 mod 3)/(3 mod 3), мы бы не определили 0/0, тогда как правильный ответ, конечно, 6/3 mod 3 = 2 mod 3 = 2.

Так что нам нужно сделать так, чтобы умножить силы 3 как на числитель, так и на знаменатель и разделить их отдельно (путем вычитания показателей). Итак, мы имеем 6 = 3^1 x 2, 3 = 3^1 x 1, поэтому 6/3 = 3^1/3^1 x 2/1 = 3^{1-1} x 2 = 3^0 x 2 = 2 mod 3. Попробуем более сложный пример: 18/6 mod 3 = (3^2 x 2)/(3^1 x 2) = 3^{2-1} x 2/2 = 3 x 1 = 3 mod 3 = 0.

Вот еще один пример: 36/18 = (3^2 x 4)/(3^2 x 2) = 3^{2-2} x 4 x 2^{- 1 } mod 3 = 4 x 2 mod 3 (так как 2^{- 1} = 2 mod 3) = 8 mod 3 = 2. В общем случае мы вычитаем показатели степени 3 части и инвертируем mod 3 немощным 3 части дивизора.

В вашем примере мы должны найти наивысшую мощность m 1000000007, которая переходит в p^e-1, и переписать p^e-1 = 1000000007^mxs, где s относительно просто до 1000000007. Мы делаем то же для p-1 = 1000000007^nxt, где t взаимно просто с 1000000007. Тогда фактор (p^e-1)/(p-1) = 1000000007^{mn} xsxt^{- 1}. Ответ 0 mod 1000000007, если m> n; в противном случае ответ будет равен s x t^{- 1} mod 1000000007. Обратный t mod 1000000007 существует, потому что t относительно просто с 1000000007; обратный может быть вычислен по модифицированной версии евклидова алгоритма.

Answer 3

Поскольку 1000000007 является простым, есть два случая.

Дело 1: 1000000007 является фактором p-1. Тогда p mod 1000000007 = 1, поэтому 1 + p + p^2 + ... + p^(e-1) = 1 + 1 + 1 ... + 1 = e mod 1000000007.

Корпус 2: 1000000007 относительно просто с p-1, и вы можете вычислить 1/(p-1) как (p-1)^1000000005 mod 1000000007 или используя алгоритм Евклида, и вы можете вычислить мощности mod 1000000007 относительно быстро, используя возведение в степень по квадрату.

Answer 4

У вас есть два случая

1. p-1 копростое в больших простых 1000000007. Это всегда верно для p <= 1000000007 и обычно для больших p. Кажется, вы знаете, что делать в этом случае - используйте алгоритм для поиска модульной инверсии p-1, то есть a такой, что a * (p - 1) == 1 mod 1000000007.

2. p-1 является кратным 1000000007 - то есть p-1 == k*1000000007.В этом случае, p == k*1000000007 + 1

   Давайте обратим внимание на верхней строке выражения

   p^e - 1 == (k * 1000000007 + 1)^e - 1 
   

   Это может быть расширена с помощью биномиального разложения в

   ((k*1000000007)^e + e*(k*1000000007)^(e-1) + ... + 1) - 1 
   

   Помните, однако, что (k*1000000007) == p-1 , Таким образом, расширение

   ((p-1)^e + e*(p-1)^(e-1) + ... + e*(p-1)) 
   

   Мы можем разделить через это на p-1 и остались с

   ((p-1)^(e-2) + e*(p-1)^(e-2) + .... + e) 
   

   Мы знаем, что все члены, содержащие p-1 являются 0 мод 1000000007 в этом случае, так что мы просто осталось с последним термином, e. Таким образом, в этом случае результат выражения (p^e - 1)/(p - 1) mod 1000000007 равен e - вы не найдете модульный инверсный p-1, потому что вы не можете, но вам тоже этого не нужно.