Question

***Code to solve***

package functions;

import java.math.*; // for BigInteger

public class NodeTransitionFunction {

   public NodeTransitionFunction(Integer exp, Integer KVal) {
       // CONSTUCTOR: Sets the class to calculate f(x) = (x ^ exp) mod KVal

       // TODO
   }
  

  
  
   public Integer apply(Integer val) {
       // PRE: -
       // POST: Implements f(val)
       return null;
   }
  

   public BigInteger apply(BigInteger val) {
       // PRE: -
       // POST: Implements f(val), with val as a BigInteger

       // TODO
      
       return null;
   }

  
   public static void main(String[] args) {
       NodeTransitionFunction f = new NodeTransitionFunction(3, 33);
      
       System.out.println(f.apply(5));
   }
  
}

Note that if you implement apply() in a straightforward way, you will almost certainly exceed Java's Integer.MAX_VALUE: try it for yourself with an instance of NodeTransitionFunction instantiated with values 3 and 33, comparing it against the value obtained from e.g. a spreadsheet. Instead, there is a useful identity that lets you make the calculation without this risk: (3) (ab) mod p = ((a mod p)(b mod p)) mod p Implement apply () using this identity.8

Answer 1

package functions;

import java.math.*; // for BigInteger

public class NodeTransitionFunction {

    private Integer exp;
    private Integer KVal;

    public NodeTransitionFunction(Integer exp, Integer KVal) {
        // CONSTRUCTOR: Sets the class to calculate f(x) = (x ^ exp) mod KVal
        this.exp = exp;
        this.KVal = KVal;
    }

    public Integer apply(Integer val) {
        Integer result = 1;
        for (int i = 0; i < exp; i++) {
            result *= val % KVal;
        }
        return result % KVal;
    }


    public BigInteger apply(BigInteger val) {
        BigInteger result = BigInteger.valueOf(1);
        for (int i = 0; i < exp; i++) {
            result = result.multiply(val);
        }
        return result.mod(BigInteger.valueOf(KVal));
    }


    public static void main(String[] args) {
        NodeTransitionFunction f = new NodeTransitionFunction(3, 33);
        System.out.println(f.apply(5));
    }
}