arithmetic operations
Summary
Runtime of arithmetic operations
- relevant when dealing with large numbers
- polynomial time algorithms are efficient
| Operation | Runtime for co485 | Best runtime |
|---|---|---|
| Addition, | = | |
| Subtraction, | = | |
| Comparison, | = | |
| Multiplication, | ||
| Integer division, | ||
| Modular addition/subtraction, | = | |
| Modular multiplication, | ||
| Modular inversion(EEA), | = | |
| Modular division, | = | |
| Modular exponentiation, |
we use
since when thinking about operations, we care about the size of the number in bits
Concept
Multiplication
- use simple
- ignore more efficient algorithms, such as:
, karatsuba algorithm , galactic algorithm
Modular inversion
- why can the EEA do modular inversion?
Application
Swapping runtime between input value and bit length
which explains why trial division is actually exponential in bit length