Question

Write a program(Java) to compute modular exponentiation: take g (base), e (exponent), and, N (modulas) as input from the user and output the result. Use an online compiler. Do not use the inbuilt functions to compute this. Also, try to make the program as efficient as possible. In particular, please implement the square and multiply algorithm discussed in the class.


Answer 1

Program:

//This is the program to calculate (x^y)%p in O(log y) time complexity

import java.io.*;

public class Main{

static int calculate(int x ,int y,int p){

//initialise result

int res=1;

x=x%p; //updating x if x is more than or equal to p

if(x==0)

return 0; //in case x is divisible by p

while(y>0){

if((y&1)==1) //checking if y is odd

res=(res*x)%p; //multiplying x with res

y=y>>1; //y must be even now so y=y/2

x= (x * x) % p;

}

return res;

}

public static void main( String args[])

{

Scanner s=new Scanner(System.in);

int g,e,N;

System.out.print("Enter base(g):");

g=s.nextInt();

System.out.print("Enter exponent(e):");

e=s.nextInt();

System.out.print("Enter modulas(N):");

N=s.nextInt();

System.out.print("Modular Exponentiation is:"+calculate(g,e,N));

}

}

Program screenshot:

Output:

Hope you understand.....

If ou have any doubts comment below....plss dont dislike......