تحسين y = x*x في حساب حقل Galois

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

على أساس الجدول؟ وصلة

وعندما تقتصر على x*x، فهي مصفوفة متفرقة.

هنا آخر ورقة جيدة (ومكتبة)

Answer 2

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 3

جدول البحث هو بالتأكيد الأسرع في تربيع جالوا على أساس متعدد الحدود.كما أنه الأسرع في الضرب عند استخدام GF(8)، لكن الجداول تصبح كبيرة جدًا بالنسبة للحقول الأكبر حجمًا كما هو مستخدم في ECC.بالنسبة للضرب في الحقول الأكبر، فإن أفضل خوارزمية هي طريقة "الدمج من اليسار إلى اليمين"...(انظر http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X الخوارزمية 2.36، الصفحة 50).

Answer 4

ربما يمكنك كتابة بعض التجميعات للقيام بعمل أفضل قليلاً.ومع ذلك، سأكون مندهشًا جدًا إذا كان هذا هو عنق الزجاجة في طلبك؛هل قمت بأي التنميط؟لا يبدو أن هذه الوظيفة تستحق التحسين.

Answer 5

ربما لا يكون هذا ما تبحث عنه، ولكن إليك بعض التسريع البسيط:

قم بتمرير وسيطة واحدة فقط، إذا تم ضمان أنها هي نفسها.

Answer 6

قد يكون من المفيد للمترجم قليلاً وضع علامة على "a" و "b" كـ const.أو فك الحلقة باليد.سيكون من المحزن إذا ساعد، على الرغم من...

أليس هذا حقل ألغام براءات الاختراع، بالمناسبة؟