content/posts: add drafts

1 files changed, 47 insertions, 0 deletions

diff --git a/content/posts/2025-11-30-faster-ml-kem-barrett-reduction.md b/content/posts/2025-11-30-faster-ml-kem-barrett-reduction.md
new file mode 100644
index 0000000..c9a50c6
--- /dev/null
+++ b/content/posts/2025-11-30-faster-ml-kem-barrett-reduction.md
@@ -0,0 +1,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
+
+```