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

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

24.04.2013, 16:12. Просмотров 7516. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2013, 16:12
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Возведение в степень по модулю. Большие числа (C++):

Возведение в степень по модулю для чисел близких к max long long
Даны числа A,B,C<=2^63-1 Надо посчитать A^B mod С. прошу не выкладывать...

Возведение числа n в степень m.
Написать программу - возведение числа n в m-ю степень. Входные данные поступают...

Возведение числа в степень!
Хай всем кто на форуме! Помогите с задачей! Надо возвести число в степень...

Возведение из числа степень
Прошу помочь. Вводим любое число n и надо возвести её степень. (притом, должно...

Возведение числа в степень
Помогите написать программу, возводящщую число M в степень N (-10<M<10, 0<N<10...

Возведение числа а в степень n
Возведение числа а в степень n ,задача не проста чем , 1<=а<=10 | 1<=n<=7000...

8
dr.curse
392 / 348 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
24.04.2013, 16:32 #2
Цитата Сообщение от Leytak Посмотреть сообщение
У меня есть пару способов возведения в степень по модулю, но с большими числами не работает.
а с насколько большими нужно?
0
Leytak
0 / 0 / 0
Регистрация: 10.02.2013
Сообщений: 10
24.04.2013, 16:41  [ТС] #3
Цитата Сообщение от aram_gyumri Посмотреть сообщение
а с насколько большими нужно?
до 2^32
0
castaway
Эксперт С++
4926 / 3033 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 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-Util/blob/master/mulmod.h#L54
0
Leytak
0 / 0 / 0
Регистрация: 10.02.2013
Сообщений: 10
26.04.2013, 00:01  [ТС] #5
lazybiz

Что-то там ничего не понятно... Зачем-то ещё какие-то вставки ассемблера.
Мне нужна функция, которая возвращает число a^x % p.
Мои варианты не то, чтобы совсем не работают с большими числами, но возвращают неправильные значения, хотя что-то возвращают.
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 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-вставки.
1
nonedark2008
1022 / 762 / 210
Регистрация: 28.07.2012
Сообщений: 2,118
26.04.2013, 01:41 #7
Цитата Сообщение от Leytak Посмотреть сообщение
до 2^32
Эммм. При чем тут большие числа? Обычно в RSA используются числа размером в 1024 бита.
А для чисел до 2^32 подойдет считай любой алгоритм возведения в степень, тока все операции проводятся по модулю. Ну и конечно же нужно учитывать возможное переполнение, либо как советовали выше - использовать __emul, либо заранее иметь дело с long long вместо unsigned.

Не по теме:


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

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

Возведение числа в степень n-1
Есть формула {(-1)}^{n-1}*{3}^{n-1} , n увеличивается циклом на 1. Как записать...

Рекурсивное возведение в степень числа
Рекурсивная функция,которая принимает 2 параметра:первый-число,второй-степень в...

Возведение отрицательного числа в степень
Написал программу по нахождению суммы ряда с заданной точностью(условия ниже)....

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


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

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