---
slug: faster-ml-kem-barrett-reduction
title: "Faster ML-KEM Barrett Reduction"
date: "2025-11-30T09:35:07-05:00"
draft: true
---

changes:

1. `b` is a constant `1` (common trick)
2. change `(a*((2^k)/n))>>k` to `((a>>12)*((1<<k)/n))>>(k-12)` so
   numerator product fits in `u32`
3. change mul by 3329 to three shifts and 3 adds (proth prime)

```ruby
# good:
# numerator product fits in u32
(((3000*3329)>>12)*((1<<31)/3329))>>19
=> 2999

# constant fits in u20
>> Math.log((1<<31)/3329, 2).ceil
=> 20

# better:
# numerator operands both fit in u16; product fits in u32
>> (((3000*3329)>>12)*((1<<27)/3329))>>15
=> 2999

# constant fits in u16
>> Math.log((1<<27)/3329, 2).ceil
=> 16

>> (((1000*3329)>>11)*((1<<27)/3329))>>16
=> 999
>> Math.log((1<<27)/3329, 2)
=> 15.299100671012633
>> Math.log((1<<28)/3329, 2)
=> 16.299118562796433

# check subset of 
>> (0...3329).each.map { |x| t = (x*3329+x) - 3329*((((x*3329)>>11)*((1<<27)/3329))>>16); { x: x, y: t - (t<3329 ? 0 : 3329), z: (x*3329+x) % 3329 } }.select { |row| row[:y] != row[:z] }
=> []

ct_mod5_,,, from pt-mldsa

```