計算する方法が必要です：
(g^u * y^v) mod p
Javaで。
（g ^ u）modpを計算するためのこのアルゴリズムを見つけました。
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;
}
それはうまく機能しますが、私はこれを行う方法を見つけることができないようです
(g^u * y^v) mod p
私の数学のスキルはつまらないので。
コンテキストに入れると、「縮小された」DSAのJava実装用です。検証部分では、これを解決する必要があります。
2つの要素がオーバーフローしないと仮定すると、次のようにこのような式を単純化できると思います。
(x * y) mod p = ( (x mod p)*(y mod p) ) mod p。そこから理解できると思います。
このコードのフラグメントは、よく知られている「高速べき乗」アルゴリズムを実装します。これは、2乗によるべき乗としても知られています。
また、（a * b）mod p =（（a mod p）*（b mod p））modpという事実も使用します。（加算と乗算の両方が素数モジュラスを取ることで保存された構造です-それは準同型です）。このようにして、アルゴリズムのすべてのポイントで、pよりも小さい数に減少します。
これらをループでインターリーブ方式で計算することはできますが、実際に計算するメリットはありません。それらを別々に計算し、それらを掛け合わせて、最後にもう一度modを取得します。
p ^ 2が表現可能な最大のintより大きい場合はオーバーフローが発生し、これにより間違った答えが返されることに注意してください。Javaの場合、大きな整数に切り替えるのが賢明かもしれません。あるいは、少なくともpのサイズを実行時にチェックして、例外をスローするのが賢明かもしれません。
最後に、これが暗号化の目的である場合は、自分で実装するのではなく、ライブラリを使用してこれを行う必要があります。動作しているように見えるわずかに間違ったことを行うのは非常に簡単ですが、セキュリティは最小限またはまったく提供されません。
試す
（Math.pow（q、u）* Math.pow（y、v））％p