composite_modulus_proofs 0.1.0

//! Legendre symbol and Jacobi symbol for primes and composites

use crate::math::misc;
use core::{
    fmt,
    ops::{Mul, Shr, Sub},
};
use crypto_bigint::{
    modular::{MontyForm, MontyParams},
    Concat, Integer, Odd, Split, Uint,
};

/// Jacobi symbol `(a|n)` for a composite `n`. Taken from https://en.wikipedia.org/wiki/Jacobi_symbol
pub fn jacobi_symbol<const LIMBS: usize>(
    mut a: Uint<LIMBS>,
    mut n: Odd<Uint<LIMBS>>,
) -> JacobiSymbol {
    // Rule 2
    a = a.rem(n.as_nz_ref());
    let mut t = 1;
    while a != Uint::<LIMBS>::ZERO {
        // Rule 9
        while a.is_even().into() {
            a = a.shr(1);
            if misc::is_3_mod_8(&n) || misc::is_5_mod_8(&n) {
                t = -t;
            }
        }
        // Rule 6
        (a, n) = {
            let temp = n.get();
            (temp, a.to_odd().unwrap())
        };
        if misc::is_3_mod_4(&n) && misc::is_3_mod_4(&a) {
            t = -t;
        }
        // Rule 2
        a = a.rem(n.as_nz_ref());
    }
    if n.as_ref() == &Uint::<LIMBS>::ONE {
        t.try_into().unwrap()
    } else {
        JacobiSymbol::Zero
    }
}

/// Same as `jacobi_symbol` but variable time in both `a` and `n`.
pub fn jacobi_symbol_vartime<const LIMBS: usize>(
    mut a: Uint<LIMBS>,
    mut n: Odd<Uint<LIMBS>>,
) -> JacobiSymbol {
    // Rule 2
    a = a.rem_vartime(n.as_nz_ref());
    let mut t = 1;
    while a != Uint::<LIMBS>::ZERO {
        // Rule 9
        while a.is_even().into() {
            a = a.shr_vartime(1);
            if misc::is_3_mod_8(&n) || misc::is_5_mod_8(&n) {
                t = -t;
            }
        }
        // Rule 6
        (a, n) = {
            let temp = n.get();
            (temp, a.to_odd().unwrap())
        };
        if misc::is_3_mod_4(&n) && misc::is_3_mod_4(&a) {
            t = -t;
        }
        // Rule 2
        a = a.rem_vartime(n.as_nz_ref());
    }
    if n.as_ref() == &Uint::<LIMBS>::ONE {
        t.try_into().unwrap()
    } else {
        JacobiSymbol::Zero
    }
}

/// Legendre symbol `(a|p)` for a prime `p`. For primes, Jacobi and Legendre symbol are the same.
/// Calculated using Euler's criterion
pub fn legendre_symbol<const LIMBS: usize, const WIDE_LIMBS: usize>(
    a: &Uint<LIMBS>,
    p: Odd<Uint<LIMBS>>,
) -> JacobiSymbol
where
    Uint<LIMBS>: Concat<Output = Uint<WIDE_LIMBS>>,
    Uint<WIDE_LIMBS>: Split<Output = Uint<LIMBS>>,
{
    let params = MontyParams::new(p);
    legendre_symbol_given_mont_params(a, params)
}

/// Same as `legendre_symbol` but takes Montgomery params for reducing mod `p`
pub fn legendre_symbol_given_mont_params<const LIMBS: usize>(
    a: &Uint<LIMBS>,
    p_mtg: MontyParams<LIMBS>,
) -> JacobiSymbol {
    // exp = (p-1)/2
    let p_minus_1 = p_mtg.modulus().sub(Uint::<LIMBS>::ONE);
    let exp = p_minus_1.shr(1);
    // b = a^{(p-1)/2} mod p
    let b = MontyForm::new(&a, p_mtg).pow(&exp).retrieve();
    if b == Uint::<LIMBS>::ONE {
        JacobiSymbol::One
    } else if b == p_minus_1 {
        JacobiSymbol::MinusOne
    } else {
        JacobiSymbol::Zero
    }
}

/// Jacobi symbol `(a|n)` for a composite `n=p*q` when the prime factors `p` and `q` are known.
/// Uses multiplicative property of Jacobi symbol
pub fn jacobi_symbol_using_primes<const LIMBS: usize, const WIDE_LIMBS: usize>(
    a: &Uint<WIDE_LIMBS>,
    p: Odd<Uint<LIMBS>>,
    q: Odd<Uint<LIMBS>>,
) -> JacobiSymbol
where
    Uint<LIMBS>: Concat<Output = Uint<WIDE_LIMBS>>,
    Uint<WIDE_LIMBS>: Split<Output = Uint<LIMBS>>,
{
    let a_mod_p = a.rem(&p.resize().to_nz().unwrap()).resize();
    let a_mod_q = a.rem(&q.resize().to_nz().unwrap()).resize();
    let a_p = legendre_symbol(&a_mod_p, p);
    let a_q = legendre_symbol(&a_mod_q, q);
    a_p * a_q
}

/// Same as `jacobi_symbol_using_primes` but uses Montgomery params
pub fn jacobi_symbol_using_primes_as_mtg_params<const LIMBS: usize, const WIDE_LIMBS: usize>(
    a: &Uint<WIDE_LIMBS>,
    p: MontyParams<LIMBS>,
    q: MontyParams<LIMBS>,
) -> JacobiSymbol
where
    Uint<LIMBS>: Concat<Output = Uint<WIDE_LIMBS>>,
    Uint<WIDE_LIMBS>: Split<Output = Uint<LIMBS>>,
{
    let a_mod_p = a.rem(&p.modulus().resize().to_nz().unwrap()).resize();
    let a_mod_q = a.rem(&q.modulus().resize().to_nz().unwrap()).resize();
    let a_p = legendre_symbol_given_mont_params(&a_mod_p, p);
    let a_q = legendre_symbol_given_mont_params(&a_mod_q, q);
    a_p * a_q
}

/// The Jacobi symbol `(a|n)` https://en.wikipedia.org/wiki/Jacobi_symbol. Its 1 if `a` is a quadratic
/// residue mod `n` and -1 if it's not but it being 1 doesn't guarantee a quadratic residue unless `n` is prime.
/// When `n` is prime, it's also the Legendre symbol. Its 0 if when `gcd(a, n) > 1`
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum JacobiSymbol {
    Zero,
    One,
    MinusOne,
}

impl fmt::Display for JacobiSymbol {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            JacobiSymbol::Zero => write!(f, "0"),
            JacobiSymbol::One => write!(f, "1"),
            JacobiSymbol::MinusOne => write!(f, "-1"),
        }
    }
}

impl TryFrom<i8> for JacobiSymbol {
    type Error = ();

    fn try_from(value: i8) -> Result<Self, Self::Error> {
        match value {
            0 => Ok(JacobiSymbol::Zero),
            1 => Ok(JacobiSymbol::One),
            -1 => Ok(JacobiSymbol::MinusOne),
            _ => Err(()),
        }
    }
}

impl JacobiSymbol {
    pub fn is_one(&self) -> bool {
        match *self {
            JacobiSymbol::One => true,
            _ => false,
        }
    }

    pub fn is_minus_one(&self) -> bool {
        match *self {
            JacobiSymbol::MinusOne => true,
            _ => false,
        }
    }

    pub fn is_zero(&self) -> bool {
        match *self {
            JacobiSymbol::Zero => true,
            _ => false,
        }
    }
}

impl Mul for JacobiSymbol {
    type Output = Self;

    fn mul(self, rhs: Self) -> Self::Output {
        // From product rules of Jacobi symbol
        match (self, rhs) {
            (JacobiSymbol::One, JacobiSymbol::One) => JacobiSymbol::One,
            (JacobiSymbol::MinusOne, JacobiSymbol::One) => JacobiSymbol::MinusOne,
            (JacobiSymbol::One, JacobiSymbol::MinusOne) => JacobiSymbol::MinusOne,
            (JacobiSymbol::MinusOne, JacobiSymbol::MinusOne) => JacobiSymbol::One,
            _ => JacobiSymbol::Zero,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::util::{get_1024_bit_primes, get_2048_bit_primes, get_coprime};
    use crypto_bigint::{Random, U1024, U128, U2048, U256, U512, U64};
    use crypto_primes::generate_prime_with_rng;
    use rand_core::OsRng;

    #[test]
    fn check_jacobi() {
        let mut rng = OsRng::default();
        assert_eq!(
            jacobi_symbol(U64::from(2_u32), U64::from(21_u32).to_odd().unwrap()),
            JacobiSymbol::MinusOne
        );
        assert_eq!(
            jacobi_symbol(U64::from(6_u32), U64::from(55_u32).to_odd().unwrap()),
            JacobiSymbol::MinusOne
        );
        assert_eq!(
            jacobi_symbol(U64::from(7_u32), U64::from(55_u32).to_odd().unwrap()),
            JacobiSymbol::One
        );
        assert_eq!(
            jacobi_symbol(U64::from(8_u32), U64::from(55_u32).to_odd().unwrap()),
            JacobiSymbol::One
        );
        assert_eq!(
            jacobi_symbol(U64::from(50_u32), U64::from(133_u32).to_odd().unwrap()),
            JacobiSymbol::MinusOne
        );
        assert_eq!(
            jacobi_symbol(U64::from(93_u32), U64::from(133_u32).to_odd().unwrap()),
            JacobiSymbol::One
        );
        assert_eq!(
            jacobi_symbol(U64::from(91_u32), U64::from(133_u32).to_odd().unwrap()),
            JacobiSymbol::Zero
        );

        let a = U128::from(659456_u128); // Obtained from x = 2^70
        assert_eq!(
            jacobi_symbol(
                a,
                Odd::new(U128::from_be_hex("ffffffffffffffffffffffffffffff5f")).unwrap()
            ),
            JacobiSymbol::One
        );

        // -2^31
        let a = U128::from(2147483648_u128);
        assert_eq!(
            jacobi_symbol(
                a,
                Odd::new(U128::from_be_hex("000000007ffffffeffffffe28000003b")).unwrap()
            ),
            JacobiSymbol::MinusOne
        );

        macro_rules! check_given_primes {
            ( $num_iters:expr, $prime_type:ident, $p:ident, $q:ident ) => {
                let n = $p.widening_mul(&$q).to_odd().unwrap();
                let p_mtg = MontyParams::new($p);
                let q_mtg = MontyParams::new($q);
                for _ in 0..$num_iters {
                    let a = get_coprime(&mut rng, &n, &n.to_nz().unwrap());
                    let j = jacobi_symbol(a, n);
                    let j1 = jacobi_symbol_vartime(a, n);
                    let j2 = jacobi_symbol_using_primes(&a, $p, $q);
                    let j3 = jacobi_symbol_using_primes_as_mtg_params(&a, p_mtg, q_mtg);
                    assert_eq!(j, j2, "{} {} {} {} {}", a, $p, $q, j, j2);
                    assert_eq!(j1, j2, "{} {} {} {} {}", a, $p, $q, j1, j2);
                    assert_eq!(j3, j2, "{} {} {} {} {}", a, $p, $q, j3, j2);
                    assert_ne!(j, JacobiSymbol::Zero);
                }
                for _ in 0..10 {
                    // Now gcd(a, n) > 1
                    let a = $prime_type::random(&mut rng).widening_mul(&$p);
                    let j = jacobi_symbol(a, n);
                    let j1 = jacobi_symbol_vartime(a, n);
                    let j2 = jacobi_symbol_using_primes(&a, $p, $q);
                    let j3 = jacobi_symbol_using_primes_as_mtg_params(&a, p_mtg, q_mtg);
                    assert_eq!(j, j2, "{} {} {} {} {}", a, $p, $q, j, j2);
                    assert_eq!(j1, j2, "{} {} {} {} {}", a, $p, $q, j1, j2);
                    assert_eq!(j3, j2, "{} {} {} {} {}", a, $p, $q, j3, j2);
                    assert_eq!(j, JacobiSymbol::Zero);
                }
            };
        }

        macro_rules! check {
            ( $num_iters:expr, $prime_type:ident ) => {
                let p: $prime_type = generate_prime_with_rng(&mut rng, $prime_type::BITS);
                let q: $prime_type = generate_prime_with_rng(&mut rng, $prime_type::BITS);
                let p = p.to_odd().unwrap();
                let q = q.to_odd().unwrap();
                check_given_primes!($num_iters, $prime_type, p, q);
            };
        }
        check!(1000, U128);
        check!(1000, U256);
        check!(100, U512);

        let (p, q) = get_1024_bit_primes();
        check_given_primes!(100, U1024, p, q);

        let (p, q) = get_2048_bit_primes();
        check_given_primes!(100, U2048, p, q);
    }
}