С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

24.04.2013, 16:12. Просмотров 6870. Ответов 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 - C++
Даны числа A,B,C<=2^63-1 Надо посчитать A^B mod С. прошу не выкладывать стандартный алгоритм для Int, так как неверный ответ в итоге...

Возведение числа а в степень n - C++
Возведение числа а в степень n ,задача не проста чем , 1<=а<=10 | 1<=n<=7000 Степень может быть 7000 , и тут у меня возникли трудности ,...

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

Возведение из числа степень - C++
Прошу помочь. Вводим любое число n и надо возвести её степень. (притом, должно быть или 2 в степени x, или 3) Например: n=81 >> 3 в...

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

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

8
dr.curse
389 / 345 / 16
Регистрация: 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
Эксперт С++
4916 / 3024 / 370
Регистрация: 10.11.2010
Сообщений: 11,081
Записей в блоге: 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
1932 / 1198 / 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-вставки.
1
nonedark2008
934 / 673 / 148
Регистрация: 28.07.2012
Сообщений: 1,837
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
10 / 10 / 1
Регистрация: 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
Привет! Вот еще темы с ответами:

Возведение дробного числа в степень - C++
Ребят, помогите, пожалуйста. Я Не могу вынести в функцию правильно кусок кода. Так-то все работает, но задача - использовать функцию для...

Возведение числа в отрицательную степень - C++
#include <iostream> #include <conio.h> using namespace std; int main() { setlocale(LC_ALL, "Rus"); double a, b , pow(1),...

Возведение числа в степень через for - C++
Нужна программа для возведения числа в степень через for

Возведение числа в целую степень - C++
Даны числа а1 , а2 , а3 т.д.... вычислить а1^1+a2^2 и т.д используя подпрограмму возведения числа в степень Где ошибка ??? ...


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

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

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