Оптимизация y = x*x в арифметике поля Галуа

StackOverflow https://stackoverflow.com/questions/117352

Вопрос

У меня есть этот 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» как константные.Или разворачивая петлю вручную.Хотя было бы грустно, если бы это помогло...

Кстати, разве это не патентованное минное поле?

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top