Регистрация Войти
Рейтинг:2
Myria avatar Crypto

Существует ли алгоритм для вычисления wNAF для показателя степени быстрее, чем квадратичный?

флаг in
Myria

Для возведения в степень в группе, для которой инверсия тривиально проста, такой как группы эллиптических кривых, существует ли алгоритм для вычисления $w$НАФ ("$w$-арная несмежная форма") быстрее, чем $ О (п ^ 2) $? стандартный алгоритм указан в Википедии как (в переводе на Python):

определение wnaf(d):
    результат = []
    для я в диапазоне (256):
        если д & 1:
            ди = моды (д)
            д -= ди
            результат += [ди]
        еще:
            результат += [0]
        г >>= 1
    вернуть результат[::-1]

Квадратичная часть здесь такова, что ди может быть отрицательным, превращая вычитание в сложение. Это может быть доведено до начала числа, поэтому обработка всего значения г потенциально необходимо для каждой итерации, что делает алгоритм квадратичным по количеству битов.

Есть лучший способ это сделать?

50
0 + 0
Рейтинг:2
Daniel S avatar Crypto
флаг ru
Daniel S

Забавный вопрос! Ответ положительный. Хитрость заключается в том, чтобы изменить цикл в соответствии со знаком последнего окна. Если последнее окно было положительным, мы пропускаем 0 и останавливаемся на следующем 1; если последнее окно было отрицательным, мы пропускаем 1 с и останавливаемся на следующем 0 и переворачиваем его. Я думаю, что есть также последний шаг как для этого, так и для алгоритма, указанного в вопросе, где, если последнее окно отрицательное, нам нужно добавить 1. Вот мой лучший удар по некоторому python для окон ширины $w$.

защита wnaf2(d):
    результат = []
    знак = 0
    в то время как д !=0:
        если (d & 1) ^ знак:
            ди = моды (d ^ знак)
            sign = (d>>(w-1)&1) # Есть смысл добавить это в функцию модов
            d = d>>w # Просто стереть последнее окно без переносов
            результат += [ди]
            результат += (w-1)*[0]
        еще:
            результат += [0]
            г >>= 1
    если знак:
        результат += [1]
    вернуть результат[::-1]

Это линейно при условии, что мы считаем сдвиги и маскируем как $O(1)$ операции.

0 + 0
Myria avatar
флаг in
Myria
Сдвиги и маскирование составляют $O(1)$ в реальной реализации (т.е. не в Python), потому что вместо фактического сдвига всего `d` мы можем просто индексировать байты и биты. Это решает проблему, которая у меня была. Спасибо!
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.