reduce.go 807 B

1234567891011121314151617181920212223242526272829303132
  1. // poly.go - NewHope reductions.
  2. //
  3. // To the extent possible under law, Yawning Angel has waived all copyright
  4. // and related or neighboring rights to newhope, 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 newhope
  8. // Incomplete-reduction routines; for details on allowed input ranges
  9. // and produced output ranges, see the description in the paper:
  10. // https://cryptojedi.org/papers/#newhope
  11. const (
  12. qinv = 12287 // -inverse_mod(p,2^18)
  13. rlog = 18
  14. )
  15. func montgomeryReduce(a uint32) uint16 {
  16. u := a * qinv
  17. u &= ((1 << rlog) - 1)
  18. u *= paramQ
  19. a = (a + u) >> 18
  20. return uint16(a)
  21. }
  22. func barrettReduce(a uint16) uint16 {
  23. u := (uint32(a) * 5) >> 16
  24. u *= paramQ
  25. a -= uint16(u)
  26. return a
  27. }