Возведение в большие степени и mod n. Поясните.

[smartchecker]

Задача - довести до такого состояния чтобы в excel'е можно было посчитать не схватитв переполнения.

Первую конструкцию довёл до конца.

$ a^{13}\ mod\ n = (a\cdot a^{12})\ mod\ n = (a\cdot a^8 \cdot a^4)\ mod\ n = (a\cdot ((a^2)^2)^2 \cdot (a^2)^2) )\ mod\ n =(((a\cdot a^2)^2)^2 \cdot a)\ mod\ n = \left[(((a^2 mod\ n)\cdot a)^2\ mod\ n)^2 \cdot a\right]\ mod\ n $

А вот эту до конца довести не могу.

$ a^{61}\ mod\ n = (a\cdot a^{60})\ mod\ n = (a\cdot a^{32} \cdot a^{16} \cdot a^3 \cdot a^2)\ mod\ n = \left[a\cdot ((((a^2)^2)^2)^2)^2 \cdot (((a^2)^2)^2)^2 \cdot ((a^2)^2)^2 \cdot (a^2)^2) \right]\ mod\ n = \left[a\cdot ((((a\cdot a^2)^2)^2)^2)^2 \cdot ((a\cdot a^2)^2)^2\right]\ mod\ n = $

Подскажите как дальше?

[venco]

Опустим $\mod\ n$, подразумевая, что все произведения и квадраты выполняются по модулю.
$a^{61}= a\cdot a^{60} = a\cdot ((a^{15})^2)^2 = a\cdot ((a\cdot a^{14})^2)^2 = a\cdot ((a\cdot (a^7)^2)^2)^2 = a\cdot ((a\cdot (a\cdot a^6)^2)^2)^2 = a\cdot ((a\cdot (a\cdot (a^3)^2)^2)^2)^2 = a\cdot ((a\cdot (a\cdot (a\cdot a^2)^2)^2)^2)^2$

[smartchecker]

Этот момент ясен.
А как с $mod\ n$ поступать?

Вот это верно или нет?

$ ((((((((a^2\ mod\ n)\cdot a)^2\ mod\ n)\cdot a)^2\ mod\ n)\cdot a)^2\ mod\ n)^2 \cdot a)\ mod\ n $

[Trotil]

Если мне память не изменяет, если $n$ - составное, можно его разложить, а после воспользоваться КТО.

[venco]

smartchecker в сообщении #244425 писал(а):

Этот момент ясен.
А как с $mod\ n$ поступать?

Надо брать модуль после каждого умножения, включая возведение в квадрат.

[Профессор Снэйп]

venco в сообщении #244457 писал(а):

Надо брать модуль после каждого умножения, включая возведение в квадрат.

Другими словами, производить все действия в $\mathbb{Z}_n$

Это, кстати, вроде бы известная задача: какое минимальное (зависящее от $n$) количество умножений нужно выполнить для возведения числа в $n$-ую степень. Название задачи не помню.

[smartchecker]

Trotil в сообщении #244439 писал(а):

Если мне память не изменяет, если $n$ - составное, можно его разложить, а после воспользоваться КТО.

Предположим так
$444^{61}\mod\ 469$

[venco]

smartchecker в сообщении #244469 писал(а):

Trotil в сообщении #244439 писал(а):

Если мне память не изменяет, если $n$ - составное, можно его разложить, а после воспользоваться КТО.

Предположим так
$444^{61}\mod\ 469$

Забудьте пока КТО. Это слишком сложно для вас.

[Профессор Снэйп]

smartchecker в сообщении #244469 писал(а):

Предположим так
$444^{61}\mod\ 469$

В $\mathbb{Z}_{469}$ справедливо $444 = -25 = -5^2$. То есть надо искать $5^{122}$

[VAL]

Проще всего возводить в большую степень по модулю бинарным алгоритмом.
Вот код на maple:

bin_deg := proc(x, d, m)
local i, c, s, dd, xx;
    s := 1;
    dd := d;
    xx := x;
    for i while 0 < dd do
        dd := iquo(dd, 2, 'c');
        if c = 1 then s := s*xx mod m end if;
        xx := xx*xx mod m
    end do;
    s
end proc

Для возведения в степень порядка 1 000 000 000 000 000 000 по модулю 20-значного числа требуется порядка трех сотых секунды.

Но бинарный алгоритм использует не наименьшее число умножений.
Для нахождения наименьшего числа умножений требуется строить степенное дерево. О нем можно почитать у Кнута во втором томе "Искусства программирования".

Только пока это дерево построишь...
Так что, для больших показателей вполне достаточно бинарного алгоритма.

[smartchecker]

venco в сообщении #244479 писал(а):

smartchecker в сообщении #244469 писал(а):

Trotil в сообщении #244439 писал(а):

Если мне память не изменяет, если $n$ - составное, можно его разложить, а после воспользоваться КТО.

Предположим так
$444^{61}\mod\ 469$

Забудьте пока КТО. Это слишком сложно для вас.

Тогда какие варианты для меня?
Ещё раз обозначу - считается всё в MS Excel.

[tolstopuz]

smartchecker в сообщении #244582 писал(а):

Ещё раз обозначу - считается всё в MS Excel.

Может, сделать пользовательскую функцию на VBA?

[Профессор Снэйп]

smartchecker в сообщении #244582 писал(а):

Тогда какие варианты для меня?

Вам уже указали наилучший вариант --- бинарный алгоритм возведения в степень. Все действия выполняйте внутри $\mathbb{Z}_n$ (то есть считайте, что результат умножения двух меньших $n$ чисел --- это остаток от их "настоящего" произведения при делении на $n$).

Число умножений при таком подходе будет близко к оптимальному. Можно добиться и оптимального числа умножений, но это труднее запрограммировать.

[Батороев]

Для удобства можно представить число в двоичной системе.
$ 61_{10}= 111101_2$
Записываем полученное число сверху-вниз, начиная с конца.
1 $a^1$
0 $a^2=a^1a^1$
1 $a^4=a^2a^2$
1 $a^8=a^4a^4$
1 $a^{16}=a^8a^8$
1 $a^{32}=a^{16}a^{16}$
Перемножаете или сами значения, или остатки тех строк, против которых стоит 1.

[VAL]

Батороев в сообщении #244645 писал(а):

Для удобства можно представить число в двоичной системе.
$ 61_{10}= 111101_2$
Записываем полученное число сверху-вниз, начиная с конца.
1 $a^1$
0 $a^2=a^1a^1$
1 $a^4=a^2a^2$
1 $a^8=a^4a^4$
1 $a^{16}=a^8a^8$
1 $a^{32}=a^{16}a^{16}$
Перемножаете или сами значения, или остатки тех строк, против которых стоит 1.

Это верно.
Более того, тремя постами выше данный алгоритм уже приведен