Improvements in basemul

[yoswuk]

Hello, I am Jonghyun Kim from Korea University. I am one of the authors of NTRU+, an algorithm submitted to the KPQC Competition held in South Korea.

I have been considering how to improve the NTRU+ code and found that we can reduce the number of montgomery_reduce calls by applying montgomery_reduce lazily.

I am sharing this insight here because it can also be applied to the basemul function in Kyber.

void basemul(int16_t r[2], const int16_t a[2], const int16_t b[2], int16_t zeta)
{
r[0] = fqmul(a[1], b[1]);
r[0] = fqmul(r[0], zeta);
r[0] += fqmul(a[0], b[0]);
r[1] = fqmul(a[0], b[1]);
r[1] += fqmul(a[1], b[0]);
}

void basemul(int16_t r[2], const int16_t a[2], const int16_t b[2], int16_t zeta)
{
r[0] = montgomery_reduce(a[0]*b[0]+montgomery_reduce(a[1]*b[1])*zeta);
r[1] = montgomery_reduce(a[0]*b[1]+a[1]*b[0]);
}