reduce.go 1.1 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243
  1. // reduce.go - Montgomery, Barret, and Full reduction.
  2. //
  3. // To the extent possible under law, Yawning Angel has waived all copyright
  4. // and related or neighboring rights to the software, using the Creative
  5. // Commons "CC0" public domain dedication. See LICENSE or
  6. // <http://creativecommons.org/publicdomain/zero/1.0/> for full details.
  7. package kyber
  8. const (
  9. qinv = 7679 // -inverse_mod(q,2^18)
  10. rlog = 18
  11. )
  12. // Montgomery reduction; given a 32-bit integer a, computes 16-bit integer
  13. // congruent to a * R^-1 mod q, where R=2^18 (see value of rlog).
  14. func montgomeryReduce(a uint32) uint16 {
  15. u := a * qinv
  16. u &= (1 << rlog) - 1
  17. u *= kyberQ
  18. a += u
  19. return uint16(a >> rlog)
  20. }
  21. // Barrett reduction; given a 16-bit integer a, computes 16-bit integer
  22. // congruent to a mod q in {0,...,11768}.
  23. func barrettReduce(a uint16) uint16 {
  24. u := uint32(a >> 13) // ((uint32_t) a * sinv) >> 16
  25. u *= kyberQ
  26. a -= uint16(u)
  27. return a
  28. }
  29. // Full reduction; given a 16-bit integer a, computes unsigned integer a mod q.
  30. func freeze(x uint16) uint16 {
  31. r := barrettReduce(x)
  32. m := r - kyberQ
  33. c := int16(m)
  34. c >>= 15
  35. r = m ^ ((r ^ m) & uint16(c))
  36. return r
  37. }