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
-
Show how to modify the topological sort algorithm so that if the graph is not acyclic, the algorithm will print out some cycle. You may not use depth-first search.
-
What is the value of each variable after the if statement? a. int n = 1; int k = 2; int r = n; if (k < n) { r = k; } b. int n = 1; int k = 2; int r; if (n < k) { r = k; } else { r = k + n; } c. int n...
-
A machine is bought for 18,000, plus 3,000 installation costs. It is to be depreciated on a diminishing balance basis using a rate of 60% p.a. What is the depreciation to be charged in the second...
-
Consider a bull spread where you buy a 40-strike call and sell a 45-strike call. Suppose S = $40, = 0.30, r = 0.08, = 0, and T = 0.5. Draw a graph with stock prices ranging from $20 to $60...
-
On December 27, goods were shipped to a customer that cost $30,000 and were invoiced $50,000 to a customer, FOB destination. The goods arrived on January 10. The business was a Consignor of Goods...
-
onsider the model of the electrically heated stirred-tank system in Section 2.4.3. Subscript e refers to the heating element: (a) Derive transfer functions relating changes in outlet temperature T to...
-
Let p(x) 8r" + 4a of p(z). 106z - 17z + 260z + 175, It is known that r is a factor a. Use the theorem on bounds to and an upper and a lower bound for the real zeros of p(z). b. How many positive and...
-
Bayer estimates the current global market for seeds at 40 billion and the market for crop protection at 50 billion. Bayer's digital platform will provide guidance from "precision" agriculture and...
-
e 1. What are the basal characteristics of animals? 2. Sponges do not have tissues or organs. But they do have specialized cells. Using your lab book and the film, briefly describe the function of...
-
Complete the following question: A: What biome do we live in here in southern California?What characterizes our biome? B: In which biomes is fire a major factor? What is therole of fire in these...
-
In cats, coat color is codominant. If a black cat mates with a spotted black and white cat, what is the probability of having a cat with a black coat?
-
In recent years, shareholders have submitted proposals for inclusion in company proxy materials that address environmental, social and political issues. For example, the Alphabet and Microsoft proxy...
-
3. Cost Analysis:3 a. Identify each cost associated with the library's book donations department. b. Classify each cost associated with the library's book donations department as fixed or variable...
-
Find the equation of the plane passing through the points P 5,4,3 ,Q 4,3,1 and R 1,5,4
-
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...
-
The balance sheets of Parkway plc for 20X7 and 20X8 are given below, together with the profit and loss account for the year ended 30 June 20X8. 1 The freehold land and buildings were purchased on 1...
-
Aspirations Ltd commenced trading as wholesale suppliers of office equipment on 1 January 20X1, issuing ordinary shares of 1 each at par in exchange for cash.The shares were fully paid on issue, the...
-
The historical cost accounts of Smith plc are as follows: 1 Land and buildings were acquired in 20X0 with the buildings component costing 800,000 and depreciated over 40 years. 2 Share capital was...
Study smarter with the SolutionInn App