I can not implement the following algorithm in Java:

Modulation Expression Algorithm

With x=5 , y=2 , N=4 gives the correct result, with x=5 , y=10 , N=11 - wrong.

 public static double modPower(double x, double y, int N) { if(y==0) return 1; double z = modPower(x, y/2, N); if ((y % 2) == 0) return (z*z)%N; else return (x*z*z)%N; }
  • one
    Why double ? In my opinion, I mean integer operations ... - Harry
  • And why is there a recursive algorithm, IMHO normal cycle is clearer. - pavel

2 answers 2

The numbers x, y and others should be integers .

Roughly speaking, what is 3.1415 % 2 , in your opinion? :) Or y/2 in the third line - this is not at all what is meant in the description of the algorithm ...

  • one
    I will add that x z z is better divided into 2 operations, ((x * z)% N * z)% N and use long non int - pavel
  • I did not understand a little about the 3rd line - what exactly should be there. Initially, everything was int, it was also wrong, with a double I just decided to play. - Anon
  • @ Anon A division is an integer (roughly, 8 divided by 3 is 2) and floating-point (5.0 divided by 2 is 2.5). Is the hint clear? :) - Harry
  • Thank. It is clear - Anon

Considering that the input is specified as n -bit numbers with no explicit boundary for n , you should probably use BigInteger instead of double :

 static BigInteger modExp(BigInteger base, BigInteger exponent, BigInteger m) { int trailing_zero_bits_count = exponent.getLowestSetBit(); if (trailing_zero_bits_count == -1) // exponent == 0 return BigInteger.ONE.mod(m); BigInteger z = modExp(base, exponent.shiftRight(1), m); // base**(exponent//2)% m BigInteger z_sq = z.pow(2).mod(m); // z**2 % m if (trailing_zero_bits_count != 0) // even return z_sq; return z_sq.multiply(base).mod(m); // z**2 * base % m }

It is worth noting that this code returns zero, not one for modExp(x, 0, 1) that is, if y == 0 , then the code does not return 1 as in the question condition is mistakenly indicated — if N == 1 , because 1 % 1 == 0 .