1) Next try writing a simple function euler_phi to compute Euler's function. This should take an integ n, and for each i from 1 to n - 1, adds one to a counter each time we have gcd(i, n) = 1 (i.e., for eac i which is relatively prime to n). Is this code quicker than semiprime_factorisation1? That is, if w wanted to compute (n) for n semiprime, is it quicker to use euler_phi directly, or to use semiprime_factorisation and then calculate (n) = (p − 1)(q − 1)? 2) It's not too hard to see that a faster semiprime factorisation function is trial division, also called direct search factorisation. This simply involves dividing n by each integer from 2 to √n], to find integers which divide n exactly (that is, have a remainder of zero). Write a function semiprime_factorisation2 which takes an integer n, which is a semiprime (i.e., is the product of two primes p and q), and returns both p and q. Remember to use integer division here, with //. Test yo function on some values of n = pq. To compute (n), for n = pq, with p, q prime, is it quickest to use euler_phi or semiprime_factorisation1, or semiprime_factorisation?? 3) Write a prime factorisation function prime_factorisation which can take any integer n and return prime factorisation. Similar to semiprime_factorisation2, this function should begin testing whether n is divisible by each integer increasing from 2. If j divides n, replace n by n/j and continue. should return a list of prime factors, with repeated factors listed multiple times, e.g., the input 24 shoul return the list [2,2,2,3], since 24 = 2³ x 3.
1) Next try writing a simple function euler_phi to compute Euler's function. This should take an integ n, and for each i from 1 to n - 1, adds one to a counter each time we have gcd(i, n) = 1 (i.e., for eac i which is relatively prime to n). Is this code quicker than semiprime_factorisation1? That is, if w wanted to compute (n) for n semiprime, is it quicker to use euler_phi directly, or to use semiprime_factorisation and then calculate (n) = (p − 1)(q − 1)? 2) It's not too hard to see that a faster semiprime factorisation function is trial division, also called direct search factorisation. This simply involves dividing n by each integer from 2 to √n], to find integers which divide n exactly (that is, have a remainder of zero). Write a function semiprime_factorisation2 which takes an integer n, which is a semiprime (i.e., is the product of two primes p and q), and returns both p and q. Remember to use integer division here, with //. Test yo function on some values of n = pq. To compute (n), for n = pq, with p, q prime, is it quickest to use euler_phi or semiprime_factorisation1, or semiprime_factorisation?? 3) Write a prime factorisation function prime_factorisation which can take any integer n and return prime factorisation. Similar to semiprime_factorisation2, this function should begin testing whether n is divisible by each integer increasing from 2. If j divides n, replace n by n/j and continue. should return a list of prime factors, with repeated factors listed multiple times, e.g., the input 24 shoul return the list [2,2,2,3], since 24 = 2³ x 3.
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
![(1) Next try writing a simple function euler_phi to compute Euler's function. This should take an integer
n, and for each i from 1 to n − 1, adds one to a counter each time we have gcd(i, n) = 1 (i.e., for each
i which is relatively prime to n). Is this code quicker than semiprime_factorisation1? That is, if we
wanted to compute (n) for n semiprime, is it quicker to use euler_phi directly, or to use
semiprime_factorisation and then calculate (n) = (p − 1)(q − 1)?
(2) It's not too hard to see that a faster semiprime factorisation function is trial division, also called direct
search factorisation. This simply involves dividing n by each integer from 2 to [√n], to find integers
which divide n exactly (that is, have a remainder of zero). Write a function
semiprime_factorisation2 which takes an integer n, which is a semiprime (i.e., is the product of
two primes p and q), and returns both p and q. Remember to use integer division here, with //. Test your
function on some values of n = pq. To compute (n), for n = pq, with p, q prime, is it quickest to use
euler_phi or semiprime_factorisation1, or semiprime_factorisation2?
(3) Write a prime factorisation function prime_factorisation which can take any integer n and return its
prime factorisation. Similar to semiprime_factorisation2, this function should begin testing
whether n is divisible by each integer increasing from 2. If j divides n, replace n by n/j and continue. It
should return a list of prime factors, with repeated factors listed multiple times, e.g., the input 24 should
return the list [2,2,2,3], since 24 = 2³ × 3.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F3011c556-643e-4a01-b0e0-55d8cf24eddf%2Fc31a5983-ff62-4b8b-909f-47391bfe96ab%2F6pinxw_processed.jpeg&w=3840&q=75)
Transcribed Image Text:(1) Next try writing a simple function euler_phi to compute Euler's function. This should take an integer
n, and for each i from 1 to n − 1, adds one to a counter each time we have gcd(i, n) = 1 (i.e., for each
i which is relatively prime to n). Is this code quicker than semiprime_factorisation1? That is, if we
wanted to compute (n) for n semiprime, is it quicker to use euler_phi directly, or to use
semiprime_factorisation and then calculate (n) = (p − 1)(q − 1)?
(2) It's not too hard to see that a faster semiprime factorisation function is trial division, also called direct
search factorisation. This simply involves dividing n by each integer from 2 to [√n], to find integers
which divide n exactly (that is, have a remainder of zero). Write a function
semiprime_factorisation2 which takes an integer n, which is a semiprime (i.e., is the product of
two primes p and q), and returns both p and q. Remember to use integer division here, with //. Test your
function on some values of n = pq. To compute (n), for n = pq, with p, q prime, is it quickest to use
euler_phi or semiprime_factorisation1, or semiprime_factorisation2?
(3) Write a prime factorisation function prime_factorisation which can take any integer n and return its
prime factorisation. Similar to semiprime_factorisation2, this function should begin testing
whether n is divisible by each integer increasing from 2. If j divides n, replace n by n/j and continue. It
should return a list of prime factors, with repeated factors listed multiple times, e.g., the input 24 should
return the list [2,2,2,3], since 24 = 2³ × 3.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 6 steps with 6 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY