search

jake-doliskani / divpoly_pit

MIT License
0 stars 1 forks source link

Do you measure in 𝔽_p-ops or 𝔽_q-ops? #5

Closed defeo closed 6 years ago

defeo commented 6 years ago

Here you say that the unit cost is an operation in 𝔽_q:

https://github.com/javad-doliskani/divpoly_pit/blob/98734cc4aff5acd423f0d10277c6f9d0162e0eb5/divpoly_pit.tex#L151-L152

But then, here:

https://github.com/javad-doliskani/divpoly_pit/blob/98734cc4aff5acd423f0d10277c6f9d0162e0eb5/divpoly_pit.tex#L324

and in various other places you use 𝔽_p. Maybe do a uniformization pass?

jake-doliskani commented 6 years ago

Added: Since $\F_q / \F_p$ is only a quadratic extension, multiplication in $\F_q$ is performed using a few multiplications in $\F_p$. Therefore, polynomial multiplication over $\F_q$ has the same asymptotic cost as that over $\F_p$, and we shall always count the number of operations in $\F_p$.

defeo commented 6 years ago

Ok. I totally agree with the sentence. Please check that there's no "F_q-ops" left in the text.