Возведение в степень

[Hokage777]

Здравствуйте!
Изучаю алгоритм RSA шифрования, и столкнулся с проблемой. Как в JS правильно возводить в трехзначную и более степень ? Например:

let p = (i**e) % n;

где е = 2003 и n= 4399

[laimas]

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

[Hokage777]

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

[laimas]

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

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

[Alexandroppolus]

Если нужен только остаток, то его можно брать в ходе работы, тогда мы не упарываемся в километровые числа. Самый простой вариант - при возведении в степень 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]

как решать подобную проблему помимо использования 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]

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 дает большое число, которое при возведении в квадрат вылезает за пределы нумбера.

[superuser]

Ребят, я тут понимаю все очень серьезно, теоремы гаусса, БинИнт и прочие ругательства, но почему встроенный калькулятор не может корректно возвести в куб одну десятую и две десятых?

function fn01 (n) {return n * n * n}
function fn02 (n) {return n ** 3}
console.log(fn01(0.1))
console.log(fn02(0.1))
console.log(Math.pow(0.1, 3))

console.log(fn01(0.2))
console.log(fn02(0.2))
console.log(Math.pow(0.2, 3))

[Alexandroppolus]

https://javascript.ru/forum/misc/818...ki-celogo.html