search

pq-crystals / kyber

Other
819 stars 196 forks source link

Why the result of barrett_reduce is in {-(q-1)/2,...,(q-1)/2} congruent to a modulo q? #64

Open sduyyy opened 1 year ago

sduyyy commented 1 year ago

In the history implementation of barrett_reduce function, the output is in {0,...,q} congruent to a modulo q. But in Commits on Nov 20, 2020, the output of barrett_reduce is in {-(q-1)/2,...,(q-1)/2} congruent to a modulo q. Why is it modified like this？

sduyyy commented 1 year ago

In addition, what is the input range?

vincentvbh commented 11 months ago

Hi, if I remember correctly, literature shows that signed arithmetic is faster for this size of modular arithmetic. For example, there are instructions smmulr in Armv7E-M and vpmulhrsw in AVX2. Both of them operate on signed inputs, and there is no unsigned counterparts.

However, I'm not sure if this is the reason for the changes. Maybe others working Kyber already can answer this.

ronhombre commented 9 months ago

I made an implementation in pure Kotlin. I even added Barrett and Montgomery reductions, but I still don't know why. All my functions work in the unsigned space only. Maybe it's worth it to dig through the commit history.