Оптимизируйте y = x * x в арифметике поля Галуа
У меня есть этот C-код для умножения над GF (8):
int32_t GaloisMultiply (int32_t a, int32_t b)
{
int32_t i;
int32_t mask = 0x100;
int32_t y = 0;
for(i=0;i<8;i++)
{
if (b & mask)
{
y ^= a;
}
mask >>= 1;
y <<= 1;
}
if (b & 0x1)
{
y ^= a;
}
return(y);
}
Это более или менее реализация из учебника.
Интересно, есть ли у меня умная оптимизация для вышеуказанного алгоритма, если я могу утверждать, что a всегда b, например Вместо умножения я занимаюсь возведением в квадрат. Кстати, я не за криптографическим использованием. Я просто хочу использовать тот факт, что x * x в GF (8) чередует биты x с нулевыми битами один за другим.
Уже есть довольно умные методы для выполнения битового чередования, но поскольку я обнаружил, что x * x в GF (8) выполняет битовое чередование (случайно), я не могу перестать пытаться использовать его для битового чередования оптимизации.
Есть идеи?
Ответы 6
Возможно, вы могли бы написать какую-нибудь сборку, чтобы сделать работу немного лучше. Однако я был бы очень удивлен, если бы это было узким местом в вашем приложении; вы делали профилирование? Эту функцию не стоит оптимизировать.
Вероятно, это не то, что вы ищете, но вот одно небольшое ускорение:
Передайте только один аргумент, если они гарантированно совпадают.
Табличный? связь
А когда вы ограничены x * x, это разреженная матрица.
Вот еще один хорошая бумага (и библиотека)
Но извините, я не думаю, что они используют эффект возведения в квадрат (битовое чередование), о котором вы говорите явно (или действительно ли его учет улучшает производительность).
Табличный метод должен быть намного быстрее независимо от того, возводите ли вы в квадрат.
Я запутался. Не могли бы вы использовать табличный подход для битового чередования 8-битных чисел, не зная поля Галуа на футбольном стадионе? Что мне не хватает?
Компилятору может немного помочь пометить "a" и "b" как const. Или развернуть петлю вручную. Хотя было бы печально, если бы это помогло ...
Кстати, разве это не патентное минное поле?
int32_t GaloisMultiply( int32_t a )
{
int32_t y = 0;
int32_t b = a & 0x01ff;
while ( b )
{
if ( b & 1 )
y ^= a;
a <<= 1;
b >>= 1;
}
return y;
}
Или, если хотите:
int32_t GaloisMultiply( int32_t a )
{
int32_t y = 0;
for ( int32_t b = a & 0x01ff; b; b >>= 1 )
{
if ( b & 1 )
y ^= a;
a <<= 1;
}
return y;
}
Причина, по которой этот подход более эффективен, чем исходный код, приведенный выше, заключается, прежде всего, в том, что цикл выполняется только до тех пор, пока не будут использованы все «интересные» биты в аргументе, в отличие от слепой проверки всех (9) битов.
Однако подход на основе таблиц будет быстрее.
Вы должны добавить некоторые подробности, почему это будет быстрее
спасибо, после того, как посмотрел, кажется, настолько коротким, насколько это возможно. Хотя я буду использовать таблицы. Это быстрее.
Таблица поиска определенно является самой быстрой для возведения в квадрат полиномиального базиса галуа. Это также самый быстрый способ умножения при использовании GF (8), но таблицы становятся слишком большими для больших полей, используемых в ECC. Для умножения в больших полях лучшим алгоритмом является метод «комбинирования слева направо» ... (см. Алгоритм 2.36 http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X, стр. 50).
Если вы используете полиномиальную арифметику для криптографии, использование таблиц поиска может быть плохой идеей. По крайней мере, если вы работаете на компьютере общего назначения. Адреса памяти, которые вы ищете, будут зависеть от значений, которые вы вычисляете, и, следовательно, задействованных наборов кешей. Существует множество статей, в которых злоумышленники неоднократно наблюдают промахи кеша и, таким образом, взламывают криптографию. В этой манере даже было несколько реальных взломов. В общем, если вы не работаете во встроенной системе, избегайте таблиц поиска.
Это действительно узкое место. Если я запускаю код на другой архитектуре, которая выполняет умножение на аппаратном уровне, я получаю до 30% ускорения.