Design and Analysis of Algorithms

Computation Models and Design by Refi nement 119

5.30 Establish the correctness of the expmod func-

tion defi ned in Example 21, by the following

steps.

(i) Show that for x, y,m ∈ P, (xy mod m) =

(x mod m)(y mod m).

(ii) Prove the correctness of the expmod

function using PMI.

5.31 Show that the time complexity of the expmod

function defi ned as in Example 21, is

O(lg e) . Consequently, the Fermat’s test can

be conducted once in O(lg n) time. Thus the

time complexity of the overall algorithm is

O(q lg n) where q is the maximum number of

times the Fermat’s test has to be applied.

5.32 Given that ∈ is the acceptable probability of

error in declaring ...