BigInteger в степени BigInteger

@magnum1992 · Регистрация: 22.05.2011

Author24 — интернет-сервис помощи студентам

Имеются переменные y,r,s,p типа BigInteger. Необходимо вычислить (y^r*r^s) % p.
Какие предложения по поводу вычисления данной формулы?
Вот мой вариант:

C#

1
2
3

if (R > int.MaxValue || S > int.MaxValue)
                throw new ArgumentException("Too big exponent");
           BigInteger l = (BigInteger.Pow(Y, (int)R) * BigInteger.Pow(R, (int)S))%P;

Если даже R и S не превышают int программа зависает.
Возможно ли это выражение разбить на два и воспользоваться методом BigInteger.ModPow?

@EVG-1980 · 03.04.2014, 10:55

magnum1992, y^r*r^s - скорее всего OutOfMemory

сколько разрядов в цифрах y, r и s?

@magnum1992 · 03.04.2014, 11:01 **[ТС]**

уже при разрядности чисел 24 бита происходит зависание.

Сообщение от EVG-1980

скорее всего OutOfMemory

скорее всего нет

@EVG-1980 · 03.04.2014, 11:03

magnum1992, Огромные цифры лучше всего засунуть в stringи или в массивы и работать с ними так

string y="123"; r=3;

y^r это y[2]+y[2]+y[2] ; y[1]+y[1]+y[1]; y[0]+y[0]+y[0]

@magnum1992 · 03.04.2014, 11:09 **[ТС]**

EVG-1980, Числа y = {3027291},r ={6893186},s ={4040391},p ={7061449} кажутся вам большими?
И что то не совсем понятно как вы со string работаете.

@EVG-1980 · 03.04.2014, 11:31

Сообщение от magnum1992

И что то не совсем понятно как вы со string работаете.

поразрядно

string y="124"; r=3;

y^r это y[2]+y[2]+y[2] ; y[1]+y[1]+y[1]; y[0]+y[0]+y[0]

т.е. сначала складываем младший разряд

C#

(int) y[2] + (int) y[2] + (int) y[2]    //  4+4+4  = 12 
 
int perenos = (int) 12/10;
 
string  resalt;
 
resalt[0] = 2  //  1 переноситься в старший разряд
 
(int) y[1] + (int) y[1] + (int) y[1] + perenos   //  2+2+2 +1 = 7 
 
resalt[1] = 7

Добавлено через 9 минут
magnum1992, тупанул

C#

1	y^r это y[2]y[2]y[2] ; y[1]y[1]y[1]; y[0]y[0]y[0]

но принцип тот же

@pycture · 03.04.2014, 13:37

Сообщение от magnum1992

Числа y = {3027291},r ={6893186},s ={4040391},p ={7061449} кажутся вам большими?

ну не маленькие 3027291^6893186

44 675 112 decimal digits

@EVG-1980 · 03.04.2014, 14:29

44 675 112 decimal digits * 2 байта в принципе не много около 100 метров памяти на 1 число

100 метров на первое число + 100 метров на второе число + 200 метров результат умножения + промежуточные массивы

@magnum1992 · 03.04.2014, 14:31 **[ТС]**

EVG-1980, Объясните еще раз пошагово на конкретном примере свой вариант(с полной детализацией пожалуйста)

@EVG-1980 · 03.04.2014, 14:42

magnum1992, возведение в степень можно представить в виде операции умножения , операцию умножения можно представить как сложение

4^3 = 4*4*4 = ( 4+4+4+4 ) * 4 = т.д.

поразрядно складывать в школе учат

C#

str1 =  "3598";
+
str2 =  "3598";
 
=             
 
 
rez[0] = str1[3] + str2[3]  //8 +8 = 16   ,  6  пишем   единичка переходит в старший разряд
rez[1] = str1[2] + str2[2] // 9 + 9 +1 =19  ,  9  пишем   единичка переходит в старший разряд
rez[2] = str1[1] + str2[1] // 5 + 5 +1 =11  ,  1  пишем   единичка переходит в старший разряд
rez[3] = str1[0] + str2[0] // 3+ 3 +1 =7

@pycture · 03.04.2014, 14:52

Сообщение от EVG-1980

в принципе не много около 100 метров памяти на 1 число

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

возведение в степень можно представить в виде операции умножения

разве возведение в степень у bigint работает по другому?

@Learx · 03.04.2014, 15:02

magnum1992, y = {3027291} $https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx$ 3*10⁶
r ={6893186} $https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx$ 6*10⁶
y^r $https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx$ 3^6*10⁶*10^36000000
это явно выходит за рамки любого типа

@magnum1992 · 03.04.2014, 15:06 **[ТС]**

Не по теме:

Сообщение от EVG-1980

поразрядно складывать в школе учат

Смотря кто что запомнил

Добавлено через 3 минуты

Не по теме:

Вообщем глупость я сморозил презнаюсь

@EVG-1980 · 03.04.2014, 15:07

Сообщение от pycture

разве возведение в степень у bigint работает по другому

так же думаю , но самописную фигню хоть можно проконтролировать припилив прогресс бар и знать что она работает , а не висит

Тебе надо написать два метода

1. который посчитает 4^3 = 4*4*4 = ( 4+4+4+4 ) * 4 = ( 4+4+4+4 ) + ( 4+4+4+4 ) + ( 4+4+4+4 ) +( 4+4+4+4 )

столько тебе раз надо сложить твое основание в этом примере 16 раз надо сложить число 4

2. метод сложения строк

C#

public SUM(ref string str1,string str2)
{
 
int temp =0;
int pr =0;
 
for(int i = str2.lithg-1; i>=0 ; i--) 
{
temp = (int) str1[i]+ (int) str2[i];    
pr= (int) temp/10;
str1[i] =(char) temp%10 ;
str1[i-1]=(int) str1[i-1]+pr;
}
 
}

писал без студии ошибки сам исправишь

@magnum1992 · 03.04.2014, 15:13 **[ТС]**

Так объясню зачем мне это нужно. Я реализую Схему Эль Гамаля в режиме подписи и мне это вычисление необходимо при проверке подписи. На сколько я понял для нормальной криптостойкости используются числа от 1024 бита откуда вытекает вопрос как у них реализовано возведение большого числа в большое

Добавлено через 2 минуты
Возможно ли как нибудь использовать метод BigInteger.ModPow для этой формулы?

@EVG-1980 · 03.04.2014, 15:44

посмотри тут может подойдет
http://www.codeproject.com/Articles/36323/BigInt

@rRczZZ · 03.04.2014, 16:08

magnum1992, а Вы пробовали очевидные формулы? $https://www.cyberforum.ru/cgi-bin/latex.cgi?(y^r\cdot r^s) mod\,p = ((y^r\, mod\,p) \cdot (r^s\, mod\,p))\,mod\,p = (y^{r-s}\cdot r)^s\, mod\, p$
хотябы так:

C#

1	(BigInteger.ModPow(y, r, p) * BigInteger.ModPow(r, s, p)) % p

Если не походит можно попробовать оценить порядок p и реализовать конкретный алгоритм, например, можно составить индексную таблицу умножения по модулю p.

EVG-1980, собственно, BigInteger и реализует длинную арифметику используя алгоритмы быстрого умножения, возведения в степень итд.. отличных от школьного умножения в столбик.

@EVG-1980 · 03.04.2014, 16:16

Сообщение от rRczZZ

и реализует длинную арифметику используя алгоритмы быстрого умножения, возведения в степень итд..

magnum1992, код в студию щас до дома приеду проверю как твой код на i7 фурычит и виснет

@magnum1992 · 03.04.2014, 16:53 **[ТС]**

rRczZZ, Спасибо все работает и очень быстро.
EVG-1980, И вам спасибо за помощь. Вот код если интересно:

C#

1
2
3

BigInteger temp = BigInteger.ModPow(Y, R, P);
            BigInteger temp2 = BigInteger.ModPow(R, S, P);
            l = (temp * temp2)%P;

Добавлено через 1 минуту
подавал на вход 128 байтные числа зависи при вычислении не наблюдалось
P.S. Core i5

@EVG-1980 192 / 199 / 82 Регистрация: 11.04.2013 Сообщений: 1,086
	03.04.2014, 10:55	2
	magnum1992, y^r*r^s - скорее всего OutOfMemory сколько разрядов в цифрах y, r и s? 0

@magnum1992 44 / 44 / 19 Регистрация: 22.05.2011 Сообщений: 156 Записей в блоге: 5
	03.04.2014, 11:01 [ТС]	3
	уже при разрядности чисел 24 бита происходит зависание. Сообщение от EVG-1980 скорее всего OutOfMemory скорее всего нет 0

@EVG-1980 192 / 199 / 82 Регистрация: 11.04.2013 Сообщений: 1,086
	03.04.2014, 11:03	4
	magnum1992, Огромные цифры лучше всего засунуть в stringи или в массивы и работать с ними так string y="123"; r=3; y^r это y[2]+y[2]+y[2] ; y[1]+y[1]+y[1]; y[0]+y[0]+y[0] 0

@magnum1992 44 / 44 / 19 Регистрация: 22.05.2011 Сообщений: 156 Записей в блоге: 5
	03.04.2014, 11:09 [ТС]	5
	EVG-1980, Числа y = {3027291},r ={6893186},s ={4040391},p ={7061449} кажутся вам большими? И что то не совсем понятно как вы со string работаете. 0

@pycture 1195 / 588 / 88 Регистрация: 20.09.2012 Сообщений: 1,881
	03.04.2014, 13:37	7
	Сообщение от magnum1992 Числа y = {3027291},r ={6893186},s ={4040391},p ={7061449} кажутся вам большими? ну не маленькие 3027291^6893186 44 675 112 decimal digits 0

@EVG-1980 192 / 199 / 82 Регистрация: 11.04.2013 Сообщений: 1,086
	03.04.2014, 14:29	8
	44 675 112 decimal digits * 2 байта в принципе не много около 100 метров памяти на 1 число 100 метров на первое число + 100 метров на второе число + 200 метров результат умножения + промежуточные массивы 0

@magnum1992 44 / 44 / 19 Регистрация: 22.05.2011 Сообщений: 156 Записей в блоге: 5
	03.04.2014, 14:31 [ТС]	9
	EVG-1980, Объясните еще раз пошагово на конкретном примере свой вариант(с полной детализацией пожалуйста) 0

@pycture 1195 / 588 / 88 Регистрация: 20.09.2012 Сообщений: 1,881
	03.04.2014, 14:52	11
	Сообщение от EVG-1980 в принципе не много около 100 метров памяти на 1 число немного это если его просто в памяти подержать, а рассчитать это уже не так все радужно. возведение в степень можно представить в виде операции умножения разве возведение в степень у bigint работает по другому? 0

@Learx 1057 / 864 / 195 Регистрация: 31.03.2010 Сообщений: 2,521
	03.04.2014, 15:02	12
	magnum1992, y = {3027291} $https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx$ 310⁶ r ={6893186} $https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx$ 610⁶ y^r $https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx$ 3^610⁶10^36000000 это явно выходит за рамки любого типа 0

@magnum1992 44 / 44 / 19 Регистрация: 22.05.2011 Сообщений: 156 Записей в блоге: 5
	03.04.2014, 15:06 [ТС]	13
	Не по теме: Сообщение от EVG-1980 поразрядно складывать в школе учат Смотря кто что запомнил Добавлено через 3 минуты Не по теме: Вообщем глупость я сморозил презнаюсь 0

@magnum1992 44 / 44 / 19 Регистрация: 22.05.2011 Сообщений: 156 Записей в блоге: 5
	03.04.2014, 15:13 [ТС]	15
	Так объясню зачем мне это нужно. Я реализую Схему Эль Гамаля в режиме подписи и мне это вычисление необходимо при проверке подписи. На сколько я понял для нормальной криптостойкости используются числа от 1024 бита откуда вытекает вопрос как у них реализовано возведение большого числа в большое Добавлено через 2 минуты Возможно ли как нибудь использовать метод BigInteger.ModPow для этой формулы? 0

@EVG-1980 192 / 199 / 82 Регистрация: 11.04.2013 Сообщений: 1,086
	03.04.2014, 15:44	16
	посмотри тут может подойдет http://www.codeproject.com/Articles/36323/BigInt 0

@EVG-1980 192 / 199 / 82 Регистрация: 11.04.2013 Сообщений: 1,086
	03.04.2014, 16:16	18
	Сообщение от rRczZZ и реализует длинную арифметику используя алгоритмы быстрого умножения, возведения в степень итд.. magnum1992, код в студию щас до дома приеду проверю как твой код на i7 фурычит и виснет 0

BigInteger в степени BigInteger

Решение