1. Write a function named factors that returns all prime factors of an integer. For example,...

Transcribed Image Text:

1. Write a function named factors that returns all prime factors of an integer. For example, factors(12) returns [2,2,3]. If the input is a prime or 1 it returns an empty list. The factors should be listed in increasing order. Please do not search or copy from the internet. You can orally discuss solutions with other students, but any collaboration that involves writing things down will be considered as cheating and earn a zero credit. If you are stuck, please talk to the instructor. Python does not limit the size of the integers so you can run it on arbitrarily large integers (bignums). 2. In the report, include the code and a derivation of the running time of your algorithm (a) assuming that multiplications and division (and additions) take constant time and (b) assuming that multiplication and division of n-bit numbers take O(n²) time and additions and subtractions take O(n) time. 3. The size of the input n is usually measured by the number of bits needed to represent the input. But here we can use decimal digits since it is directly proportional to the bits. Give a table T(n) vs. n from your experimental results. Does your table closely match one of the running time functions derived in 2? How large can n be so that T(n) is approximately 5 minutes. What if T(n) is 5 hours? 5 days? Factoring is a fundamental crypto-primitive that underlies modern cryptography. What size of n makes it practically impossible for your algorithm to factorize, e.g., T(n) > 10 years. 4. State a useful invariant of the loop towards proving the correctness of the algorithm. 5. Prove that the algorithm is correct using your previously defined invariant. 1. Write a function named factors that returns all prime factors of an integer. For example, factors(12) returns [2,2,3]. If the input is a prime or 1 it returns an empty list. The factors should be listed in increasing order. Please do not search or copy from the internet. You can orally discuss solutions with other students, but any collaboration that involves writing things down will be considered as cheating and earn a zero credit. If you are stuck, please talk to the instructor. Python does not limit the size of the integers so you can run it on arbitrarily large integers (bignums). 2. In the report, include the code and a derivation of the running time of your algorithm (a) assuming that multiplications and division (and additions) take constant time and (b) assuming that multiplication and division of n-bit numbers take O(n²) time and additions and subtractions take O(n) time. 3. The size of the input n is usually measured by the number of bits needed to represent the input. But here we can use decimal digits since it is directly proportional to the bits. Give a table T(n) vs. n from your experimental results. Does your table closely match one of the running time functions derived in 2? How large can n be so that T(n) is approximately 5 minutes. What if T(n) is 5 hours? 5 days? Factoring is a fundamental crypto-primitive that underlies modern cryptography. What size of n makes it practically impossible for your algorithm to factorize, e.g., T(n) > 10 years. 4. State a useful invariant of the loop towards proving the correctness of the algorithm. 5. Prove that the algorithm is correct using your previously defined invariant.

Answer rating: 100% (QA)

Answer Python Code for Prime Factorization def factorsn primefactors divisor 2 while n 1 while n div... View the full answer