Javascript-форум (https://javascript.ru/forum/)
-   Общие вопросы Javascript (https://javascript.ru/forum/misc/)
-   -   Возведение в степень (https://javascript.ru/forum/misc/78824-vozvedenie-v-stepen.html)

Hokage777 09.11.2019 15:53

Возведение в степень
 
Здравствуйте!
Изучаю алгоритм RSA шифрования, и столкнулся с проблемой. Как в JS правильно возводить в трехзначную и более степень ? Например:
let p = (i**e) % n;
где е = 2003 и n= 4399

laimas 09.11.2019 15:55

https://developer.mozilla.org/ru/doc...jects/Math/pow

Hokage777 09.11.2019 16:15

Math.pow() и ** при возведении в такую большую степень выбрасывают NaN, как решать подобную проблему помимо использования BigInt, который не дает делить по модулю из-за разницы типов ?

laimas 09.11.2019 16:30

Цитата:

Сообщение от Hokage777
помимо использования BigInt, который не дает делить по модулю

Кто такое сказал?

Alexandroppolus 09.11.2019 16:48

Если нужен только остаток, то его можно брать в ходе работы, тогда мы не упарываемся в километровые числа. Самый простой вариант - при возведении в степень n**p сделать цикл из p умножений на n (после каждого берем остаток), но гораздо быстрее смотреть биты числа р и умножать на соответствующие им значения n**(2**i)

// вычисляет (n ** p) % m
function powMod(n, p, m) {
  if (n < 1) { return 0; }
  if (m < 0) { m = 0; }
  p = Math.round(p);
  n = n % m;
  var r = 1;
  while (p >= 1) {
    if (p % 2) {
      r = (r * n) % m;
    }
    n = (n * n) % m;
    p = Math.floor(p / 2);
  }
  return r;
}

alert(powMod(34546, 68883, 2437));


в хроме на относительно больших числах это работает быстрее "прямого" вычисления с BigInt

Malleys 09.11.2019 18:28

Цитата:

Сообщение от Hokage777
как решать подобную проблему помимо использования BigInt, который не дает делить по модулю из-за разницы типов ?

Всё таки даёт...
function powToMod(base, power, module) {
	if(power === 1n) return base;
	if(power % 2n === 0n) return powToMod(base, power / 2n, module) ** 2n % module;
	return powToMod(base, power - 1n, module) * base % module;
}

alert(powToMod(366142356n, 1447804911n, 219020071n));


Alexandroppolus, проверьте свой алгоритм, powToMod(366142356n, 1447804911n, 219020071n) должно выдавать 38504623

Проверял также тут — https://www.wolframalpha.com/input/?...11mod219020071

Alexandroppolus 09.11.2019 19:44

Цитата:

Сообщение от Malleys
Alexandroppolus, проверьте свой алгоритм, powToMod(366142356n, 1447804911n, 219020071n) должно выдавать 38504623

тот же вариант для БигИнта, работает правильно

function powModBig(n, p, m) {
  if (n < 1n) { return 0n; }
  if (m < 0n) { m = 0n; }
  n = n % m;
  var r = 1n;
  while (p >= 1n) {
    if (p % 2n) {
      r = (r * n) % m;
    }
    n = (n * n) % m;
    p = p / 2n;
  }
  return r;
}

alert(powModBig(366142356n, 1447804911n, 219020071n))


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

----
вариант для обычных чисел не может с такими параметрами, потому что 366142356 % 219020071 дает большое число, которое при возведении в квадрат вылезает за пределы нумбера.

Rise 09.11.2019 22:11

Цитата:

Сообщение от Hokage777
Math.pow() и **

Это одно и тоже, чувак.


Часовой пояс GMT +3, время: 16:51.