Modulo function f (a, p, q) = (ap mod q)

Write a Java function for the computation of modulo operation ap mod q. You need to use the following property in Modular arithmetic:

(a b) mod c = [(a mod c) * (b mod c)] mod c

The above formula can be extended to following result:

ap mod q = (a mod q)p mod q

The idea is to use the above formulas to reduce the value ap to avoid the overflow during the calculation.

In this function the parameters a, p, and q should be declared as long type. The easiest way is to use the recursion for the implementation of the function. Here is the pseudocode:

f(a, p, q):

Check the value a and q, if a < q, skip to step c.

if a q, then use formula (2) to assign a: = (a mod q); then go to step c

Now we know that a < q. Then check the value p,

if p is even, then ap mod q = (a2 mod q )p/2 mod q;

assign a := (a2 mod q), p := p/2 and then return f(a, p, q)

if p is odd, then ap mod q = [a (a2 mod q )(p-1)/2 ] mod q;

assign b := (a2 mod q), p := (p - 1)/2 and then return [a f(b, p, q)] mod q

write Java code to perform the Modulo function f (a, p, q). test your function by using the data a = 88, p = 7, and q = 187. The result

887 mod 187 = 11.

You dont need to create any GUI interface for your code. A command line prompt like the following will be enough.

>> MyModulo

Please enter a, p, and q:

88 7 187

The result is

11