Оптимизация y = x*x в арифметике поля Галуа
-
02-07-2019 - |
Вопрос
У меня есть этот 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) выполняет чередование битов (случайно), я не могу перестать пытаться использовать его для чередования битов. оптимизации.
Есть идеи?
Решение
На основе таблиц? связь
А когда вы ограничены x*x, это разреженная матрица.
Вот еще один хорошая бумага (и библиотека)
Другие советы
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.Для умножения в больших полях лучшим алгоритмом является метод объединения слева направо... (см. http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X алгоритм 2.36, стр. 50).
Вероятно, вы могли бы написать какую-нибудь сборку, чтобы сделать работу немного лучше.Однако я был бы очень удивлен, если бы это было узким местом вашего приложения;ты делал какое-нибудь профилирование?Эту функцию, похоже, не стоит оптимизировать.
Вероятно, это не то, что вы ищете, но вот одно незначительное ускорение:
Передавайте только один аргумент, если они гарантированно будут одинаковыми.
Компилятору может быть немного полезно пометить «a» и «b» как константные.Или разворачивая петлю вручную.Хотя было бы грустно, если бы это помогло...
Кстати, разве это не патентованное минное поле?