Phép nhân nhanh modulo 2^16 + 1

Question

Mật mã IDEA sử dụng phép nhân modulo 2^16 + 1. Có một thuật toán để thực hiện thao tác này mà không có toán tử modulo chung (chỉ modulo 2^16 (cắt ngắn))? Trong bối cảnh IDEA, số 0 được hiểu là 2^16 (có nghĩa là không phải là đối số của phép nhân của chúng ta và nó không thể là kết quả, vì vậy chúng ta có thể tiết kiệm một chút và lưu trữ giá trị 2^16 làm mẫu bit 0000000000000000). Tôi tự hỏi làm thế nào để thực hiện nó một cách hiệu quả (hoặc cho dù nó có thể ở tất cả) mà không cần sử dụng các nhà điều hành modulo tiêu chuẩn.

Answer 1

Bạn có thể sử dụng thực tế, rằng (N-1)% N == -1.

Do đó, (65536 * a)% 65.537 == -a% 65537.
Ngoài ra, -a% 65.537 == -a + 1 (mod 65536), khi 0 được hiểu là 65536

uint16_t fastmod65537(uint16_t a, uint16_t b) 
{ 
    uint32_t c; 
    uint16_t hi, lo; 
    if (a == 0) 
     return -b + 1; 
    if (b == 0) 
     return -a + 1; 

    c = (uint32_t)a * (uint32_t)b; 
    hi = c >> 16; 
    lo = c; 
    if (lo > hi) 
     return lo-hi; 
    return lo-hi+1; 
} 

vấn đề duy nhất ở đây là nếu hi == lo, kết quả sẽ là 0. may mắn một bộ kiểm tra xác nhận, rằng nó thực sự không thể ...

int main() 
{ 
    uint64_t a, b; 
    for (a = 1; a <= 65536; a++) 
     for (b = 1; b <= 65536; b++) 
     { 
      uint64_t c = a*b; 
      uint32_t d = (c % 65537) & 65535; 
      uint32_t e = m(a & 65535, b & 65535); 
      if (d != e) 
       printf("a * b % 65537 != m(%d, %d) real=%d m()=%d\n", 
         (uint32_t)a, (uint32_t)b, d, e); 
     } 
    } 

Output: none

Answer 2

Thứ nhất, trường hợp a hoặc b bằng không. Trong trường hợp đó, nó được xem như là có giá trị 2^16, do đó tiểu học modulo số học cho chúng ta biết:

result = -a - b + 1; 

, bởi vì (trong bối cảnh của IDEA) các nghịch đảo của 2^16 vẫn là 2^16, và 16 bit thấp nhất của nó là tất cả các số không.

Các trường hợp chung là dễ dàng hơn nhiều so với có vẻ như, bây giờ mà chúng tôi đã chăm sóc của "0" trường hợp đặc biệt (2^16 + 1 là 0x10001):

/* This operation can overflow: */ 
unsigned result = (product & 0xFFFF) - (product >> 16); 
/* ..so account for cases of overflow: */ 
result -= result >> 16; 

Đưa nó với nhau:

/* All types must be sufficiently wide unsigned, e.g. uint32_t: */ 
unsigned long long product = a * b; 
if (product == 0) { 
    return -a - b + 1; 
} else { 
    result = (product & 0xFFFF) - (product >> 16); 
    result -= result >> 16; 
    return result & 0xFFFF; 
}