The fast exponentiation algorithm described in chapter 2 is at a high-level. Spe

Question

The fast exponentiation algorithm described in chapter 2 is at a high-level. Specify and show the computation steps for the Big O of both the algorithms. Please comment your pseudocode well. – 25 pts

Write a low-level algorithm in the form of a pseudocode that one can use to implement. Now change the pseudocode to implement modular fast exponentiation. The least common multiple (LCM) of integers A and B is the smallest integer that A and B both divide into evenly. Specify and show the computation steps for the Big O of both the algorithms. Please comment your pseudocode well. – 25 pts

Write an efficient pseudocode to compute GCD of two numbers. How can you use the GCD to computer LCM? Write the pseudocode to do that. Write an algorithm in the form of a pseudocode to find the largest item in an unsorted singly linked list with cells containing integers. Please comment your pseudocode well. Specify and show the computation steps for the Big O of both the algorithms. – 20 pts

Write an algorithm in the form of a pseudocode to find the second smallest item in an unsorted singly linked list with cells containing integers. Please comment your pseudocode well. Specify and show the computation steps for the Big O of both the algorithms. – 20 pts

Is there any difference between the Big O running time of algorithms in question 4 and question 5? Which of the algorithms would run faster in real-time? Explain. – 5 pts

Explanation / Answer

Hi there,

Lets pick integers a , n and m where in n>=0 & 0<=a<n, compute an(mod m).=a ;

so a simple algorithm considering

y=a;

for (i=2,3...,n)

y=ya(mod m);

return y;

In this simple algorithm we use n-1 modular multiplications.

It is completely impractical if n has several hundred digits .For n integers of the size much of public key cryptography depends our ability to compute an(mod m) .

If n is a power of 2, say n= 2k, we have a faster way : square a, k times.

input: integers a, n and m , with n>=0 & 0<=a<m.

output : an(mod m)

algorithm : Let n = (betakbetak-1......beta0)2 , Where betak=! 0 unless k=0.

then k = [log(n)] and n = sigmaki=0 betai2i.

if betai=(n>>i)& 1 in C notation.

for notaional purposes, let us take ni;

interger fastexp(int a, int n , int m)

x=a;

y=(beta0==1)? a:1 ;

for (i=1,2,...k)

x=x2(mod m);

if (betai==1)

y=(y==1)?x:yx(mod m);

return y;

this is one of the simplest fast exponentiation algorithm.

.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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