blob: c9a50c6ec845f9e1cb1a84efd7a078ef25b45e90 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
---
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
```
|
