Suppose that we want to compute the value of the expression a d mod n for positi

Question

Suppose that we want to compute the value of the expression

ad mod n

for positive integers a, d, and n, where a and d are guaranteed to belong to {1, 2, . . . , n1}. Since a and d are both guaranteed to be less than n, we know that the input size is (log n). Therefore, an efficient (i.e., polynomial time) algorithm for the problem is one that runs in O(logc n) for some constant c. In this problem you are required to design and implement an O(log3 n)-time algorithm. In practical terms, I want your function to be able to run very fast (essentially instantaneously) on pretty large numbers, e.g., numbers with roughly 100 digits. Specifically, I want you to implement a function – let us call it bigPowerMod – that takes as arguments a, d, and n and returns a d mod n. There are two efficiency-related issues to pay attention to.

(i) It is possible to compute a d by performing d1 multiplications. But, this is too many because d1 can be as large as n2 and therefore performing so many multiplications would take (n) time. For another way of seeing how inefficient this would be suppose that n is a 100-digit number, then your program would be performing, roughly 10100 multiplications, which would literally take forever!

(ii) While your final answer is an integer in the range [0, n 1] (because of the mod n), you have to watch out for the size of intermediate answers. When we mutiply a number with b bits with another number with b 0 bits, the answer can have answer many as b+b 0 bits. This means that if a has log2 n bits, then a2 can have 2 log2n bits, a3 can have 3 log2 n bits, and so on. Thus ad can have d log n bits, which is (n log n) in the worst case. Again, if n is a 100-digit number, this amounts to more that 10100 bits (which is more than the number of atoms in the universe!). Of course, carrying such large intermediate answers around also means that each multiplication will take forever.

You can use divide-and-conquer to solve the first problem. Here is a hint: to compute ad , you can (recursively) compute ad/2 and after that it takes one or two multiplications, depending on whether d is even or odd, to compute a d . This approach allows you to compute ad mod n using O(log d) multiplications. To solve the second problem, you should note that you can perform mod n as soon as you get intermediate answers rather than wait to compute mod n at the very end. This is because of the following property of mod : (a · b · c) mod n = ((a · b) mod n) mod n.

(a) Print and submit your code. No matter what programming language you use, I expect that your function will be no more than 10 lines long. Make sure your code is well documented.

(b) Let n be the following 100-digit number. 29085119528125578724347048203972299284505302539901 58990550731991011846571635621025786879881561814989 Use the function bigPowerMod to compute (n 100)n-1mod n. Report the answer you get.

(c) Provide an argument for why the running time of your algorithm/code is O(log3 n)

Please submit the code in Java or at the very least write pseudocode and I can write the actual code. Thank you

Explanation / Answer

Complete Program:

// File: BigIntegerMod.java
import java.math.BigInteger;
public class BigIntegerMod
{
public static void main(String[] args)
{
  BigInteger n = new BigInteger("2908511952812557872434704820397229928450530253990158990550731991011846571635621025786879881561814989");
  
  BigInteger bi1 = new BigInteger("100");
  BigInteger bi2 = new BigInteger("1");
  
  BigInteger a = n.subtract(bi1);
  BigInteger d = n.subtract(bi2);
  
  System.out.println("a = " + a);
  System.out.println("d = " + d);
  System.out.println("n = " + n);
  
  // by using predefined method of BigInteger class
  System.out.println("a^d mod n = " + bigPowerMod(a, d, n));
  
  // by user defined method
  System.out.println("a^d mod n = " + bigPowerMod2(a, d, n));
}

public static BigInteger bigPowerMod(BigInteger a, BigInteger d, BigInteger n)
{
  return a.modPow(d, n);
}

public static BigInteger bigPowerMod2(BigInteger a, BigInteger d, BigInteger n)
{
  BigInteger result = new BigInteger("1");
  BigInteger k = new BigInteger("1");
  
  while(k.compareTo(d) <= 0)
  {
   result = result.multiply(a);
   result = result.mod(n);
   
   k = k.add(new BigInteger("1"));
  }
  
  return result;
}
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.