Lũy thừa Modular trong Java

Question

Tôi cần một cách để tính toán:

(g^u * y^v) mod p 

trong Java.

tôi đã tìm thấy thuật toán này để tính (g^u) mod p:

int modulo(int a,int b,int c) { 
    long x=1 
    long y=a; 
    while(b > 0){ 
     if(b%2 == 1){ 
      x=(x*y)%c; 
     } 
     y = (y*y)%c; // squaring the base 
     b /= 2; 
    } 
    return (int) x%c; 
} 

và nó hoạt động tuyệt vời, nhưng tôi dường như không thể tìm thấy một cách để làm điều này cho

(g^u * y^v) mod p 

vì kỹ năng toán học của tôi kém chất lượng.

Để đặt nó trong ngữ cảnh, đó là cho một thực hiện java của một DSA "giảm" - phần xác minh yêu cầu điều này phải được giải quyết.

Answer 1

Giả sử rằng hai yếu tố này sẽ không tràn, tôi tin bạn có thể đơn giản hóa một biểu thức như vậy theo cách này:

(x * y) mod p = ((x mod p)*(y mod p)) mod p. Tôi chắc rằng bạn có thể tìm ra từ đó.

Answer 2

Hãy thử

(Math.pow (q, u) * Math.pow (y, v))% p

Answer 3

Đoạn mã đó thực hiện thuật toán "lũy thừa nhanh" nổi tiếng, còn được gọi là Exponentiation by squaring.

Nó cũng sử dụng thực tế là (a * b) mod p = ((a mod p) * (b mod p)) mod p. (Cả hai bổ sung và phép nhân được bảo tồn cấu trúc dưới một mô đun chính - đó là một homomorphism). Bằng cách này, tại mọi điểm trong thuật toán, nó giảm xuống các số nhỏ hơn p.

Trong khi bạn có thể thử tính toán những điều này theo kiểu xen kẽ trong một vòng lặp, thì không có lợi ích thực sự để làm như vậy. Chỉ cần tính chúng một cách riêng biệt, nhân chúng lại với nhau và lấy mod lần cuối.

Được cảnh báo rằng bạn sẽ bị tràn nếu p^2 lớn hơn int thể hiện lớn nhất và điều này sẽ khiến bạn có câu trả lời sai. Đối với Java, việc chuyển sang số nguyên lớn có thể thận trọng, hoặc ít nhất là kiểm tra thời gian chạy trên kích thước của p và ném một ngoại lệ.

Cuối cùng, nếu điều này là dành cho mục đích mã hóa, có thể bạn đang sử dụng thư viện để thực hiện việc này, thay vì tự thực hiện nó. Nó rất dễ dàng để làm một cái gì đó hơi sai mà dường như làm việc, nhưng cung cấp tối thiểu để không có bảo mật.