Phép nhân và phép trừ nhanh modulo một số nguyên tố

Question

Tôi cần tối ưu hóa một số mã mà tôi nhân một vectơ ints (32 bit) bởi một modul p vô hướng (trong đó p là số nguyên tố (2^32) -5) và sau đó trừ vector đó từ một vector khác p.

Mã này trông như thế này:

public static void multiplyAndSubtract(long fragmentCoefficient, long[] equationToSubtractFrom, long[] equationToSubtract) { 
    for (int i = 0; i < equationToSubtractFrom.length; i++) { 
     equationToSubtractFrom[i] = modP(equationToSubtractFrom[i] - multiplyModP(fragmentCoefficient, equationToSubtract[i])); 
    } 
} 

Tôi đang sử dụng chờ đợi vì Java không hỗ trợ số nguyên unsigned nhưng cả hai vectơ là mod p, do đó bạn có thể mong đợi mỗi số là 0 < = x < (2^32) -5

Bất kỳ ý tưởng nào để tối ưu hóa điều này? Các hoạt động mod mod là những gì chiếm hầu hết thời gian thực hiện vì vậy một cách để tối ưu hóa điều này có thể bằng cách nào đó không làm modP sau khi nhân và chỉ làm điều đó sau khi trừ. Bất kỳ ý tưởng về cách làm điều đó?

Answer 1

Có thể tăng tốc độ tính toán và tránh bất kỳ sự phân chia nào bằng cách sử dụng thực tế là 2^32 = 5 (mod p).

Sau phép nhân và phép trừ, chia kết quả thành các phần thấp (x% 2^32) và hi (x/2^32). Sau đó nhân phần hi thành 5 và cộng với phần thấp. Sau đó lặp lại quy trình này một lần nữa. Nếu kết quả lớn hơn p, trừ p. Đối với kết quả âm, thêm p.

Chỉnh sửa: Vì phép nhân và phép trừ kết hợp có thể tràn, nên kết quả phép nhân cũng được thực hiện bằng modulo p. Nhưng chỉ một bước của quy trình trên là đủ: chỉ cần chia nhỏ, nhân với 5 và thêm.

Answer 2

e - (f * e mod p) mod p = (e-e f) mod p 

Xem Wolfram Alpha.

Answer 3

Tôi biết trong hai cách để làm điều này mà không sử dụng bộ phận hoặc mô đun:

Phương pháp 1: Bất Biến Nhân. (see this paper)

Ý tưởng cơ bản ở đây là để tính toán trước và xấp xỉ của đối ứng của p cho phép bạn làm một phép chia số nguyên chỉ sử dụng một vài phép nhân số nguyên. Sau đó, bạn có thể nhân trở lại và có được mô-đun của bạn. Đây là cách tiếp cận dễ thực hiện hơn.

Cách 2: (là người mà tôi thường sử dụng), là sử dụng dấu chấm động. Chuyển đổi các số sang dấu phẩy động và nhân với một đối ứng được tính trước của p. Sau đó, tròn và chuyển đổi trở lại một số nguyên. Cách tiếp cận này khó đạt được hơn, nhưng từ kinh nghiệm của tôi thì nó nhanh hơn nếu được thực hiện đúng cách.

Cả hai cách tiếp cận ở đây không liên quan đến việc phân chia trước tính toán nghịch đảo trong số nguyên hoặc dấu phẩy động.

Có hoặc không một trong các phương pháp này sẽ nhanh hơn sử dụng thẳng về phía trước %, sẽ tùy thuộc vào mức độ bạn có thể triển khai chúng. Vì vậy, tôi không thể đảm bảo rằng một trong hai sẽ nhanh hơn.