Воскресенье, 17.12.2017, 18:43
Тверь-Робот
Главная | Быстрое возведение в сепень по модулю - Форум | Регистрация | Вход
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Форум » Вопросы роботостроительства в Твери » Прочие вопросы программирования роботов » Быстрое возведение в сепень по модулю (Возведение в сепень по модулю)
Быстрое возведение в сепень по модулю
avaria69Дата: Среда, 15.05.2013, 08:29 | Сообщение # 1
Рядовой
Группа: Пользователи
Сообщений: 2
Репутация: 0
Статус: Offline
Пусть у нас есть некоторое число a, которое требуется возвести в степень k(возможно, по модулю n). Можно просто умножить a само на себя k раз, но при больших размерах чисел это довольно сложная и медленная операция. Рассмотрим алгоритм, вычисляющий ak за O(log k) операций. В квадратных скобках указаны изменения, необдимые для вычисления степени по модулю.

1. Представим d в двоичной системе счисления d = d02r + ... + dr-12 + dr, где di, цифры в двоичном представлении, равны 0 или 1, d0=1.

2. Положим a0 =a и затем для i=1, ... ,r вычислим
ai = ai-12 * adi [(mod n)].

3. ar есть искомый вычет ad [(mod n)].

Исходник на Си/* Author: Pate Williams © 1997 */

#include <stdio.h>

#define BITS_PER_LONG 32l
#define DEBUG

// Перевод числа в двоичную системуlong long_to_binary(long K, long *k)
{
int found = 0;
long a = K, i, l = 0, length;

while (!found && l < BITS_PER_LONG) {
found = ((a & 0x80000000l) >> 31) == 1;
if (!found) a <<= 1, l++;
}

length = BITS_PER_LONG - l;
for (i = 0; i < length; i++) k = K & 1, K >>= 1;
return length;
}

// Возведение a в степень K по модулю n// Если модуль не нужен - уберите все вхождения nlong powmod(long a, long K, long n)
{
long A = a, b = 1, i, k[32];
long t = long_to_binary(K, k);

if (K == 0) return b;
if (k[0] == 1) b = a;

#ifdef DEBUG
printf("-------------\n");
printf("i k A B \n");
printf("-------------\n");
printf("%ld %ld %4ld %4ld\n", i = 0, k, A, b);
#endif

for (i = 1; i < t; i++) {
A = (A * A) % n;
if (k) b = (A * b) % n;
#ifdef DEBUG
printf("%ld %ld %4ld %4ld\n", i, k, A, b);
#endif
}

#ifdef DEBUG
printf("-------------\n");
#endif

return b;
}

int main(void)
{

long a = 5, K = 596, n = 1234;

printf ("%ld\n",powmod(a, K, n));

return 0;
}
А вот - другой вид функции возведения в степень, неявно использующий двоичное представление(вычисляющий его на лету) и ненуждающийся в long2binary():

long powmod(long a, long k, long n)
{
long b=1;

while (k) {
if (k%2==0) {
k /= 2;
a *= a; // [ a = (a*a)%n; ] }
else {
k--;
b *= a; // [b=(b*a)%n;] }
}
return b;
}[/b]
 
Форум » Вопросы роботостроительства в Твери » Прочие вопросы программирования роботов » Быстрое возведение в сепень по модулю (Возведение в сепень по модулю)
Страница 1 из 11
Поиск:

Copyright Ассоциация Тверь-Робот © 2017Бесплатный конструктор сайтов - uCoz