Hi, I need help with this lab In this lab, calculate the residue of an integer o

Question

Hi,

I need help with this lab

In this lab, calculate the residue of an integer of the form a^n. Your program should prompt the user for a, and n and the modulus. Your program will then print out the residue. The program should loop through 4 times so that I can test it with 4 different values of a, n and the modulus. You must use the technique for this program. The technique is:

144^4 mod 713 = (144^2)^2 mod 713

= (144^2 mod 713^2)^2 mod 713

=(20736 mod 713)^2 mod 713

=59^2 mod 713

=3481 mod 713

=629

Use the long long type for intermediate results since raising even small numbers to powers can result in very large numbers.

You will need to have a decimal to binary conversion to implement the algorithm

I recommend that you first write a function to calculate residues for power of 2. You can then use this function to determine the residues for numbers that are not powers of 2.  

Explanation / Answer

#include <stdio.h>
#include <math.h>

int mod(int a,int n,int m)
{
   if(n==0) // base case- 0
       return 1;
   else if(n==1) // base case -1
       return a%m;
   else if(n==2) // logic as given in the question!!
   {
       long long temp = a*a;
       return temp%m;
   }
   int p = log(n)/log(2);
   return ((mod(a,p,m)* mod(a,n-p,m))%m); // Recursively calling it for the remaining
}

int main(void) {
   int i,t=4,a,n,m,p=0;
  
   while(t--) // test cases
   {
       scanf("%d%d%d", &a,&n,&m); // Scanning the input
       printf("%d ",(mod(a,n,m))); // Calling the function
   }
   return 0;
}

-----------------------------------------------------------------------------------------------------------------------------------

Note : I have commented the code. If you have any doubts, please feel free to ask

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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