Tối ưu hóa nhân modulo số nguyên tố nhỏ

Question

tôi cần phải làm các thao tác sau đây nhiều lần:

1. Hãy hai số nguyên a, b
2. Tính a * b mod p, nơi p = 1000000007 và a, b là của cùng một thứ tự của tầm quan trọng như p

Cảm giác ruột của tôi là ngây thơ

result = a * b 
result %= p 

không hiệu quả. Tôi có thể tối ưu hóa mô đun nhân số p giống như hàm mũ modulo p được tối ưu hóa với pow(a, b, p)?

Answer 1

Để thực hiện phép tính này khi lắp ráp, nhưng có thể gọi từ Python, tôi muốn thử inline assembly từ số Python module written in C. Cả hai GCC và MSVC trình biên dịch tính năng lắp ráp nội tuyến, chỉ với cú pháp khác nhau.

Lưu ý rằng mô-đun của chúng tôi p = 1000000007 chỉ vừa với 30 bit. Kết quả mong muốn (a*b)%p có thể được tính trong các thanh ghi Intel 80x86 cho một số hạn chế yếu trên a,b không lớn hơn nhiều so với p.

Hạn chế về kích thước của a,b

(1) a,b là 32-bit số nguyên unsigned

(2) a*b là ít hơn p << 32, ví dụ:p lần 2^32

Cụ thể nếu a,b mỗi số ít hơn 2*p, sẽ không thể tràn. Cho (1), nó cũng đủ rằng một trong số chúng nhỏ hơn p.

Hướng dẫn Intel 80x86 MUL có thể nhân hai số nguyên không dấu 32 bit và lưu trữ kết quả 64 bit trong cặp đăng ký tích lũy EDX: EAX. Một số chi tiết và các câu hỏi về MUL được thảo luận trong Mục 10.2.1 của mục này hữu ích summary.

Lệnh DIV sau đó có thể chia kết quả 64 bit này bằng hằng số 32 bit (mô đun p), lưu trữ thương trong EAX và phần còn lại trong EDX. Xem Phần 10.2.2 của liên kết cuối cùng. Kết quả chúng tôi muốn là phần còn lại. Đó là hướng dẫn phân chia DIV này đòi hỏi phải có nguy cơ tràn, nên sản phẩm 64 bit trong tử số EDX: EAX cho một thương lớn hơn 32 bit do không thỏa mãn (2) ở trên.

Tôi đang làm việc trên đoạn mã trong phần C/inline assembly cho "bằng chứng khái niệm". Tuy nhiên, lợi ích tối đa về tốc độ sẽ phụ thuộc vào việc sắp xếp các mảng dữ liệu a,b để xử lý, phân bổ chi phí cho các cuộc gọi hàm, v.v. Python (nếu đó là nền tảng đích).

Answer 2

Mặc dù đây là trivally đơn giản, bạn có thể thử nó và tiết kiệm thời gian trên bước mod p bằng cách xây dựng một danh sách các sản phẩm dựa trên 1000000007 (kích thước của danh sách phụ thuộc vào kích thước của a và b). Kiểm tra modulo trên mỗi cái (bắt đầu với giá trị cao nhất). Cấp, điều này chỉ giúp nếu a & b >= sqrt(p) * 2.

Answer 3

Bạn đề cập rằng "a, b có cùng thứ tự độ lớn như p." Thường trong mật mã học, điều này có nghĩa là a,b là số lớn gần p, nhưng nhỏ hơn p.

Nếu đây là trường hợp, sau đó bạn có thể sử dụng danh tính đơn giản

để biến tính của bạn vào

result = ((a-p)*(b-p))%p 

Bạn đã rồi quay một nhân lớn thành hai subtractions lớn và một phép nhân nhỏ. Bạn sẽ phải xem hồ sơ để xem nhanh hơn.

Answer 4

Điều này không trả lời trực tiếp câu hỏi, nhưng tôi khuyên bạn không nên làm điều này bằng Python thuần túy nếu bạn đang tìm kiếm hiệu suất. Một số tùy chọn:

• Tạo một thư viện nhỏ bằng C để tính toán và sử dụng Python ctypes để nói chuyện với nó.
• Sử dụng numpy; có lẽ là lựa chọn tốt nhất nếu bạn muốn tránh phải tự mình giải quyết vấn đề. Thực hiện một thao tác tại một thời điểm sẽ không nhanh hơn các toán tử riêng của Python, nhưng nếu bạn có thể đặt nhiều toán tử trong một mảng phức tạp, các phép tính trên chúng sẽ nhanh hơn nhiều so với Python tương đương.
• Sử dụng cython để khai báo các biến của bạn dưới dạng số nguyên C; một lần nữa, giống như numpy, bạn sẽ được hưởng lợi từ điều này nhiều nhất nếu bạn làm điều đó theo lô (bởi vì sau đó bạn cũng có thể tối ưu hóa vòng lặp).

Answer 5

Có thể có một đầu mối để tối ưu hóa nếu bạn làm rõ những gì bạn có ý nghĩa bởi nhiều lần, ví dụ như nếu bạn đang thu thập các kết quả từ một vòng lặp tần số cao, vòng lặp có thể cung cấp các phương tiện để tối ưu hóa thói quen của bạn.

Nói vòng lặp được tối ưu hóa là:

p = 1000000007 
b = 123456789 
a = 0 
while a < p: 
    result = (a * b) % p 
    dosomething(a, b, result) 
    a += 1 

bạn có thể tối ưu hóa ra * và% so với vòng lặp tần số cao:

p = 1000000007 
b = 123456789 
a = 0 
result = (a * b) % p 
while a < p: 
    dosomething(a, b, result) 
    a += 1 
    result += b 
    if result >= p: 
     result -= p