Question

In: Computer Science

Q4. Find the multiplicative inverse of 14 in GF(31) domain using Fermat’s little theorem. Show your...

Q4. Find the multiplicative inverse of 14 in GF(31) domain using Fermat’s little theorem. Show your work

Q5. Using Euler’s theorem to find the following exponential: 4200mod 27. Show how you have employed Euler’s theorem here

Solutions

Expert Solution

Fermat’s theorem :

Theorem

Let p be a prime. Then for all integers a not divisible by p, we have

ap-1 ≡ 1 mod p

Proof:

The group has p − 1 elements. Then by the Lagrange

theorem, for all a ∈ , ap-1 ≡ 1 mod p

p−1 ≡ 1 mod p.

// Java program to find modular inverse of a under modulo m  
// using Fermat's little theorem.  
// This program works only if m is prime. 
  
class GFG 
{ 
    static int __gcd(int a, int b) 
    { 
      
        if(b == 0)  
        { 
            return a; 
        } 
        else 
        { 
            return __gcd(b, a % b); 
        } 
    } 
      
    // To compute x^y under modulo m 
    static int power(int x,int y,int m) 
    { 
        if (y == 0) 
            return 1; 
        int p = power(x, y / 2, m) % m; 
        p = (p * p) % m; 
      
        return (y % 2 == 0) ? p : (x * p) % m; 
    } 
      
    // Function to find modular  
    // inverse of a under modulo m 
    // Assumption: m is prime 
    static void modInverse(int a, int m) 
    { 
        if (__gcd(a, m) != 1) 
            System.out.print("Inverse doesn't exist"); 
      
        else { 
      
            // If a and m are relatively prime, then 
            // modulo inverse is a^(m-2) mode m 
            System.out.print("Modular multiplicative inverse is "
                                            +power(a, m - 2, m)); 
        } 
    } 
      
      
    // Driver code 
    public static void main (String[] args)  
    { 
        int a = 31, m = 14; 
        modInverse(a, m); 
    } 
} 

Euler’s theorem:

Let n be any positive integer. Then, for all integers a relatively prime to n, we have

≡ 1 mod n.

So, By the formula we get 4200 modulo 27 = 15.


Related Solutions

1. Find the multiplicative inverse of 14 in GF(31) domain using Fermat’s little theorem. Show your...
1. Find the multiplicative inverse of 14 in GF(31) domain using Fermat’s little theorem. Show your work. 2 Using Euler’s theorem to find the following exponential: 4200 mod 27. Show how you have employed Euler’s theorem here.
1. Find all solutions to the following linear congruences using Fermat’s Little Theorem or Euler’s Theorem...
1. Find all solutions to the following linear congruences using Fermat’s Little Theorem or Euler’s Theorem to help you. Show all your steps. (a) 3462x ≡ 6 173 (mod 59) (b) 27145x ≡ 1 (mod 42)
Problem Solving Set #1 (10 pts each) a. Find the multiplicative inverse of 1234 in GF(4321)...
Problem Solving Set #1 (10 pts each) a. Find the multiplicative inverse of 1234 in GF(4321) using the extended Euclidean algorithm b. Does the multiplicative inverse of 24140 in GF(40902) exist? Prove your answer. c. Is x4 + 1 irreducible over GF(2)? Prove your answer. d. Find (x3 + x + 1)-1 in GF(24 ) mod x4 + x + 1 using the extended Euclidean algorithm e. Find (x3 + x + 1)-1 in GF(28 ) mod x8 + x4...
Use this theorem to find the inverse of the given matrix or show that no inverse...
Use this theorem to find the inverse of the given matrix or show that no inverse exists. (If an answer does not exist, enter DNE in any cell.) 1    2    5    1 −1    0    2    1 2    1    −5    0 1    1    2    1
Write a program( preferably in C++)  using the extended Euclidean algorithm to find the multiplicative inverse of...
Write a program( preferably in C++)  using the extended Euclidean algorithm to find the multiplicative inverse of a mod n. Your program should allow user to enter a and n. Note: For this question please make sure the code compiles and runs, it is not copied and pasted from elsewhere( I will be checking!). Thanks
Using Fermat't Little Theorem for primality test. Answer the following. Show work for credit. (a) Test...
Using Fermat't Little Theorem for primality test. Answer the following. Show work for credit. (a) Test whether each of the following numbers is primes: 101, 341, and 1105. Try at least two bases if needed, and state if the number is pseudoprime to any base you try. You may use a claculator to compute large powers. (MS Excel can be used) (b) Find a composit number that is pseudoprime to base 3 and 7 but not pseudoprime to base 2...
3A. Find the domain and range of the function. (Enter your answer using interval notation.) h(x)...
3A. Find the domain and range of the function. (Enter your answer using interval notation.) h(x) = 8 x + 7 Domain Range 3B. Determine whether y is a function of x. xy + x3 − 2y = 0 Yes, y is a function of x. No, y is not a function of x.    It cannot be determined whether y is a function of x. 3C.   Consider the following function. Find the composite functions f ∘ g and g ∘...
Find ten accounting softwares and show their advantages and disadvantages. (Clearly show your resources using APA...
Find ten accounting softwares and show their advantages and disadvantages. (Clearly show your resources using APA Style)
a) Using Binary Signed Magnitude arithmetic, find the ‘sum’ of 5810 + (-2310). Show your work....
a) Using Binary Signed Magnitude arithmetic, find the ‘sum’ of 5810 + (-2310). Show your work. (use 8 bits) b) Using two’s complement binary arithmetic, find the sum of 45 and -16. Show your work. (use 8 bits)
Can you please show your work. Thank you Using the following information find the ratios listed:...
Can you please show your work. Thank you Using the following information find the ratios listed: Hamilton Company Comparative Balance Sheets December 31, 2018 and December 31, 2019 Assets         2018      2019   Difference Cash              15,000              47,000         32,000 Accounts Receivable              55,000              47,000         (8,000) Inventory           110,000           144,000         34,000 Prepaid Expenses                5,000                1,000         (4,000) Long term investments           127,000           115,000       (12,000) Land             55,000             55,000                   -   Building          ...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT