Assume a fully connected graph of N nodes $0...$ N $1$ of the sort defined in

Assignment $2.$ The initiator node creates and sends a message along a path through the

graph to a receiver node; it defines this path using the inverse function f

$1$

$()=$ g$()$ of

Equation $(2).$ Intermediate nodes use the function f$()$ of Equation $(1)$ to determine

which node to forward the message to$.$

The process of the initiator creating a path is as follows: To transmit a message m to a

receiver v$,$ initiator v$0$ first chooses a desired path length n and calls vn :$=$ v the receiver.

It then goes to choose a value rn $$ vn mod N$,$ and backward iterates rn$1=$ f

$1$

$($rn$)$ until

it reaches a value r$1.$ The first node to transmit the message to is thus v$1=$ r$1$ mod N$.$

Consider the example from the assignment specs, where initiator node v$0=1$ sends a

message through a path of length $3$ to receiver node v$3=6$: the path through the graph

was found to be $1->4->10->6.$ For a path of length $4$ between the same initiator and

receiver, the path is $1->18->4->10->6.$

Write a function as defined below that calculates the value r$1.$

public Integer firstR$($Integer k$,$ Integer v$,$ NodeTransitionFunction fInv$)\{$

$//$ PRE: k is number of steps, v is destination node ID$,$ fInv is the inverse of f$()$

$//$ POST: Uses the trapdoor function inverse fInv, applied to destination node v

$//$ with number of steps k$,$ to calculate the node path;

$//$ returns value of r that determines first step on node path

$\}$

Note: The trapdoor function inverse can be calculated by instantiating NodeTransitionFunction

with parameters d and K $($rather than the forward direction version instantiated with e

and K$).$