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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 46, средняя оценка - 4.83
Leytak
0 / 0 / 0
Регистрация: 10.02.2013
Сообщений: 10
#1

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

24.04.2013, 16:12. Просмотров 6258. Ответов 8
Метки нет (Все метки)

Всем привет.
У меня есть пару способов возведения в степень по модулю, но с большими числами не работает.
Требуется вычислить 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 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
1927 / 1193 / 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
883 / 622 / 125
Регистрация: 28.07.2012
Сообщений: 1,662
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++ Возведение отрицательного числа в степень
Возведение в степень, отрицательные числа C++
Рекурсия, возведение числа в степень C++
Возведение числа в целую степень C++
Возведение числа в степень через for C++

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru