갈루아 필드 산술에서 y = x*x 최적화

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

문제

GF(8)에 대한 곱셈을 수행하는 C 코드가 있습니다.

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라고 주장할 수 있다면 위의 알고리즘에 대한 영리한 최적화가 있는지 궁금합니다.곱셈 대신 제곱을 합니다.나는 암호화 사용 btw를 따르지 않습니다.나는 GF(8)의 x*x가 x의 비트를 0비트로 하나씩 인터리브한다는 사실을 활용하고 싶습니다.

비트 인터리빙을 수행하는 꽤 영리한 방법이 이미 있지만 GF(8)의 xx*x가 (우연히) 비트 인터리빙 작업을 수행한다는 것을 알았으므로 비트 인터리빙에 사용하려는 시도를 멈출 수 없습니다. 최적화.

어떤 아이디어가 있나요?

도움이 되었습니까?

해결책

테이블 기반? 링크

그리고 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"를 const로 표시하는 데 도움이 될 수 있습니다.아니면 손으로 고리를 풀어보세요.도움이 되었다면 아쉽겠지만...

그건 그렇고, 특허 지뢰밭이 아닌가?

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top