Самое быстрое модульное возведение в степень в JavaScript
Спросите о любых контрольно-пропускных пунктах или обходных решениях, с которыми столкнулся исходный разработчик.
Узнают о Ваших клиентах также. Действительно ли они придирчивы? Что они ожидают?
5 ответов
Будет ли приемлемой какая-либо другая технология на стороне клиента, вызываемая из JS, такая как Java-апплет или Flash-фильм? Подход BigInt уже довольно быстр. Вы можете настроить BigInt или попробовать другой алгоритм , но вы, вероятно, не получите улучшения на порядок.
Почему бы не сделать это на стороне сервера в какой-нибудь веб-службе, используя более подходящий язык, например C? Тогда время будет временем для одного цикла туда и обратно (менее 9 секунд), плюс время, в течение которого сервер вычислит результат с использованием некоторой библиотеки BigInt в собственном коде. Вероятно, это будет намного быстрее.
Я использую "%" для модульного (модульного) и "/" для целочисленного деления. Пусть функция f (p, g, x, r) вычисляет (r * g ^ x)% p при условии, что r
bigint_t f(p,g,x,r) {
bigint_t i, z = g, y;
for (i = 1; i < x; ++i) {
y = z; z *= g;
if (z > p) break;
}
if (i >= x - 1) return r*z%p; // g^x*r%p = g^x*r
else return f(p,y,x/i,g^(x%i)*r%p); // reduce to (r*g^(x%i)%p)*(g^i)^(x/i)%p
}
Эта процедура включает в себя немного больше вычислений, но каждое целое число меньше 4096 бит, что обычно намного меньше, чем g ^ x. Я считаю, что это могло быть более эффективно, чем прямой расчет. Также обратите внимание, что g ^ (x% i) можно вычислить быстрее, потому что мы вычислили g ^ (i + 1).
РЕДАКТИРОВАТЬ: см. этот пост . Мехрдад предлагает правильное (и лучшее) решение.
Попробуйте это модульное сокращение Монтгомери из http://code.google.com/p/bi2php/ на JavaScript.
Хотелось бы посмотреть исходные тексты вашей модифицированной библиотеки BigInt - она доступна где угодно?