arithmetic operations

Work in Progress

Summary

Runtime of arithmetic operations

  • relevant when dealing with large numbers
  • polynomial time algorithms are efficient
OperationRuntime for co485Best runtime
Addition, =
Subtraction, =
Comparison, =
Multiplication,
Integer division,
Modular addition/subtraction, =
Modular multiplication, ^fa4ba8
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:

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