Saving a significant multiplication in odd order Toom-Cook negacyclic convolution

[Brian Quach]

I have not implemented it yet - it is still mostly an idea. For this
reason, I do not know how well it will perform in practice. In addition, I
am unfamiliar with low level programming and with the existing code, so I
will probably be unable to make meaningful direct contributions.

Currently I am just trying to produce some 'evaluation' and 'interpolation'
matrices (not similar to Toom-Cook matrices).
Here is an example for N = 3:
cyclotomic factorisation: x^3 + 1 = (x + 1)(x^2 - x + 1) (number of factors
k = 2)
multiplications needed: 2N - k = 6 - 2 = 4 (better than the straightforward
find all coefficients and then wrap around)
multiply modulo the factors using scalar multiplication and Karatsuba
multiplication, respectively
'evaluation' matrix for each operand (array of rows): [[1, -1, 1], [1, 0,
-1], [1, 1, 0], [0, 1, 1]] (can involve 5 additions / subtractions)
This is probably better than Bodrato's optimal sequence for Toom-3, as it
has the same addition / subtraction count and saves 2 shifts.
'interpolation' matrix: [[1, 1, 1, -2], [-1, -1, 2, -1], [1, -2, 1, 1]] / 3
(6 additions / subtractions and 1 division by 3)

I have also derived these things for other numbers of pieces.
N, Toom-Cook pointwise multiplications, new scheme pointwise
multiplications, cyclotomic factorisation
4, 7, 7, x^4 + 1
5, 9, 8, (x + 1)(x^4 - x^3 + x^2 - x + 1)
6, 11, 10, (x^2 + 1)(x^4 - x^2 + 1)
7, 13, 12, (x + 1)(x^6 - x^5 + x^4 - x^3 + x^2 - x + 1)
8, 15, 15, x^8 + 1
9, 17, 15, (x + 1)(x^2 - x + 1)(x^6 - x^3 + 1)

Anyway, mistakes in my earlier emails
first email, second paragraph, second sentence is meant to mention odd N
second email, second sentence is supposed to say that 2 is not the only
prime divisor (or alternatively, N has at least one odd prime divisor)

On Fri, Jul 5, 2019 at 9:48 PM Torbjörn Granlund <tg at gmplib.org> wrote:

> You seem to have replied to me privately, not to the list.
>
> --
> Torbjörn
> Please encrypt, key id 0xC8601622
>