Score:0

Matrix formulation of Number-theoretic transforms (NTT)

cn flag

I have two polynomials over a finite field. I am trying to compute the product of these polynomials using Number-theoretic transforms. For my use case, it makes sense to do this in the matrix form.

What is the matrix formulation of the NTT and inverse-NTT? Does it differ from the DFT and inverse-DFT matrices?

kelalaka avatar
in flag
And where does this related to Cryptography? NTT is for the finite fields, https://math.stackexchange.com/q/1182734/338051
Daniel S avatar
ru flag
See [further down the page that you link to](https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)#Number-theoretic_transform). The number theoretic transform is the discrete Fourier transform when the roots of unity are interpreted modulo $p$ for some prime $p$.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.