ntt.go 1.9 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
  1. // ntt.go - Number-Theoretic Transform.
  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. // Computes negacyclic number-theoretic transform (NTT) of a polynomial (vector
  9. // of 256 coefficients) in place; inputs assumed to be in normal order, output
  10. // in bitreversed order.
  11. func nttRef(p *[kyberN]uint16) {
  12. var j int
  13. k := 1
  14. for level := 7; level >= 0; level-- {
  15. distance := 1 << uint(level)
  16. for start := 0; start < kyberN; start = j + distance {
  17. zeta := zetas[k]
  18. k++
  19. for j = start; j < start+distance; j++ {
  20. t := montgomeryReduce(uint32(zeta) * uint32(p[j+distance]))
  21. p[j+distance] = barrettReduce(p[j] + 4*kyberQ - t)
  22. if level&1 == 1 { // odd level
  23. p[j] = p[j] + t // Omit reduction (be lazy)
  24. } else {
  25. p[j] = barrettReduce(p[j] + t)
  26. }
  27. }
  28. }
  29. }
  30. }
  31. // Computes inverse of negacyclic number-theoretic transform (NTT) of a
  32. // polynomial (vector of 256 coefficients) in place; inputs assumed to be in
  33. // bitreversed order, output in normal order.
  34. func invnttRef(a *[kyberN]uint16) {
  35. for level := 0; level < 8; level++ {
  36. distance := 1 << uint(level)
  37. for start := 0; start < distance; start++ {
  38. var jTwiddle int
  39. for j := start; j < kyberN-1; j += 2 * distance {
  40. w := uint32(omegasInvBitrevMontgomery[jTwiddle])
  41. jTwiddle++
  42. temp := a[j]
  43. if level&1 == 1 { // odd level
  44. a[j] = barrettReduce(temp + a[j+distance])
  45. } else {
  46. a[j] = temp + a[j+distance] // Omit reduction (be lazy)
  47. }
  48. t := w * (uint32(temp) + 4*kyberQ - uint32(a[j+distance]))
  49. a[j+distance] = montgomeryReduce(t)
  50. }
  51. }
  52. }
  53. for i, v := range psisInvMontgomery {
  54. a[i] = montgomeryReduce(uint32(a[i]) * uint32(v))
  55. }
  56. }