Skip to main content

logicaffeine_proof/
lattice.rs

1//! LLL lattice reduction — the geometric lens of the compression campaign.
2//!
3//! Every rung so far reads structure through a finite field: linear/algebraic/correlation attacks are
4//! linear algebra or statistics over GF(2), GF(p), GF(2ⁿ). Lattice reduction reads it through the
5//! GEOMETRY OF NUMBERS instead — an orthogonal lens. A lattice is the integer span of a basis; its short
6//! vectors are its most compressed representatives, and a SHORT vector *is* a hidden small relation among
7//! the basis rows. So "find the shortest vector" is exactly "find the maximal compression," and the
8//! symmetry being broken is the lattice's own geometry rather than a field's algebra.
9//!
10//! This is the lens that reaches the cryptographic weaknesses the field-based rungs cannot express: an
11//! RSA key that is *structured but not factorable by Fermat* — small hidden roots (Coppersmith),
12//! partial key exposure, a private exponent below Wiener's bound (Boneh–Durfee `d < N^0.292`) — leaks a
13//! short lattice vector even when no factoring shortcut exists. It is a different game than factoring:
14//! the compression game, played on the reals. [`lll_reduce`] is that lens; Coppersmith's small-roots
15//! method is built on top of it.
16//!
17//! The reduction is EXACT — Gram–Schmidt over [`Rational`], no floating point — so its output is a
18//! certified reduced basis, not a numerical approximation.
19
20use logicaffeine_base::numeric::{BigInt, Rational};
21
22fn zero() -> Rational {
23    Rational::zero()
24}
25
26fn rat(n: i64, d: i64) -> Rational {
27    Rational::new(BigInt::from_i64(n), BigInt::from_i64(d)).expect("nonzero denominator")
28}
29
30/// The inner product of two rational vectors.
31fn dot(a: &[Rational], b: &[Rational]) -> Rational {
32    a.iter().zip(b).fold(zero(), |s, (x, y)| s.add(&x.mul(y)))
33}
34
35/// Gram–Schmidt orthogonalization: the orthogonal vectors `b*ᵢ` and the coefficients
36/// `μᵢⱼ = ⟨bᵢ, b*ⱼ⟩ / ⟨b*ⱼ, b*ⱼ⟩`, all exact over the rationals.
37fn gram_schmidt(b: &[Vec<Rational>]) -> (Vec<Vec<Rational>>, Vec<Vec<Rational>>) {
38    let n = b.len();
39    let mut bstar: Vec<Vec<Rational>> = Vec::with_capacity(n);
40    let mut mu = vec![vec![zero(); n]; n];
41    for i in 0..n {
42        let mut v = b[i].clone();
43        for j in 0..i {
44            let m = dot(&b[i], &bstar[j])
45                .div(&dot(&bstar[j], &bstar[j]))
46                .expect("independent basis");
47            for d in 0..v.len() {
48                v[d] = v[d].sub(&m.mul(&bstar[j][d]));
49            }
50            mu[i][j] = m;
51        }
52        bstar.push(v);
53    }
54    (bstar, mu)
55}
56
57/// The LLL algorithm proper, on rational vectors: returns a reduced basis of the same lattice.
58fn lll_core(mut b: Vec<Vec<Rational>>) -> Vec<Vec<Rational>> {
59    let n = b.len();
60    if n < 2 {
61        return b;
62    }
63    let delta = rat(3, 4);
64    let half = rat(1, 2);
65    let (mut bstar, mut mu) = gram_schmidt(&b);
66    let mut norm: Vec<Rational> = (0..n).map(|i| dot(&bstar[i], &bstar[i])).collect();
67
68    let mut k = 1;
69    while k < n {
70        // Size-reduce bₖ against b_{k-1}, …, b₀.
71        for j in (0..k).rev() {
72            if mu[k][j].abs() > half {
73                let q = mu[k][j].round(); // nearest integer
74                let qr = Rational::from_bigint(q);
75                for d in 0..b[k].len() {
76                    b[k][d] = b[k][d].sub(&qr.mul(&b[j][d]));
77                }
78                mu[k][j] = mu[k][j].sub(&qr);
79                for l in 0..j {
80                    mu[k][l] = mu[k][l].sub(&qr.mul(&mu[j][l]));
81                }
82            }
83        }
84        // Lovász condition: ‖b*ₖ‖² ≥ (δ − μ²ₖ,ₖ₋₁)·‖b*ₖ₋₁‖².
85        let rhs = delta
86            .sub(&mu[k][k - 1].mul(&mu[k][k - 1]))
87            .mul(&norm[k - 1]);
88        if norm[k] >= rhs {
89            k += 1;
90        } else {
91            b.swap(k, k - 1);
92            let (bs, m) = gram_schmidt(&b);
93            bstar = bs;
94            mu = m;
95            norm = (0..n).map(|i| dot(&bstar[i], &bstar[i])).collect();
96            k = if k >= 2 { k - 1 } else { 1 };
97        }
98    }
99    b
100}
101
102/// LLL-reduce an integer lattice basis (the rows of `basis`), returning a reduced basis of the same
103/// lattice with short, nearly-orthogonal vectors. Exact arithmetic throughout (Gram–Schmidt over the
104/// rationals, size reduction with `|μ| ≤ ½`, the Lovász swap at `δ = ¾`), so the result is a certified
105/// LLL-reduced basis. The first row is a short vector — for a lattice built to encode a cryptographic
106/// weakness, that short vector is the leaked secret.
107pub fn lll_reduce(basis: &[Vec<i64>]) -> Vec<Vec<BigInt>> {
108    let b = basis
109        .iter()
110        .map(|row| row.iter().map(|&x| Rational::from_i64(x)).collect())
111        .collect();
112    lll_core(b)
113        .iter()
114        .map(|row| row.iter().map(|r| r.round()).collect())
115        .collect()
116}
117
118/// The bit length of `|x|`.
119fn bit_len(x: &BigInt) -> usize {
120    let (_, bytes) = x.to_le_bytes();
121    for (i, &byte) in bytes.iter().enumerate().rev() {
122        if byte != 0 {
123            return i * 8 + (8 - byte.leading_zeros() as usize);
124        }
125    }
126    0
127}
128
129/// Floating-point Gram–Schmidt of an EXACT integer basis, uniformly down-scaled so the doubles stay
130/// finite (the scale cancels in `μ` and in the Lovász ratio, both scale-invariant). Returns `(μ, ‖b*‖²)`.
131fn gram_schmidt_f64(b: &[Vec<BigInt>]) -> (Vec<Vec<f64>>, Vec<f64>) {
132    let (n, dim) = (b.len(), b[0].len());
133    let maxbits = b.iter().flatten().map(bit_len).max().unwrap_or(0);
134    let shift = maxbits.saturating_sub(900);
135    let mut scale = BigInt::from_i64(1);
136    for _ in 0..shift {
137        scale = scale.mul(&BigInt::from_i64(2));
138    }
139    let cf: Vec<Vec<f64>> = b
140        .iter()
141        .map(|row| {
142            row.iter()
143                .map(|x| {
144                    Rational::new(x.clone(), scale.clone())
145                        .map(|r| r.to_f64())
146                        .unwrap_or(0.0)
147                })
148                .collect()
149        })
150        .collect();
151    let mut bstar = vec![vec![0f64; dim]; n];
152    let mut mu = vec![vec![0f64; n]; n];
153    for i in 0..n {
154        bstar[i].clone_from(&cf[i]);
155        for j in 0..i {
156            let dp: f64 = cf[i].iter().zip(&bstar[j]).map(|(a, c)| a * c).sum();
157            let nj: f64 = bstar[j].iter().map(|c| c * c).sum();
158            let m = if nj != 0.0 { dp / nj } else { 0.0 };
159            mu[i][j] = m;
160            for d in 0..dim {
161                bstar[i][d] -= m * bstar[j][d];
162            }
163        }
164    }
165    let norm = bstar
166        .iter()
167        .map(|v| v.iter().map(|c| c * c).sum())
168        .collect();
169    (mu, norm)
170}
171
172fn vdot(u: &[BigInt], v: &[BigInt]) -> BigInt {
173    u.iter()
174        .zip(v)
175        .fold(BigInt::zero(), |a, (x, y)| a.add(&x.mul(y)))
176}
177
178// ---- BigFloat: fixed-precision binary floating point for the L² reduction (fpLLL) --------------------
179//
180// The f64 Gram–Schmidt loses precision on Boneh–Durfee's huge dynamic range; the exact integer LLL is
181// correct but its sub-determinants grow to ~2^(dim·bits) and crawl. BigFloat splits the difference: a
182// `BigInt` mantissa kept to a FIXED number of significant bits (`FP_PREC`) times `2^exp`. It behaves like
183// floating point (fast, bounded size — no blow-up) but with enough bits to survive the dynamic range.
184
185const FP_PREC: u64 = 2048;
186
187fn bit_length(x: &BigInt) -> u64 {
188    let (_, bytes) = x.to_le_bytes();
189    for (i, &b) in bytes.iter().enumerate().rev() {
190        if b != 0 {
191            return i as u64 * 8 + (8 - b.leading_zeros() as u64);
192        }
193    }
194    0
195}
196
197fn two_pow(k: u64) -> BigInt {
198    BigInt::from_i64(2).pow(k as u32)
199}
200
201fn shl(x: &BigInt, k: u64) -> BigInt {
202    if k == 0 {
203        x.clone()
204    } else {
205        x.mul(&two_pow(k))
206    }
207}
208
209fn shr(x: &BigInt, k: u64) -> BigInt {
210    if k == 0 {
211        x.clone()
212    } else {
213        x.div_rem(&two_pow(k)).expect("nonzero").0
214    }
215}
216
217#[derive(Clone)]
218struct BigFloat {
219    m: BigInt,
220    e: i64,
221}
222
223impl BigFloat {
224    fn normalized(m: BigInt, e: i64) -> Self {
225        if m.is_zero() {
226            return Self { m, e: 0 };
227        }
228        let bl = bit_length(&m);
229        if bl > FP_PREC {
230            let s = bl - FP_PREC;
231            Self {
232                m: shr(&m, s),
233                e: e + s as i64,
234            }
235        } else {
236            Self { m, e }
237        }
238    }
239    fn zero() -> Self {
240        Self {
241            m: BigInt::zero(),
242            e: 0,
243        }
244    }
245    fn from_bigint(n: &BigInt) -> Self {
246        Self::normalized(n.clone(), 0)
247    }
248    fn from_i64(n: i64) -> Self {
249        Self::from_bigint(&BigInt::from_i64(n))
250    }
251    fn add(&self, o: &Self) -> Self {
252        if self.m.is_zero() {
253            return o.clone();
254        }
255        if o.m.is_zero() {
256            return self.clone();
257        }
258        // Align to the MINIMUM exponent (shift mantissas UP, losing nothing); if one operand is more than
259        // FP_PREC bits smaller in magnitude, it is below precision and the larger one is returned.
260        let mag_s = self.e + bit_length(&self.m) as i64;
261        let mag_o = o.e + bit_length(&o.m) as i64;
262        if mag_s > mag_o + FP_PREC as i64 + 8 {
263            return self.clone();
264        }
265        if mag_o > mag_s + FP_PREC as i64 + 8 {
266            return o.clone();
267        }
268        let e = self.e.min(o.e);
269        let ma = shl(&self.m, (self.e - e) as u64);
270        let mb = shl(&o.m, (o.e - e) as u64);
271        Self::normalized(ma.add(&mb), e)
272    }
273    fn neg(&self) -> Self {
274        Self {
275            m: self.m.negated(),
276            e: self.e,
277        }
278    }
279    fn sub(&self, o: &Self) -> Self {
280        self.add(&o.neg())
281    }
282    fn mul(&self, o: &Self) -> Self {
283        Self::normalized(self.m.mul(&o.m), self.e + o.e)
284    }
285    fn div(&self, o: &Self) -> Self {
286        let num = shl(&self.m, FP_PREC);
287        Self::normalized(
288            num.div_rem(&o.m).expect("nonzero div").0,
289            self.e - o.e - FP_PREC as i64,
290        )
291    }
292    fn abs(&self) -> Self {
293        Self {
294            m: self.m.abs(),
295            e: self.e,
296        }
297    }
298    fn cmp(&self, o: &Self) -> std::cmp::Ordering {
299        let d = self.sub(o).m;
300        if d.is_zero() {
301            std::cmp::Ordering::Equal
302        } else if d.is_negative() {
303            std::cmp::Ordering::Less
304        } else {
305            std::cmp::Ordering::Greater
306        }
307    }
308    /// Nearest integer (ties away from zero).
309    fn round(&self) -> BigInt {
310        if self.e >= 0 {
311            shl(&self.m, self.e as u64)
312        } else {
313            let k = (-self.e) as u64;
314            let half = two_pow(k - 1);
315            let adj = if self.m.is_negative() {
316                self.m.sub(&half)
317            } else {
318                self.m.add(&half)
319            };
320            adj.div_rem(&two_pow(k)).expect("nonzero").0
321        }
322    }
323}
324
325fn dot_bf(u: &[BigFloat], v: &[BigFloat]) -> BigFloat {
326    u.iter()
327        .zip(v)
328        .fold(BigFloat::zero(), |a, (x, y)| a.add(&x.mul(y)))
329}
330
331fn gram_schmidt_bf(b: &[Vec<BigInt>]) -> (Vec<Vec<BigFloat>>, Vec<BigFloat>) {
332    let (n, dim) = (b.len(), b[0].len());
333    let cf: Vec<Vec<BigFloat>> = b
334        .iter()
335        .map(|r| r.iter().map(BigFloat::from_bigint).collect())
336        .collect();
337    let mut bstar = vec![vec![BigFloat::zero(); dim]; n];
338    let mut mu = vec![vec![BigFloat::zero(); n]; n];
339    for i in 0..n {
340        bstar[i].clone_from(&cf[i]);
341        for j in 0..i {
342            let m = dot_bf(&cf[i], &bstar[j]).div(&dot_bf(&bstar[j], &bstar[j]));
343            for d in 0..dim {
344                bstar[i][d] = bstar[i][d].sub(&m.mul(&bstar[j][d]));
345            }
346            mu[i][j] = m;
347        }
348    }
349    let norm = bstar.iter().map(|v| dot_bf(v, v)).collect();
350    (mu, norm)
351}
352
353/// Incrementally update the Gram–Schmidt data `(mu, norm)` when swapping basis rows `k` and `k−1` — the
354/// standard LLL swap formulas, so a swap is `O(n)` rather than a full `O(n²·dim)` recomputation.
355fn swap_gso(
356    k: usize,
357    n: usize,
358    b: &mut [Vec<BigInt>],
359    mu: &mut [Vec<BigFloat>],
360    norm: &mut [BigFloat],
361) {
362    b.swap(k, k - 1);
363    let nu = mu[k][k - 1].clone();
364    let db = norm[k].add(&nu.mul(&nu).mul(&norm[k - 1])); // new ‖b*_{k-1}‖²
365    let new_mu = nu.mul(&norm[k - 1]).div(&db);
366    let new_norm_k = norm[k - 1].mul(&norm[k]).div(&db);
367    {
368        let (lower, upper) = mu.split_at_mut(k);
369        let (row_km1, row_k) = (&mut lower[k - 1], &mut upper[0]);
370        for j in 0..(k - 1) {
371            std::mem::swap(&mut row_km1[j], &mut row_k[j]);
372        }
373    }
374    mu[k][k - 1] = new_mu.clone();
375    norm[k] = new_norm_k;
376    norm[k - 1] = db;
377    for i in (k + 1)..n {
378        let t = mu[i][k].clone();
379        mu[i][k] = mu[i][k - 1].sub(&nu.mul(&t));
380        mu[i][k - 1] = t.add(&new_mu.mul(&mu[i][k]));
381    }
382}
383
384/// The L² lattice reduction (fpLLL): LLL with a BigFloat Gram–Schmidt — fast like floating point, but
385/// with `FP_PREC` bits of precision so it survives the high dynamic range of Coppersmith/Boneh–Durfee
386/// lattices where f64 fails, and without the determinant blow-up of the exact integer LLL. The basis
387/// stays exact integer; only the steering is in BigFloat, and swaps update the Gram–Schmidt incrementally
388/// (`O(n³)` overall rather than the `O(n⁵)` of recompute-on-swap).
389pub fn lll_reduce_bigint_fp(basis: &[Vec<BigInt>]) -> Vec<Vec<BigInt>> {
390    let n = basis.len();
391    if n < 2 {
392        return basis.to_vec();
393    }
394    let dim = basis[0].len();
395    let mut b = basis.to_vec();
396    let delta = BigFloat::from_i64(3).div(&BigFloat::from_i64(4));
397    let half = BigFloat::from_i64(1).div(&BigFloat::from_i64(2));
398    let (mut mu, mut norm) = gram_schmidt_bf(&b);
399    let max_bits = b.iter().flatten().map(bit_length).max().unwrap_or(1) as usize;
400    let cap = (max_bits + 16) * n * n * 4;
401    let mut k = 1;
402    let mut guard = 0usize;
403    while k < n && guard < cap {
404        guard += 1;
405        for j in (0..k).rev() {
406            if mu[k][j].abs().cmp(&half) == std::cmp::Ordering::Greater {
407                let q = mu[k][j].round();
408                if !q.is_zero() {
409                    let qf = BigFloat::from_bigint(&q);
410                    for d in 0..dim {
411                        b[k][d] = b[k][d].sub(&q.mul(&b[j][d]));
412                    }
413                    mu[k][j] = mu[k][j].sub(&qf);
414                    for l in 0..j {
415                        mu[k][l] = mu[k][l].sub(&qf.mul(&mu[j][l]));
416                    }
417                }
418            }
419        }
420        let rhs = delta
421            .sub(&mu[k][k - 1].mul(&mu[k][k - 1]))
422            .mul(&norm[k - 1]);
423        if norm[k].cmp(&rhs) != std::cmp::Ordering::Less {
424            k += 1;
425        } else {
426            swap_gso(k, n, &mut b, &mut mu, &mut norm);
427            k = if k >= 2 { k - 1 } else { 1 };
428        }
429    }
430    b
431}
432
433/// Nearest integer to `a/b` for `b > 0`.
434fn round_div(a: &BigInt, b: &BigInt) -> BigInt {
435    let (q, r) = a.div_rem(b).expect("nonzero");
436    if BigInt::from_i64(2).mul(&r.abs()) > *b {
437        if a.is_negative() {
438            q.sub(&BigInt::from_i64(1))
439        } else {
440            q.add(&BigInt::from_i64(1))
441        }
442    } else {
443        q
444    }
445}
446
447fn redi(k: usize, l: usize, b: &mut [Vec<BigInt>], d: &[BigInt], lam: &mut [Vec<BigInt>]) {
448    if BigInt::from_i64(2).mul(&lam[k][l].abs()) <= d[l] {
449        return;
450    }
451    let q = round_div(&lam[k][l], &d[l]);
452    let bl = b[l].clone();
453    for c in 0..bl.len() {
454        b[k][c] = b[k][c].sub(&q.mul(&bl[c]));
455    }
456    lam[k][l] = lam[k][l].sub(&q.mul(&d[l]));
457    let laml = lam[l].clone();
458    for i in 1..l {
459        lam[k][i] = lam[k][i].sub(&q.mul(&laml[i]));
460    }
461}
462
463fn swapi(k: usize, n: usize, b: &mut [Vec<BigInt>], d: &mut [BigInt], lam: &mut [Vec<BigInt>]) {
464    b.swap(k, k - 1);
465    for j in 1..=k.saturating_sub(2) {
466        let t = lam[k][j].clone();
467        lam[k][j] = lam[k - 1][j].clone();
468        lam[k - 1][j] = t;
469    }
470    let lambda = lam[k][k - 1].clone();
471    let bval = d[k - 2]
472        .mul(&d[k])
473        .add(&lambda.mul(&lambda))
474        .div_rem(&d[k - 1])
475        .expect("exact")
476        .0;
477    for i in (k + 1)..=n {
478        let t = lam[i][k].clone();
479        let new_ik = d[k]
480            .mul(&lam[i][k - 1])
481            .sub(&lambda.mul(&t))
482            .div_rem(&d[k - 1])
483            .expect("exact")
484            .0;
485        let new_ik1 = bval
486            .mul(&t)
487            .add(&lambda.mul(&new_ik))
488            .div_rem(&d[k])
489            .expect("exact")
490            .0;
491        lam[i][k] = new_ik;
492        lam[i][k - 1] = new_ik1;
493    }
494    d[k - 1] = bval;
495}
496
497/// Exact integer LLL (Cohen, *A Course in Computational Algebraic Number Theory*, Algorithm 2.6.3): the
498/// Gram–Schmidt quantities are tracked as EXACT integers (the sub-determinants `dᵢ` and the scaled
499/// coefficients `λᵢⱼ = dⱼ·μᵢⱼ`), with Bareiss-style exact division — no floating point (so no precision
500/// loss on high-dynamic-range lattices) and no rationals (so no coefficient blow-up). This is the
501/// trustworthy reduction the Boneh–Durfee independence diagnosis needs.
502pub fn lll_reduce_bigint_exact(basis: &[Vec<BigInt>]) -> Vec<Vec<BigInt>> {
503    let n = basis.len();
504    if n < 2 {
505        return basis.to_vec();
506    }
507    let mut b: Vec<Vec<BigInt>> = vec![Vec::new()]; // 1-indexed; b[0] is a dummy
508    b.extend(basis.iter().cloned());
509    let mut d = vec![BigInt::zero(); n + 2];
510    d[0] = BigInt::from_i64(1);
511    let mut lam = vec![vec![BigInt::zero(); n + 2]; n + 2];
512
513    d[1] = vdot(&b[1], &b[1]);
514    let mut k = 2;
515    let mut kmax = 1;
516    while k <= n {
517        if k > kmax {
518            kmax = k;
519            for j in 1..=k {
520                let mut u = vdot(&b[k], &b[j]);
521                for i in 1..j {
522                    u = d[i]
523                        .mul(&u)
524                        .sub(&lam[k][i].mul(&lam[j][i]))
525                        .div_rem(&d[i - 1])
526                        .expect("exact")
527                        .0;
528                }
529                if j < k {
530                    lam[k][j] = u;
531                } else {
532                    d[k] = u;
533                }
534            }
535        }
536        redi(k, k - 1, &mut b, &d, &mut lam);
537        let lhs = BigInt::from_i64(4).mul(&d[k]).mul(&d[k - 2]);
538        let rhs = BigInt::from_i64(3)
539            .mul(&d[k - 1].mul(&d[k - 1]))
540            .sub(&BigInt::from_i64(4).mul(&lam[k][k - 1].mul(&lam[k][k - 1])));
541        if lhs < rhs {
542            swapi(k, n, &mut b, &mut d, &mut lam);
543            k = if k - 1 >= 2 { k - 1 } else { 2 };
544        } else {
545            for l in (1..=k.saturating_sub(2)).rev() {
546                redi(k, l, &mut b, &d, &mut lam);
547            }
548            k += 1;
549        }
550    }
551    b.into_iter().skip(1).collect()
552}
553
554/// LLL-reduce a `BigInt` lattice basis — the entry point for lattices with huge entries, such as the
555/// `N^m`-scaled rows of Coppersmith's method. The symmetry that makes this fast: only the BASIS need be
556/// exact; the Gram–Schmidt that steers the size-reductions and Lovász swaps runs in floating point, so
557/// there is no rational coefficient blow-up. The reduced basis is still exact integer, and correctness is
558/// re-checked downstream (a Coppersmith root either divides `N` or it does not).
559pub fn lll_reduce_bigint(basis: &[Vec<BigInt>]) -> Vec<Vec<BigInt>> {
560    let n = basis.len();
561    if n < 2 {
562        return basis.to_vec();
563    }
564    let dim = basis[0].len();
565    let mut b = basis.to_vec();
566    let (mut mu, mut norm) = gram_schmidt_f64(&b);
567    let mut k = 1;
568    let mut guard = 0usize;
569    let cap = 2000 * n * n; // precision backstop against float-induced non-termination
570    while k < n && guard < cap {
571        guard += 1;
572        for j in (0..k).rev() {
573            if mu[k][j].abs() > 0.5 {
574                let q = mu[k][j].round();
575                if q != 0.0 {
576                    let qb = BigInt::parse_decimal(&format!("{q:.0}")).unwrap_or_else(BigInt::zero);
577                    for d in 0..dim {
578                        b[k][d] = b[k][d].sub(&qb.mul(&b[j][d]));
579                    }
580                    mu[k][j] -= q;
581                    for l in 0..j {
582                        mu[k][l] -= q * mu[j][l];
583                    }
584                }
585            }
586        }
587        if norm[k] >= (0.75 - mu[k][k - 1] * mu[k][k - 1]) * norm[k - 1] {
588            k += 1;
589        } else {
590            b.swap(k, k - 1);
591            let (m, nn) = gram_schmidt_f64(&b);
592            mu = m;
593            norm = nn;
594            k = if k >= 2 { k - 1 } else { 1 };
595        }
596    }
597    b
598}
599
600#[cfg(test)]
601#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/lattice/tests.rs"]
602mod tests;