Mod Runtimes Flashcards
1
Q
Runtimes:
addition, mod-add
A
O(n)
2
Q
Runtimes:
multiplication, mod-mul
A
O(n^2)
3
Q
Runtimes:
division, mod
A
O(n^2)
4
Q
Runtimes:
naive mod-exp
A
O(n^2 * 2^n)
5
Q
Runtimes:
fast mod-exp
A
O(n^3)
6
Q
Runtimes:
mod-inv
A
O(n^3)
7
Q
Runtimes:
gcd/ext-gcd
A
O(n^3)
