Chapter 1: Algorithms with numbers
Dramatic Contrast between 2 Ancient Problems
Factoring:
- Given a number N , express it as a product of its prime factors.
- Take time exponential in the number of bits of N .
Primality:
- Given a number N , determine whether it is a prime.
- Easy to solve.
Addition
Property: The sum of any three single-digit numbers is at most two digits long.
- this rule holds not just in decimal but in any base $$b ≥ 2$$
Given two binary numbers x and y, the running time as $$O(n)$$ suppose x and y are each $$n$$ bits long.