Problem 5 (Pseudoprimes and Carmichael Numbers!). We have seen that an integer n is prime when...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Problem 5 (Pseudoprimes and Carmichael Numbers!). We have seen that an integer n is prime when it is not divisible by any prime p with p n. Unfortunately, using this criterion to show that a given integer is prime is inefficient. We can use the converse of Fermat's Little Theorem (with p = 2) to obtain an alternative primality test. Fermat Primality Test (p = 2): Let n> 1 be an odd integer. If 2-1 # 1 (modn), then n is composite. Notice - this gives us a way to determine if a number is composite without knowing a single factor of n - Neat! a. Using the Fermat Primality Test along with the Modular Exponentiation Algorithm, either your own (Activ- ity/Project 4) or the built in Sage Algorithm, show the following numbers are composite. i. Jenny x (Jenny + 2) = 75261003596099 ii. Jenny x Devil's Prime 8675309000000577775579400000008675309 iii. RSA 100 = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 iv. RSA 230 = 1796949159794106673291612844957324615636756180801260007088891883553172646034149093349337224786865075523085586419992 9221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689 RSA 230 has 230 decimal digits (762 bits) and was (recently) factored on August 15, 2018. See RSA Numbers/RSA Factoring Challenge. b. Unfortunately, there are composite integers n such that 2"-1 = 1 (mod n). Such integers are called 2- pseudoprimes. i. Show that n = 341 is a 2-pseudoprime. That is, show that 341 is composite (not prime) and 2841-1 = 1 (mod 341). ii. There are seven 2-pseudoprimes less than 2000. Find them. (341 is the smallest pseudoprime.) Hint: Start with non-prime numbers and test if 2-1 = 1(mod n) iii. Determine the number of 2-pseudoprimes that do not exceed 10000. c. A natural question now arises, if n is composite, is there some b such that b1 #1(mod n)? The easy answer is 'yes' since we can take b to be a prime divisor of n and then bis 0 modulo n (i.e., it is not 1). However, if we know ged(n, b) # 1, then we know a factor of n! We are primarily worried about whether we can pick a few values of b with the hope of finding one that will fail the Fermat Test. Definition 2. A composite n> 1 is called a Carmichael number if b-1 = 1 (mod n) for all integers b with god(b, n) = 1. i. Show that 561 = 3-11-17 is a Carmichael number. We see that 561 is composite so it remains to show that 6561-1 = 1(mod 561) for all integers b with gcd (561, b) = 1. ii. Show that 1729 7 13 19 is a Carmichael number iii. Write and implement a program with input n that returns True if n is a Carmichael number and False if n is prime or not a Carmichael number. iv. List and count the number of Carmichael numbers up to 10000. Count the number of Carmichael numbers up to 1000000. Count the number of Carmichael numbers up to 10. Problem 5 (Pseudoprimes and Carmichael Numbers!). We have seen that an integer n is prime when it is not divisible by any prime p with p n. Unfortunately, using this criterion to show that a given integer is prime is inefficient. We can use the converse of Fermat's Little Theorem (with p = 2) to obtain an alternative primality test. Fermat Primality Test (p = 2): Let n> 1 be an odd integer. If 2-1 # 1 (modn), then n is composite. Notice - this gives us a way to determine if a number is composite without knowing a single factor of n - Neat! a. Using the Fermat Primality Test along with the Modular Exponentiation Algorithm, either your own (Activ- ity/Project 4) or the built in Sage Algorithm, show the following numbers are composite. i. Jenny x (Jenny + 2) = 75261003596099 ii. Jenny x Devil's Prime 8675309000000577775579400000008675309 iii. RSA 100 = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 iv. RSA 230 = 1796949159794106673291612844957324615636756180801260007088891883553172646034149093349337224786865075523085586419992 9221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689 RSA 230 has 230 decimal digits (762 bits) and was (recently) factored on August 15, 2018. See RSA Numbers/RSA Factoring Challenge. b. Unfortunately, there are composite integers n such that 2"-1 = 1 (mod n). Such integers are called 2- pseudoprimes. i. Show that n = 341 is a 2-pseudoprime. That is, show that 341 is composite (not prime) and 2841-1 = 1 (mod 341). ii. There are seven 2-pseudoprimes less than 2000. Find them. (341 is the smallest pseudoprime.) Hint: Start with non-prime numbers and test if 2-1 = 1(mod n) iii. Determine the number of 2-pseudoprimes that do not exceed 10000. c. A natural question now arises, if n is composite, is there some b such that b1 #1(mod n)? The easy answer is 'yes' since we can take b to be a prime divisor of n and then bis 0 modulo n (i.e., it is not 1). However, if we know ged(n, b) # 1, then we know a factor of n! We are primarily worried about whether we can pick a few values of b with the hope of finding one that will fail the Fermat Test. Definition 2. A composite n> 1 is called a Carmichael number if b-1 = 1 (mod n) for all integers b with god(b, n) = 1. i. Show that 561 = 3-11-17 is a Carmichael number. We see that 561 is composite so it remains to show that 6561-1 = 1(mod 561) for all integers b with gcd (561, b) = 1. ii. Show that 1729 7 13 19 is a Carmichael number iii. Write and implement a program with input n that returns True if n is a Carmichael number and False if n is prime or not a Carmichael number. iv. List and count the number of Carmichael numbers up to 10000. Count the number of Carmichael numbers up to 1000000. Count the number of Carmichael numbers up to 10.
Expert Answer:
Answer rating: 100% (QA)
To determine whether the given numbers are composite using the Fermat Primality Test we need to check if 21 mod n holds true for each number If it does then the number is composite a Lets check the gi... View the full answer
Related Book For
Statistics Unlocking The Power Of Data
ISBN: 9780470601877
1st Edition
Authors: Robin H. Lock, Patti Frazer Lock, Kari Lock Morgan, Eric F. Lock, Dennis F. Lock
Posted Date:
Students also viewed these finance questions
-
How much depreciation on its property and equipment did Aritzia record in 2018 and 2017? 6. Property and equipment Cost Balance, February 28, 2016 Additions Transfers from construction-in-progress...
-
We have seen that the adjacency matrix can be used to represent a graph. However, this method proves to be rather inefficient when there are many 0's (that is, few edges) present. A better method...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
In Exercises 1 through 22, find the critical points of the given functions and classify each as a relative maximum, a relative minimum, or a saddle point. f(x, y) = x 4 32x + y 3 12y + 7
-
Determine the heat transfer coefficient for liquid bismuth flowing through an annulus (5 cm ID, 6.1 cm OD) at a velocity of 4.5 m/s. The wall temperature of the inner surface is 427C and the bismuth...
-
Even though silver is a better electrical conductor than copper, most electrical cables are made from copper. The main reason is cost: The per-kilogram price of silver is about 100 times the...
-
The A-36 steel column is encased in high-strength concrete as shown. If an axial force of 60 kip is applied to the column, determine the required area of the steel so that the force is shared equally...
-
Refer to Figure which shows the computer solution THE MANAGEMENT SCIENTIST SOLUTION FOR THE INVESTMENT ADVISORS PROBLEM a. How much would the return for U.S. Oil have to increase before it would be...
-
What are the common issues encountered when scaling chemical processes from laboratory-scale to pilot-scale and ultimately to full-scale production, and how can they be mitigated ?
-
Create a set of use cases for the following high-level requirements in a housing system run by the Campus Housing Service. The Campus Housing Service helps students find apartments. Owners of...
-
Select an annual report of S&G where the company disclosed contingent assets and contingent liabilities. Consider the following three alternatives and the three possible ways to account for them....
-
The frequency of the zero lower bound around the world Use the FRED database at the Federal Reserve Bank of St. Louis to find the monthly average nominal policy interest rates for four major central...
-
Reread the Management Focus The European Commission and Media Industry Mergers, then answer the following questions: a. Given that both AOL and Time Warner were U.S.-based companies, do you think the...
-
Caterpillar Tractor has long been one of Americas major exporters. The company sells its construction equipment, mining equipment, and engines to some 200 countries worldwide. As a leading exporter,...
-
In late 2004 IBM announced it was getting out of the personal computer business and would sell its entire PC operations to Lenovo, the fast-growing Chinese manufacturer of personal computers, for...
-
Al Merritt founded MD International in 1987. A former salesman for a medical equipment company, Merritt saw an opportunity to act as an export intermediary for medical equipment manufacturers in the...
-
Given below are balance sheets as of December 31, 2020, and December 31, 2019, for James Hospital. Using the balance sheets and the additional information provided, complete the income statement of...
-
The following information is available for Partin Company: Sales $598,000 Sales Returns and Allowances 20,000 Cost of Goods Sold 398,000 Selling Expense 69,000 Administrative Expense 25,000 Interest...
-
Answer the same questions using Figure 6.10 as in Exercise 6.100 except assume that each histogram represents only 15 homes. Is the t-distribution appropriate to model sample means of housing price...
-
Near Death Experiences Exercise 2.21 on page 56 describes a study of the prevalence of near-death experiences. A near-death experience includes the sensation of seeing a bright light or feeling...
-
In 2007 a Harvard psychologist set out to test her theory that Mind-Set Matters. She recruited 75 female maids working in different hotels to participate in her study, and informed 41 maids (randomly...
-
Let \(X_{1}, X_{2}, \ldots, X_{5}\) be 5 independent random variables. Find the moment generating function \[M_{\sum X_{i}}(t)=E\left(e^{t\left(X_{1}+X_{2}+\cdots+X_{5} ight)} ight)\] of the sum when...
-
Let \(X_{1}, X_{2}\), and \(X_{3}\) be independent normal variables with \[\begin{array}{lll}E\left(X_{1} ight)=5 & \text { and } & \sigma_{1}^{2}=9 \\E\left(X_{2} ight)=-2 & \text { and } &...
-
Refer to Exercise 6.36. (a) Show that \(2 X_{1}-X_{2}-4 X_{3}-12\) has a normal distribution. (b) Find the mean and variance of the random variable in part (a). Data From Exercise 6.36 6.36 Let X1,...
Study smarter with the SolutionInn App