Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 09.11.2019, 15:53
Новичок на форуме
Отправить личное сообщение для Hokage777 Посмотреть профиль Найти все сообщения от Hokage777
 
Регистрация: 06.11.2019
Сообщений: 4

Возведение в степень
Здравствуйте!
Изучаю алгоритм RSA шифрования, и столкнулся с проблемой. Как в JS правильно возводить в трехзначную и более степень ? Например:
let p = (i**e) % n;
где е = 2003 и n= 4399
Ответить с цитированием
  #2 (permalink)  
Старый 09.11.2019, 15:55
Профессор
Отправить личное сообщение для laimas Посмотреть профиль Найти все сообщения от laimas
 
Регистрация: 14.01.2015
Сообщений: 11,162

https://developer.mozilla.org/ru/doc...jects/Math/pow
Ответить с цитированием
  #3 (permalink)  
Старый 09.11.2019, 16:15
Новичок на форуме
Отправить личное сообщение для Hokage777 Посмотреть профиль Найти все сообщения от Hokage777
 
Регистрация: 06.11.2019
Сообщений: 4

Math.pow() и ** при возведении в такую большую степень выбрасывают NaN, как решать подобную проблему помимо использования BigInt, который не дает делить по модулю из-за разницы типов ?
Ответить с цитированием
  #4 (permalink)  
Старый 09.11.2019, 16:30
Профессор
Отправить личное сообщение для laimas Посмотреть профиль Найти все сообщения от laimas
 
Регистрация: 14.01.2015
Сообщений: 11,162

Сообщение от Hokage777
помимо использования BigInt, который не дает делить по модулю
Кто такое сказал?
Ответить с цитированием
  #5 (permalink)  
Старый 09.11.2019, 16:48
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 715

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

Последний раз редактировалось Alexandroppolus, 09.11.2019 в 16:59.
Ответить с цитированием
  #6 (permalink)  
Старый 09.11.2019, 18:28
Аватар для Malleys
Профессор
Отправить личное сообщение для Malleys Посмотреть профиль Найти все сообщения от Malleys
 
Регистрация: 20.12.2009
Сообщений: 1,283

Сообщение от 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
Ответить с цитированием
  #7 (permalink)  
Старый 09.11.2019, 19:44
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 715

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

Последний раз редактировалось Alexandroppolus, 09.11.2019 в 19:46.
Ответить с цитированием
  #8 (permalink)  
Старый 09.11.2019, 22:11
Профессор
Отправить личное сообщение для Rise Посмотреть профиль Найти все сообщения от Rise
 
Регистрация: 07.11.2013
Сообщений: 4,179

Сообщение от Hokage777
Math.pow() и **
Это одно и тоже, чувак.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Возведение в степень по модулю. Что не так? Добрый_Серый_Волк Ваши сайты и скрипты 7 18.10.2019 19:03
Возведение в степень больших чисел. Алгоритм DH Morr123 Элементы интерфейса 0 13.09.2016 23:07
возведение числа в степень BpArCuCTeMbI Общие вопросы Javascript 15 09.06.2014 02:07
Не работает возведение в степень TuxShot Элементы интерфейса 1 01.12.2013 08:57
Возведение в очень большую степень. satan Общие вопросы Javascript 0 25.10.2012 18:21