1use 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
30fn dot(a: &[Rational], b: &[Rational]) -> Rational {
32 a.iter().zip(b).fold(zero(), |s, (x, y)| s.add(&x.mul(y)))
33}
34
35fn 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
57fn 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 for j in (0..k).rev() {
72 if mu[k][j].abs() > half {
73 let q = mu[k][j].round(); 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 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
102pub 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
118fn 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
129fn 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
178const 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 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 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
353fn 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])); 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
384pub 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
433fn 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
497pub 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()]; 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
554pub 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; 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;