Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Можно поюзать таблицу умножения наоборот.
20.03.04 02:47 Число просмотров: 4994
Автор: Xelator Статус: Незарегистрированный пользователь
|
> 2) Как брать остатки от деления на лажевые числа мерсена > типа > 2^192 - 2^64 - 1 (не проводя самого деления, быстро). От > нормальных чисел мерсена легко брать, а от этих – не знаю > как. Можно поюзать таблицу умножения наоборот.
У вас трехчлен, т.е. надо будет разбить делимое на блоки, смотреть на значение блока, по нему выбирать кусок множителя, после чего блок можно занулить, и в соответствующих местах прибавить части кусок множителя на младшие члены делителя, в вашем примере:
r = d / (2^192-2^64-1), найти m такой что m*2^192 равен нескольким битам в d (количество бит равно как бы разрядности таблицы умножения), соответсвенно r1 = m1 - 2^64*m -m;где m1 = d - m*2^192.
Придется немного чиселки подвигать и "поксорить" пока d не станет меньше 2^192...
> 3) Формулки для сложения и удвоения точек содержат деление > по модулю-обратные элементы. Это ведь ОЧЧЕНЬ долго кажный > раз вычислять (взять хоть евклида, хоть степень p-2)!!! > Забыл как... кажется если взять p-2 а бинарные степени все сохранить, ну вроде того, что (p-2) = sum(j=0,k)(2^j) то там должно быть нормально - быстрое возведение в степень - это просто "раздвигание" битов на четные позиции (если мы в нормальном базисе?!).... я попробую повспоминать...
|
|
|