heir icon indicating copy to clipboard operation
heir copied to clipboard

poly: add pass to convert poly.mul to use ntt ops

Open inbelic opened this issue 1 year ago • 2 comments

  • We can reduce complexity of polynomial multiplication by using the number-theoretic transform

  • Here we add a pass that will convert all poly.mul operations into a poly.ntt of both operands -> modulus multiplication of the coefficients -> poly.intt back into the polynomial type

Resolves #541

inbelic avatar Apr 29 '24 17:04 inbelic

Also please squash the commits when you're ready. Thanks!

j2kun avatar May 01 '24 17:05 j2kun

Great thanks. I will be AFK until the 15th, but can fix it up when I have my laptop again. Otherwise, feel free to apply your suggestions and merge. Sorry for the delay

inbelic avatar May 02 '24 05:05 inbelic