openvm_pairing_guest/halo2curves_shims/
naf.rs

1use alloc::vec::Vec;
2
3use num_bigint::BigUint;
4use num_traits::{One, ToPrimitive, Zero};
5
6/// Convert a positive integer into a Non-Adjacent Form (NAF) digit vector (LSB-first).
7pub fn biguint_to_naf(n: &BigUint) -> Vec<i8> {
8    if n.is_zero() {
9        return Vec::new();
10    }
11
12    let mut k = n.clone();
13    let one = BigUint::one();
14    let three = &one + &one + &one;
15    let mut naf = Vec::new();
16
17    while !k.is_zero() {
18        if (&k & &one) == one {
19            let rem = (&k & &three).to_u8().unwrap();
20            let digit = 2i8 - rem as i8;
21            naf.push(if digit == 2 { -1 } else { digit });
22            if *naf.last().unwrap() > 0 {
23                k -= &one;
24            } else {
25                k += &one;
26            }
27        } else {
28            naf.push(0);
29        }
30        k >>= 1usize;
31    }
32    naf
33}