Class: MLKEM::Math::NTT

Inherits:
Object
  • Object
show all
Defined in:
lib/ml_kem/math/ntt.rb

Overview

Implements the Number Theoretic Transform (NTT) and related operations as defined in the ML-KEM standard (2024), used for polynomial arithmetic in the ring Z_q/(X^256 + 1).

Includes forward and inverse NTT transforms, pointwise multiplication, and the base case multiplication algorithm.

Since:

  • 0.1.0

Instance Method Summary collapse

Constructor Details

#initialize(q = Constants::Q) ⇒ NTT

Initializes an NTT instance with a modulus ‘q`.

Examples:

ntt = NTT.new

Parameters:

  • q (Integer) (defaults to: Constants::Q) —

    The modulus for all modular arithmetic.

Since:

  • 0.1.0



20
21
22
 
# File 'lib/ml_kem/math/ntt.rb', line 20

def initialize(q = Constants::Q)
  @q = q
end

Instance Method Details

#base_case_multiply(a0, a1, b0, b1, gam) ⇒ Array<Integer>

Performs the base case multiplication for two polynomial coefficient pairs.

Implements Algorithm 12, BaseCaseMultiply(a0, a1, b0, b1, gamma).

Examples:

ntt.base_case_multiply(3, 4, 5, 6, gamma) # => [expected_c0, expected_c1]

Parameters:

  • a0 (Integer) —

    Coefficient a_0

  • a1 (Integer) —

    Coefficient a_1

  • b0 (Integer) —

    Coefficient b_0

  • b1 (Integer) —

    Coefficient b_1

  • gam (Integer) —

    Precomputed gamma value

Returns:

  • (Array<Integer>) —

    The resulting coefficients [c0, c1]

Since:

  • 0.1.0



116
117
118
119
120
 
# File 'lib/ml_kem/math/ntt.rb', line 116

def base_case_multiply(a0, a1, b0, b1, gam)
  c0 = (a0 * b0 + a1 * b1 * gam) % @q
  c1 = (a0 * b1 + a1 * b0) % @q
  [c0, c1]
end

#inverse_ntt(f) ⇒ Array<Integer>

Applies the inverse Number Theoretic Transform to a polynomial.

Implements Algorithm 10, NTT^<sup>-1</sup>(f).

Examples:

original = ntt.inverse_ntt(transformed_poly)

Parameters:

  • f (Array<Integer>) —

    A 256-element array in the NTT domain.

Returns:

  • (Array<Integer>) —

    The inverse-transformed polynomial.

Since:

  • 0.1.0



63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/ml_kem/math/ntt.rb', line 63

def inverse_ntt(f)
  f = f.dup
  i = 127
  le = 2
  
  while le <= 128
    (0...256).step(2 * le) do |st|
      ze = Constants::ZETA_NTT[i]
      i -= 1
      (st...(st + le)).each do |j|
        t = f[j]
        f[j] = (t + f[j + le]) % @q
        f[j + le] = (ze * (f[j + le] - t)) % @q
      end
    end
    le *= 2
  end
  
  f.map { |x| (x * 3303) % @q }
end

#multiply_ntts(f, g) ⇒ Array<Integer>

Performs pointwise multiplication in the NTT domain.

Implements Algorithm 11, MultiplyNTTs(~f, ~g).

Examples:

product = ntt.multiply_ntts(ntt_f, ntt_g)

Parameters:

  • f (Array<Integer>) —

    First polynomial in NTT form.

  • g (Array<Integer>) —

    Second polynomial in NTT form.

Returns:

  • (Array<Integer>) —

    Result of the pointwise multiplication.

Since:

  • 0.1.0



94
95
96
97
98
99
100
101
 
# File 'lib/ml_kem/math/ntt.rb', line 94

def multiply_ntts(f, g)
  h = []
  (0...256).step(2) do |ii|
    h.concat(base_case_multiply(f[ii], f[ii + 1], g[ii], g[ii + 1], 
                                Constants::ZETA_MUL[ii / 2]))
  end
  h
end

#ntt(f) ⇒ Array<Integer>

Applies the forward Number Theoretic Transform to a polynomial.

Implements Algorithm 9, NTT(f).

Examples:

transformed = ntt.ntt(original_poly)

Parameters:

  • f (Array<Integer>) —

    A 256-element array representing the polynomial.

Returns:

  • (Array<Integer>) —

    The transformed polynomial.

Since:

  • 0.1.0



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/ml_kem/math/ntt.rb', line 33

def ntt(f)
  f = f.dup
  i = 1
  le = 128
  
  while le >= 2
    (0...256).step(2 * le) do |st|
      ze = Constants::ZETA_NTT[i]
      i += 1
      (st...(st + le)).each do |j|
        t = (ze * f[j + le]) % @q
        f[j + le] = (f[j] - t) % @q
        f[j] = (f[j] + t) % @q
      end
    end
    le /= 2
  end
  
  f
end