I need to find the first $n$ coefficients of $$\prod_{i = 1}^{i = q}(1 + x^{a_i})^{b_i}$$ modulo a NTT favourable prime. Can someone suggest an algorithm with worst-case complexity $O(n\log n)$ or $O(q\log q)$? I think this is to be done using NTT but cannot get an exact method. I tried Divide and Conquer but it is $O(qn\log n)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.