There’s been some nice recent work on time and space efficient integer and polynomial multiplication. Of particular note in this case, you can do karatsuba with

There’s been some nice recent work on time and space efficient integer and polynomial multiplication. Of particular note in this case, you can do karatsuba with only O(log(n)) workspace, at the cost of some additional bookkeeping. See, e.g., https://www.usna.edu/Users/cs/roche/research/papers/lsmul.pdf https://www.usna.edu/Users/cs/roche/research/papers/lsmul.pd...