From 4ed232aa72e6b507b15b333528aa6a978b72afee Mon Sep 17 00:00:00 2001
From: Simon Tatham <anakin@pobox.com>
Date: Sat, 12 Apr 2025 12:57:55 +0100
Subject: [PATCH] Implement fast squaring, and use it in Div

---
 src/finitenimber.rs | 72 +++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 67 insertions(+), 5 deletions(-)

diff --git a/src/finitenimber.rs b/src/finitenimber.rs
index c74e3a1..974152a 100644
--- a/src/finitenimber.rs
+++ b/src/finitenimber.rs
@@ -356,6 +356,22 @@ impl<'a> FiniteNimberRef<'a> {
         }
     }
 
+    fn square_recurse(self, level: usize) -> FiniteNimber {
+        match level.checked_sub(1) {
+            Some(sublevel) => {
+                let (lo, hi) = self.split(sublevel);
+                let lo2 = lo.square_recurse(sublevel);
+                let hi2 = hi.square_recurse(sublevel);
+                (lo2 + hi2.to_ref().mul_by_h(sublevel))
+                    .to_ref()
+                    .join(hi2.to_ref(), sublevel)
+            }
+
+            // At level 0, both elements of GF(2) square to themselves.
+            None => self.into(),
+        }
+    }
+
     fn mul_recurse(
         self,
         other: FiniteNimberRef<'a>,
@@ -380,6 +396,16 @@ impl<'a> FiniteNimberRef<'a> {
     }
 }
 
+impl FiniteNimber {
+    /// Compute the square of a nimber, faster than the general
+    /// multiplication algorithm performed by the `Mul` trait can do
+    /// it.
+    pub fn square(&self) -> FiniteNimber {
+        let r = self.to_ref();
+        r.square_recurse(r.level())
+    }
+}
+
 impl<'a, 'b> Mul<FiniteNimberRef<'a>> for FiniteNimberRef<'b> {
     type Output = FiniteNimber;
     fn mul(self, other: FiniteNimberRef<'a>) -> FiniteNimber {
@@ -392,14 +418,14 @@ impl<'a> FiniteNimberRef<'a> {
     fn inverse_recurse(self, level: usize) -> FiniteNimber {
         match level.checked_sub(1) {
             Some(sublevel) => {
-                let (alo, ahi) = self.split(sublevel);
-                let sum = alo + ahi;
-                let sq = ahi * ahi; // todo! dedicated squaring function
-                let det = alo * sum.to_ref() + sq.to_ref().mul_by_h(sublevel);
+                let (lo, hi) = self.split(sublevel);
+                let sum = lo + hi;
+                let sq = hi.square_recurse(sublevel);
+                let det = lo * sum.to_ref() + sq.to_ref().mul_by_h(sublevel);
                 let detinv = det.to_ref().inverse_recurse(sublevel);
                 (detinv.to_ref() * sum)
                     .to_ref()
-                    .join((detinv.to_ref() * ahi).to_ref(), sublevel)
+                    .join((detinv.to_ref() * hi).to_ref(), sublevel)
             }
 
             // At level 0, we're in GF(2), so the only invertible
@@ -702,6 +728,42 @@ mod tests {
         );
     }
 
+    #[test]
+    fn square() {
+        assert_eq!(
+            FiniteNimber::from(0x80).square(),
+            FiniteNimber::from(0xde)
+        );
+        assert_eq!(
+            FiniteNimber::from(0x8000).square(),
+            FiniteNimber::from(0xde4a)
+        );
+
+        assert_eq!(
+            FiniteNimber::from(vec![
+                0x3f84d5b5b5470917,
+                0xc0ac29b7c97c50dd,
+                0xbe5466cf34e90c6c,
+                0x452821e638d01377,
+                0x082efa98ec4e6c89,
+                0xa4093822299f31d0,
+                0x13198a2e03707344,
+                0x243f6a8885a308d3,
+            ])
+            .square(),
+            FiniteNimber::from(vec![
+                0xd0e74a0945d35342,
+                0xfa91473032b5438a,
+                0xe17bdc047300f99d,
+                0x1a51cba4adb8ddb9,
+                0xdc06e76f54f372c0,
+                0xe74d7b7c65542a19,
+                0xffe69bcb391c628b,
+                0x32ae6e49dcd65156,
+            ])
+        );
+    }
+
     #[test]
     fn div() {
         assert_eq!(
-- 
2.30.2