Polynomial multiplication over finite fields in time O(n log n)
2019
Assuming a widely-believed hypothesis concerning the least prime in an arithmetic progression, we show that two n-bit integers can be multiplied in time O(n log n) on a Turing machine with a finite number of tapes; we also show that polynomials of degree less than n over a finite field F_q with q elements can be multiplied in time O(n log q log(n log q)), uniformly in q.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
12
Citations
NaN
KQI