content/posts: add drafts

2 files changed, 146 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
+
+```
diff --git a/content/posts/2026-01-02-new-years-primality-testing-by-hand.md b/content/posts/2026-01-02-new-years-primality-testing-by-hand.md
new file mode 100644
index 0000000..00c13da
--- /dev/null
+++ b/content/posts/2026-01-02-new-years-primality-testing-by-hand.md
@@ -0,0 +1,99 @@
+---
+slug: new-years-primality-testing-by-hand
+title: "New Year's Primality Testing by Hand"
+date: "2026-01-02T09:37:22-05:00"
+draft: true
+---
+
+Happy New Year!
+
+The number 2026 has two factors: 2 and 1013.  I wondered "is 1013
+prime?" and "for fun, can I solve this in my head?" (e.g. no calculator,
+computer, or pen and paper).
+
+If 1013 is *not* prime, then it is composite and must have at least one
+odd prime factor &le; &#x230A;&radic;1013&#x230B;.
+
+(We know the factor -- if it exists -- is odd because the factors of odd
+composite numbers are always odd, and we know the factor is prime
+because of the [fundamental theorem of arithmetic][]).
+
+So our approach will be to check the odd primes from 3 to &radic;1013 to
+see if any are a factor of 1013.
+
+Unfortunately we don't know &radic;1013, so we can't calculate the range
+upper bound.  Fortunately 1013 is close to 1024.  1024 is a handy power
+of 2, so lets use that instead:
+
+2. &radic;1024 = &radic;(2{{<sup 10>}}) = 2{{<sup 5>}} = 32
+3. 1013 &lt; 1024, so &radic;1013 &lt; &radic;1024
+4. Therefore, &radic;1013 &lt; 32
+
+So we need to test the odd primes in the range \[3,31\] to see if any
+are a factor of 1013.
+
+Before that, though, we narrow the list with the [divisibility rules][]:
+
+1. Remove 3 because the sum of the digits of 1013 isn't divisible by 3:
+   `1+1+3=5` and 3&#x2224;5
+2. Remove 5 because the last digit of 1013 isn't 0 or 5.
+3. Remove 7 because 5 times the last digit (3) plus the rest (101) is
+   not a multiple of 7: `5*3+101=116, 5*6+11=41`, and 7&#x2224;41.
+4. ...and so on for [11][], [13][], [17][], [19][], [23][], and [29][].
+
+(Full disclosure: I don't have the [divisibility rules][] for primes in
+the range \[11,29\] memorized; instead I checked to see if they were
+factors of 1013).
+
+The only remaining possibility is 31.  To check it, we can use the
+[Euclidean algorithm][] to check if `gcd(31, 1013) != 1` or do some
+brief arithmetic.  I chose the latter:
+
+1. 31 = (30 + 1)
+2. (30 + 1) * 33 = 990 + 33 = 1023
+3. The closest multiples of 31 are 992 and 1023, so 31&#x2224;1013.
+
+1013 does not have any odd prime factors in the range \[3,&radic;1013\],
+so it must be prime.
+
+Let's check our work:
+
+```python
+>>> import sympy
+>>> sympy.ntheory.primetest.isprime(1013)
+True
+```
+...
+
+Success!
+
+Further reading:
+
+- [Integer factorization][]
+- [Primality test][]
+- [Sieve of Eratosthenes][]
+
+[fundamental theorem of arithmetic]: https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
+  "Fundamental Theorem of Arithmetic"
+[divisibility rules]: https://en.wikipedia.org/wiki/Divisibility_rule
+  "shorthand rules for determining if a number is factor of another number without performing division"
+[11]: https://en.wikipedia.org/wiki/Divisibility_rule#11
+  "divisibility rules for 11"
+[13]: https://en.wikipedia.org/wiki/Divisibility_rule#13
+  "divisibility rules for 13"
+[17]: https://en.wikipedia.org/wiki/Divisibility_rule#17
+  "divisibility rules for 17"
+[19]: https://en.wikipedia.org/wiki/Divisibility_rule#19
+  "divisibility rules for 19"
+[23]: https://en.wikipedia.org/wiki/Divisibility_rule#23
+  "divisibility rules for 23"
+[29]: https://en.wikipedia.org/wiki/Divisibility_rule#29
+  "divisibility rules for 29"
+[euclidean algorithm]: https://en.wikipedia.org/wiki/Euclidean_algorithm
+  "Euclidean Algorithm"
+[integer factorization]: https://en.wikipedia.org/wiki/Integer_factorization
+  "Integer factorization"
+[primality test]: https://en.wikipedia.org/wiki/Primality_test
+  "Primality test"
+[sieve of eratosthenes]: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
+  "Sieve of Eratosthenes"