Question

This is an Intro to Java Question, Please respond with code and pseudocode.

Problem 3: RSA Private Key (10 points) (Cyber Security)

In the RSA algorithm, encrypting and decrypting a message is done using a pair of numbers that are multiplicative inverses with respect to a carefully selected modulus. In this task, you must calculate the modular multiplicative inverse for given set of values. What is the Modular Multiplicative Inverse? In mathematics, each operation typically has an inverse. For example, the inverse of multiplication is division and the inverse of addition is subtraction. Likewise, modulus has an inverse expression. The basic expression given is: Solve for x, Given an integer a and modulo m where ax % m = 1 . However, solving for x is not a trivial task. One naive approach is to bruteforce a solution for x by simply trying each number starting at 1 until a solution is found that makes the expression true.

Facts

● Solve for x, when (a*x) % m == 1 and where a and m are given.

● Use a Brute force approach: First try 1 for x, and check for validity. if invalid then continue to increase x until you find a valid value for x that makes the expression true.

● Consider using long data types instead of int

Input

first line of input is the number of test cases. Each line thereafter, consists of two positive long integer inputs. The first represents the integer a, the second represents the modulo m.

Output Your program should print the value of x that makes the Modular Multiplicative Inverse expression true.

Sample Input

3

17 20

3 7

131101 524269

Sample Output

13

5

229125

Answer 1

PseudoCode:

Input t

Input a,m

Initialize x=1

while loop(infinite)

if a*x % m==1

break the loop

store x in an array ans

for i in ans

print i

Solution:

import java.util.Scanner;
public class Main
{
   public static void main(String[] args) {
       Scanner in=new Scanner(System.in);
       System.out.print("Enter number of test cases:");
      
       //Scanning input
       int t=in.nextInt();
       long ans[]=new long[t];
       int j=0;
      
       while(t!=0)
       {
       long a=in.nextLong();
       long m=in.nextLong();
      
       int x=1;
       while(true)
       {
       //Checking for condition
       if((a*x)%m==1)
       break;
       x++;
       }
       //Storing x
       ans[j]=x;
       j=j+1;
       t--;
       }
       System.out.println();
       //Printing x for each case
       for(long i:ans)
       System.out.println(i);
      
   }
}

Output: