Оптимизировать у = х * х в поле Галуа арифметического

Question

У меня есть этот 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) делает операцию чередования бит (случайно), я не могу перестать пытаться ее использовать для оптимизации чередования бит.

Любые идеи?

Answer 1

Настольный? link

И когда вы ограничены x * x, это разреженная матрица.

Вот еще good paper (and a library)

Answer 2

Возможно, вы можете написать сборку, чтобы немного улучшить работу. Однако я был бы очень удивлен, если бы это было узким местом в вашем приложении; вы сделали какие-либо профилирования? Эта функция не кажется оптимальной.

Answer 3

Это, вероятно, не то, что вы ищете, но вот один несовершеннолетний убыстрение:

Передавать только один аргумент, если они гарантированно будут одинаковыми.

Answer 4

Это может помочь компилятору немного, чтобы отметить «а» и «б» константным. Или разматывать петлю вручную. Было бы грустно, если бы это помогло, хотя ...

Разве это не патентное минное поле, между прочим?

Answer 5

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) бит.

Настольный подход будет быстрее.

Answer 6

Таблица поиска, безусловно, самая быстрая для построения полиномиальных оснований. Он также является самым быстрым для умножения при использовании GF (8), но таблицы становятся слишком большими для больших полей, используемых в ECC. Для умножения в больших полях лучшим алгоритмом является метод «слева направо» ... (см. Алгоритм http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X 2.36, с. 50).