Форум программистов, компьютерный форум CyberForum.ru

Возведение в степень по модулю. Большие числа - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 46, средняя оценка - 4.83
Leytak
0 / 0 / 0
Регистрация: 10.02.2013
Сообщений: 10
24.04.2013, 16:12     Возведение в степень по модулю. Большие числа #1
Всем привет.
У меня есть пару способов возведения в степень по модулю, но с большими числами не работает.
Требуется вычислить A^X mod P.
Нужно для реализации шифра RSA.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
unsigned long powmod(unsigned long a, unsigned long x, unsigned long p)
{
  unsigned long result = 1;
 
  while(x)
  {
      if (x%2==0)
      {
          x /= 2;
          a *= a % p;
      }
      else
      {
          x--;
          result *= a % p;
      }
  }
 
  return result % p;
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unsigned long powmod(unsigned long a, unsigned long x, unsigned long p)
{
   unsigned long result = 1;
   char x_bin[100];
   int t = int(log(x)/log(2.0));
   itoa(x, x_bin, 2);
   for(int i=t;i>=0;i--)
   {
      if(x_bin[i] == '1')
                 result *= a % p;
      a *= a % p;
   }
   result %= p;
   return result;
}
C++
1
2
3
4
5
6
7
8
unsigned long powmod(unsigned long a, unsigned long x, unsigned long p)
{
    if (x == 0) return 1;
    unsigned long res = powmod(a, x >> 1, p);
    res *= res;
    res %= p;
    return (x & 1)? (a * res) % p : res;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2013, 16:12     Возведение в степень по модулю. Большие числа
Посмотрите здесь:

C++ Возведение числа n в степень m.
C++ Возведение в степень по модулю для чисел близких к max long long
C++ Возведение числа в степень
C++ Возведение числа в целую степень
Рекурсивное возведение в степень числа C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
24.04.2013, 16:32     Возведение в степень по модулю. Большие числа #2
Цитата Сообщение от Leytak Посмотреть сообщение
У меня есть пару способов возведения в степень по модулю, но с большими числами не работает.
а с насколько большими нужно?
Leytak
0 / 0 / 0
Регистрация: 10.02.2013
Сообщений: 10
24.04.2013, 16:41  [ТС]     Возведение в степень по модулю. Большие числа #3
Цитата Сообщение от aram_gyumri Посмотреть сообщение
а с насколько большими нужно?
до 2^32
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
24.04.2013, 19:10     Возведение в степень по модулю. Большие числа #4
Какой компилятор?
Почему банальная конструкция не подходит?
C++
1
#define mulmod( a, b, m )  (((uint64_t)(a) * (uint64_t)(b)) % ((uint64_t)(m)))
Добавлено через 59 минут
Пардон, не то. Вообщем тут есть: https://github.com/danaj/Math-Prime-...r/mulmod.h#L54
Leytak
0 / 0 / 0
Регистрация: 10.02.2013
Сообщений: 10
26.04.2013, 00:01  [ТС]     Возведение в степень по модулю. Большие числа #5
lazybiz

Что-то там ничего не понятно... Зачем-то ещё какие-то вставки ассемблера.
Мне нужна функция, которая возвращает число a^x % p.
Мои варианты не то, чтобы совсем не работают с большими числами, но возвращают неправильные значения, хотя что-то возвращают.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.04.2013, 00:31     Возведение в степень по модулю. Большие числа #6
Как-то так.
Можно даже тип exp сменить на unsigned long long, все равно оно мгновенно считать будет за счет логарифмической сложности.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unsigned powmod(unsigned base, unsigned exp, unsigned modulo)
{
    unsigned res = 1;
    
    while (exp != 0) 
    {
        if ((exp & 1) != 0)
        {
            res = (1ll * res * base) % modulo;
        }
        
        base = (1ll * base * base) % modulo;
        exp >>= 1;
    }
    
    return res;
}
Добавлено через 10 минут
Цитата Сообщение от diagon Посмотреть сообщение
(1ll * res * base)
Цитата Сообщение от diagon Посмотреть сообщение
(1ll * base * base)
Вот эту часть можно ускорить за счет лоулевельщины.
Для студии есть специальный интринсик. Для gcc аналога не нашел, так что надо либо надеяться на то, что он оптимизирует это самостоятельно, либо использовать asm-вставки.
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
26.04.2013, 01:41     Возведение в степень по модулю. Большие числа #7
Цитата Сообщение от Leytak Посмотреть сообщение
до 2^32
Эммм. При чем тут большие числа? Обычно в RSA используются числа размером в 1024 бита.
А для чисел до 2^32 подойдет считай любой алгоритм возведения в степень, тока все операции проводятся по модулю. Ну и конечно же нужно учитывать возможное переполнение, либо как советовали выше - использовать __emul, либо заранее иметь дело с long long вместо unsigned.

Не по теме:


Везет же некоторым, а мне пришлось реализовывать длинную арифметику для RSA >_>

Leytak
0 / 0 / 0
Регистрация: 10.02.2013
Сообщений: 10
26.04.2013, 21:45  [ТС]     Возведение в степень по модулю. Большие числа #8
diagon
Спасибо большое, всё получилось!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2013, 15:57     Возведение в степень по модулю. Большие числа
Еще ссылки по теме:

C++ Возведение числа в отрицательную степень
Возведение числа в степень через for C++
Рекурсия, возведение числа в степень C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
lexflax
10 / 10 / 1
Регистрация: 03.04.2011
Сообщений: 627
11.12.2013, 15:57     Возведение в степень по модулю. Большие числа #9
Доброго времени суток.
Leytak, получилось реализовать алгоритм RSA с помощью подпрограмм? Если да , то не могли бы скинуть весь код.
Yandex
Объявления
11.12.2013, 15:57     Возведение в степень по модулю. Большие числа
Ответ Создать тему
Опции темы

Текущее время: 10:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru