Question

In: Computer Science

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

note (MS Excel can be used)

Solutions

Expert Solution

a)Fermat's little theorem states that, Let 'p' be a prime number and a be a non-negative integer which is relatively prime to 'p',
GCD(a,b)=1 such that,
a^p-1 ≡ 1 (mod p) OR a^p-1%p=1


If a given number is prime, then the method returns true. If the number is composite, then it may return true or false, but the probability of resulting incorrect result for a composite is low and it can be reduced by doing more iterations.

1) let's find 101 is prime or not...
Since 101 is prime, 2^100 ≡ 1 (mod 101)

=2^100 mod 101
=2^10^10 mod 101
=1024^10 mod 101
=14^10 mod 101
=(-6)^5 mod 101
=-216*36 mod 101
=-14*36 mod 101
=-504 mod 101
=505–504
=1
ie,The number 101 is pseudoprime [or 2^101 = 1].

2) let's find 341 is prime or not...
Since 341 is prime, 2^340 ≡ 1 (mod 341) [or 2^341 = 1]

here 341 is prime and 2 and p are coprime then,

The remainder is 1.
ie, The number 341 is pseudoprime


3) let's find 1105 is prime or not...
Since1105 is prime, 2^1104 ≡ 1 (mod 1105)

By Fermat’s Little Theorem,
here, a^p−1 ≡ 1(mod p) if 'a' is relatively prime to 'p'. that means b is relatively prime to 1105.
so 1105 is a prime number.[or 2^1105 = 1]


b)91 is a pseudoprime to the base 3 but not to the base 2.
n=91=7*13 is a composite number
so 312 ≡ 1(mod 7)
312 ≡ 1(mod 13)
= 3
12 ≡ 1(mod 7 * 13) i.e 312 ≡ 1(mod 91) by result 1.2.1.
Now 391 = (312)
7 * 3
7 ≡ 1
7 * 2187 ≡ 3(mod 91).
ie, 91 is a pseudoprime to the base 3.
Similarly, 212 ≡ 1(mod 91) and 291 = (212)
7 * 2
7 ≡ 1
7 * 128 ≡
37(mod 91)
ie,91 is not a pseudoprime to the base 2

and,
6 is a pseudoprime to the base 7 but not to the base 2.

Hope you got the correct answer...

Please like...Thank you!


Related Solutions

Answer & show work andswer and show work answer n show work Using a sample of...
Answer & show work andswer and show work answer n show work Using a sample of 20 people, the testing agency found that 14 of them had better protection than that provided by the competitor. Do you have enough evidence to say/claom that your suncreen lotion provides better protection than the competitiors in a majority of cases? Use alpha = 0.01 to answer. 1. What are the apporiate hypotheses for situation? 2. the appropriate rejection rule is? 3. the calculated...
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)
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.
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
answer all or do not answer SHOW ALL WORK FOR COMPUTATIONAL PROBLEMS OR NO CREDIT (write...
answer all or do not answer SHOW ALL WORK FOR COMPUTATIONAL PROBLEMS OR NO CREDIT (write out the equation and solution) 1. Determine the number of significant figures for the following: A) 4778526 B) 0.075 C) 850 D) 14268.5 E) 25.8 x 105 F) 3310 x 10-1 2) Convert the following into scientific notation: A) 0.004288 B) 4200 C) 363000000 D) 0.00000363 Please use these conversion for the following problems : 1mi = 1609 m               3.79 L = 1.00 gal          ...
Using Miller-Rabin primality test algorithm to write a Java program which can test if an integer...
Using Miller-Rabin primality test algorithm to write a Java program which can test if an integer is a prime. The input of the algorithm is a large positive integer. The output is “the number *** is a prime” or “the number *** is not a prime”. The error probability of the algorithm should be no more than 1 256 . Use this program to test some big integers. In Java, there is a class BigInteger. You can use methods of...
Using the Fermat primality test, find the number of Fermat witness and number of Fermat liars...
Using the Fermat primality test, find the number of Fermat witness and number of Fermat liars for 341 via computer programming (ex;c++).
State the Null and Alternative Find The Standard error and Test statistics (show work for credit...
State the Null and Alternative Find The Standard error and Test statistics (show work for credit ) include the decoding. Draw the standard normal Distribution and decide how likely is the test statistics. Decide to reject or accept the Null hypothesis ~ Use the Test statistics and or the p-value. Show or describe where did you get the p-value if use it. Conclusion 1) One study found that 52% of women with breast cancer experience optimism, social support, spirituality. A...
Using the following stock data for GRMN and LMT, Answer the following questions. (Show Work). Stock...
Using the following stock data for GRMN and LMT, Answer the following questions. (Show Work). Stock GRMN LMT Mean 100.05 99.79 Standard Deviation 1.10 1.47 Sample Size 62 62 a. Calculate the 95% two-sample confidence interval. What can be determined from this confidence interval. Is the difference in stock price significantly different from 0? b. Conduct a two-sample t-test using an alpha value of 0.05. c. If there was a significant difference between GRMN and LMT, What is the probability...
Show by direct computation that the impulse momentum theorem and the work-energy theorem are invariant under...
Show by direct computation that the impulse momentum theorem and the work-energy theorem are invariant under the Galilean transformation.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT