use malachite_base::num::arithmetic::kronecker_symbol::{
jacobi_symbol_unsigned_double_fast_2, jacobi_symbol_unsigned_simple,
};
use malachite_base::num::arithmetic::traits::{ModPowerOf2, UnsignedAbs};
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::basic::signeds::PrimitiveSigned;
use malachite_base::num::basic::unsigneds::PrimitiveUnsigned;
use malachite_base::num::comparison::traits::PartialOrdAbs;
use malachite_base::num::conversion::traits::{HasHalf, JoinHalves, WrappingFrom};
use malachite_base::test_util::generators::{
signed_gen, signed_gen_var_13, signed_pair_gen, signed_pair_gen_var_10, signed_pair_gen_var_8,
signed_pair_gen_var_9, signed_triple_gen, signed_triple_gen_var_6, signed_triple_gen_var_7,
unsigned_gen, unsigned_gen_var_22, unsigned_pair_gen_var_27, unsigned_pair_gen_var_40,
unsigned_pair_gen_var_41, unsigned_pair_gen_var_42, unsigned_quadruple_gen_var_12,
unsigned_triple_gen_var_19, unsigned_triple_gen_var_22, unsigned_triple_gen_var_23,
};
use malachite_base::test_util::num::arithmetic::kronecker_symbol::{
jacobi_symbol_unsigned_double_fast_1, jacobi_symbol_unsigned_double_simple,
jacobi_symbol_unsigned_fast_1, jacobi_symbol_unsigned_fast_2_1,
jacobi_symbol_unsigned_fast_2_2, jacobi_symbol_unsigned_fast_2_3,
jacobi_symbol_unsigned_fast_2_4,
};
use std::panic::catch_unwind;
#[test]
fn test_jacobi_symbol() {
fn test_u<T: PrimitiveUnsigned>(a: T, n: T, s: i8) {
assert_eq!(a.legendre_symbol(n), s);
assert_eq!(a.jacobi_symbol(n), s);
assert_eq!(a.kronecker_symbol(n), s);
assert_eq!(jacobi_symbol_unsigned_simple(a, n), s);
assert_eq!(jacobi_symbol_unsigned_fast_1(a, n), s);
assert_eq!(jacobi_symbol_unsigned_fast_2_1(a, n), s);
assert_eq!(jacobi_symbol_unsigned_fast_2_2(a, n), s);
assert_eq!(jacobi_symbol_unsigned_fast_2_3(a, n), s);
assert_eq!(jacobi_symbol_unsigned_fast_2_4(a, n), s);
}
test_u::<u8>(0, 1, 1);
test_u::<u8>(0, 3, 0);
test_u::<u8>(1, 3, 1);
test_u::<u8>(2, 3, -1);
test_u::<u8>(0, 5, 0);
test_u::<u8>(1, 5, 1);
test_u::<u8>(2, 5, -1);
test_u::<u8>(3, 5, -1);
test_u::<u8>(4, 5, 1);
test_u::<u8>(0, 7, 0);
test_u::<u8>(1, 7, 1);
test_u::<u8>(2, 7, 1);
test_u::<u8>(3, 7, -1);
test_u::<u8>(4, 7, 1);
test_u::<u8>(5, 7, -1);
test_u::<u8>(6, 7, -1);
test_u::<u8>(0, 9, 0);
test_u::<u8>(1, 9, 1);
test_u::<u8>(2, 9, 1);
test_u::<u8>(3, 9, 0);
test_u::<u8>(4, 9, 1);
test_u::<u8>(5, 9, 1);
test_u::<u8>(6, 9, 0);
test_u::<u8>(7, 9, 1);
test_u::<u8>(8, 9, 1);
test_u::<u8>(7, 7, 0);
test_u::<u8>(8, 7, 1);
test_u::<u8>(9, 7, 1);
test_u::<u8>(10, 7, -1);
test_u::<u8>(11, 7, 1);
test_u::<u8>(12, 7, -1);
test_u::<u8>(13, 7, -1);
test_u::<u8>(9, 9, 0);
test_u::<u8>(10, 9, 1);
test_u::<u8>(11, 9, 1);
test_u::<u8>(12, 9, 0);
test_u::<u8>(13, 9, 1);
test_u::<u8>(14, 9, 1);
test_u::<u8>(15, 9, 0);
test_u::<u8>(16, 9, 1);
test_u::<u8>(17, 9, 1);
test_u::<u16>(1001, 9907, -1);
test_u::<u16>(10908, 9907, -1);
fn test_s<U: PrimitiveUnsigned, S: ModPowerOf2<Output = U> + PrimitiveSigned>(
a: S,
n: S,
s: i8,
) {
assert_eq!(a.legendre_symbol(n), s);
assert_eq!(a.jacobi_symbol(n), s);
assert_eq!(a.kronecker_symbol(n), s);
}
test_s::<u8, i8>(0, 1, 1);
test_s::<u8, i8>(0, 3, 0);
test_s::<u8, i8>(1, 3, 1);
test_s::<u8, i8>(2, 3, -1);
test_s::<u8, i8>(0, 5, 0);
test_s::<u8, i8>(1, 5, 1);
test_s::<u8, i8>(2, 5, -1);
test_s::<u8, i8>(3, 5, -1);
test_s::<u8, i8>(4, 5, 1);
test_s::<u8, i8>(0, 7, 0);
test_s::<u8, i8>(1, 7, 1);
test_s::<u8, i8>(2, 7, 1);
test_s::<u8, i8>(3, 7, -1);
test_s::<u8, i8>(4, 7, 1);
test_s::<u8, i8>(5, 7, -1);
test_s::<u8, i8>(6, 7, -1);
test_s::<u8, i8>(0, 9, 0);
test_s::<u8, i8>(1, 9, 1);
test_s::<u8, i8>(2, 9, 1);
test_s::<u8, i8>(3, 9, 0);
test_s::<u8, i8>(4, 9, 1);
test_s::<u8, i8>(5, 9, 1);
test_s::<u8, i8>(6, 9, 0);
test_s::<u8, i8>(7, 9, 1);
test_s::<u8, i8>(8, 9, 1);
test_s::<u8, i8>(7, 7, 0);
test_s::<u8, i8>(8, 7, 1);
test_s::<u8, i8>(9, 7, 1);
test_s::<u8, i8>(10, 7, -1);
test_s::<u8, i8>(11, 7, 1);
test_s::<u8, i8>(12, 7, -1);
test_s::<u8, i8>(13, 7, -1);
test_s::<u8, i8>(9, 9, 0);
test_s::<u8, i8>(10, 9, 1);
test_s::<u8, i8>(11, 9, 1);
test_s::<u8, i8>(12, 9, 0);
test_s::<u8, i8>(13, 9, 1);
test_s::<u8, i8>(14, 9, 1);
test_s::<u8, i8>(15, 9, 0);
test_s::<u8, i8>(16, 9, 1);
test_s::<u8, i8>(17, 9, 1);
test_s::<u8, i8>(-7, 7, 0);
test_s::<u8, i8>(-6, 7, 1);
test_s::<u8, i8>(-5, 7, 1);
test_s::<u8, i8>(-4, 7, -1);
test_s::<u8, i8>(-3, 7, 1);
test_s::<u8, i8>(-2, 7, -1);
test_s::<u8, i8>(-1, 7, -1);
test_s::<u8, i8>(-9, 9, 0);
test_s::<u8, i8>(-8, 9, 1);
test_s::<u8, i8>(-7, 9, 1);
test_s::<u8, i8>(-6, 9, 0);
test_s::<u8, i8>(-5, 9, 1);
test_s::<u8, i8>(-4, 9, 1);
test_s::<u8, i8>(-3, 9, 0);
test_s::<u8, i8>(-2, 9, 1);
test_s::<u8, i8>(-1, 9, 1);
test_s::<u16, i16>(1001, 9907, -1);
test_s::<u16, i16>(10908, 9907, -1);
test_s::<u16, i16>(-8906, 9907, -1);
}
fn jacobi_symbol_fail_helper<T: PrimitiveInt>() {
assert_panic!(T::ONE.jacobi_symbol(T::TWO));
}
fn jacobi_symbol_fail_helper_signed<T: PrimitiveSigned>() {
assert_panic!(T::ONE.jacobi_symbol(T::NEGATIVE_ONE));
}
#[test]
fn jacobi_symbol_fail() {
apply_fn_to_primitive_ints!(jacobi_symbol_fail_helper);
apply_fn_to_signeds!(jacobi_symbol_fail_helper_signed);
}
#[test]
fn test_jacobi_symbol_unsigned_double() {
fn test<T: PrimitiveUnsigned, D: HasHalf<Half = T> + JoinHalves + PrimitiveUnsigned>(
x_1: T,
x_0: T,
y_1: T,
y_0: T,
s: i8,
) {
assert_eq!(
jacobi_symbol_unsigned_double_simple::<T, D>(x_1, x_0, y_1, y_0),
s
);
assert_eq!(jacobi_symbol_unsigned_double_fast_1(x_1, x_0, y_1, y_0), s);
assert_eq!(jacobi_symbol_unsigned_double_fast_2(x_1, x_0, y_1, y_0), s);
}
test::<u64, u128>(0, 0, 0, 1, 1);
test::<u64, u128>(0, 3, 2, 3, 1);
test::<u64, u128>(0, 0, 0, 3, 0);
test::<u64, u128>(0, 1, 1, 1, 1);
test::<u64, u128>(0, 1, 1, 3, 1);
test::<u64, u128>(1, 0, 0, 3, 1);
test::<u64, u128>(1, 1, 0, 3, -1);
test::<u64, u128>(1, 1, 1, 1, 0);
test::<u64, u128>(0, 1, 2, 1, 1);
test::<u64, u128>(1, 1, 2, 1, 1);
test::<u64, u128>(2, 1, 0, 3, 0);
test::<u64, u128>(2, 1, 2, 1, 0);
test::<u8, u16>(242, 128, 173, 173, -1);
test::<u8, u16>(0, 1, 0, 3, 1);
test::<u8, u16>(1, 1, 1, 3, 1);
test::<u8, u16>(1, 1, 1, 7, -1);
test::<u8, u16>(1, 1, 2, 3, 1);
test::<u8, u16>(2, 1, 1, 1, 1);
test::<u8, u16>(2, 1, 1, 3, -1);
test::<u8, u16>(3, 0, 0, 3, 0);
}
#[test]
fn test_kronecker_symbol() {
fn test_u<T: PrimitiveUnsigned>(a: T, n: T, s: i8) {
assert_eq!(a.kronecker_symbol(n), s);
}
test_u::<u8>(0, 2, 0);
test_u::<u8>(1, 2, 1);
test_u::<u8>(2, 2, 0);
test_u::<u8>(3, 2, -1);
test_u::<u8>(4, 2, 0);
test_u::<u8>(5, 2, -1);
test_u::<u8>(6, 2, 0);
test_u::<u8>(7, 2, 1);
test_u::<u8>(0, 4, 0);
test_u::<u8>(1, 4, 1);
test_u::<u8>(2, 4, 0);
test_u::<u8>(3, 4, 1);
test_u::<u8>(0, 6, 0);
test_u::<u8>(1, 6, 1);
test_u::<u8>(2, 6, 0);
test_u::<u8>(3, 6, 0);
test_u::<u8>(4, 6, 0);
test_u::<u8>(5, 6, 1);
test_u::<u8>(6, 6, 0);
test_u::<u8>(7, 6, 1);
test_u::<u8>(8, 6, 0);
test_u::<u8>(9, 6, 0);
test_u::<u8>(10, 6, 0);
test_u::<u8>(11, 6, 1);
test_u::<u8>(12, 6, 0);
test_u::<u8>(13, 6, -1);
test_u::<u8>(14, 6, 0);
test_u::<u8>(15, 6, 0);
test_u::<u8>(16, 6, 0);
test_u::<u8>(17, 6, -1);
test_u::<u8>(18, 6, 0);
test_u::<u8>(19, 6, -1);
test_u::<u8>(20, 6, 0);
test_u::<u8>(21, 6, 0);
test_u::<u8>(22, 6, 0);
test_u::<u8>(23, 6, -1);
test_u::<u16>(1001, 9908, -1);
test_u::<u16>(10909, 9908, -1);
fn test_s<U: PrimitiveUnsigned, S: ModPowerOf2<Output = U> + PrimitiveSigned>(
a: S,
n: S,
s: i8,
) {
assert_eq!(a.kronecker_symbol(n), s);
}
test_s::<u8, i8>(0, 2, 0);
test_s::<u8, i8>(1, 2, 1);
test_s::<u8, i8>(2, 2, 0);
test_s::<u8, i8>(3, 2, -1);
test_s::<u8, i8>(4, 2, 0);
test_s::<u8, i8>(5, 2, -1);
test_s::<u8, i8>(6, 2, 0);
test_s::<u8, i8>(7, 2, 1);
test_s::<u8, i8>(0, 4, 0);
test_s::<u8, i8>(1, 4, 1);
test_s::<u8, i8>(2, 4, 0);
test_s::<u8, i8>(3, 4, 1);
test_s::<u8, i8>(0, 6, 0);
test_s::<u8, i8>(1, 6, 1);
test_s::<u8, i8>(2, 6, 0);
test_s::<u8, i8>(3, 6, 0);
test_s::<u8, i8>(4, 6, 0);
test_s::<u8, i8>(5, 6, 1);
test_s::<u8, i8>(6, 6, 0);
test_s::<u8, i8>(7, 6, 1);
test_s::<u8, i8>(8, 6, 0);
test_s::<u8, i8>(9, 6, 0);
test_s::<u8, i8>(10, 6, 0);
test_s::<u8, i8>(11, 6, 1);
test_s::<u8, i8>(12, 6, 0);
test_s::<u8, i8>(13, 6, -1);
test_s::<u8, i8>(14, 6, 0);
test_s::<u8, i8>(15, 6, 0);
test_s::<u8, i8>(16, 6, 0);
test_s::<u8, i8>(17, 6, -1);
test_s::<u8, i8>(18, 6, 0);
test_s::<u8, i8>(19, 6, -1);
test_s::<u8, i8>(20, 6, 0);
test_s::<u8, i8>(21, 6, 0);
test_s::<u8, i8>(22, 6, 0);
test_s::<u8, i8>(23, 6, -1);
test_s::<u8, i8>(-1, 2, 1);
test_s::<u8, i8>(-2, 2, 0);
test_s::<u8, i8>(-3, 2, -1);
test_s::<u8, i8>(-4, 2, 0);
test_s::<u8, i8>(-5, 2, -1);
test_s::<u8, i8>(-6, 2, 0);
test_s::<u8, i8>(-7, 2, 1);
test_s::<u8, i8>(-1, 4, 1);
test_s::<u8, i8>(-2, 4, 0);
test_s::<u8, i8>(-3, 4, 1);
test_s::<u8, i8>(-1, 6, -1);
test_s::<u8, i8>(-2, 6, 0);
test_s::<u8, i8>(-3, 6, 0);
test_s::<u8, i8>(-4, 6, 0);
test_s::<u8, i8>(-5, 6, -1);
test_s::<u8, i8>(-6, 6, 0);
test_s::<u8, i8>(-7, 6, -1);
test_s::<u8, i8>(-8, 6, 0);
test_s::<u8, i8>(-9, 6, 0);
test_s::<u8, i8>(-10, 6, 0);
test_s::<u8, i8>(-11, 6, -1);
test_s::<u8, i8>(-12, 6, 0);
test_s::<u8, i8>(-13, 6, 1);
test_s::<u8, i8>(-14, 6, 0);
test_s::<u8, i8>(-15, 6, 0);
test_s::<u8, i8>(-16, 6, 0);
test_s::<u8, i8>(-17, 6, 1);
test_s::<u8, i8>(-18, 6, 0);
test_s::<u8, i8>(-19, 6, 1);
test_s::<u8, i8>(-20, 6, 0);
test_s::<u8, i8>(-21, 6, 0);
test_s::<u8, i8>(-22, 6, 0);
test_s::<u8, i8>(-23, 6, 1);
test_s::<u8, i8>(0, -2, 0);
test_s::<u8, i8>(1, -2, 1);
test_s::<u8, i8>(2, -2, 0);
test_s::<u8, i8>(3, -2, -1);
test_s::<u8, i8>(4, -2, 0);
test_s::<u8, i8>(5, -2, -1);
test_s::<u8, i8>(6, -2, 0);
test_s::<u8, i8>(7, -2, 1);
test_s::<u8, i8>(0, -4, 0);
test_s::<u8, i8>(1, -4, 1);
test_s::<u8, i8>(2, -4, 0);
test_s::<u8, i8>(3, -4, 1);
test_s::<u8, i8>(0, -6, 0);
test_s::<u8, i8>(1, -6, 1);
test_s::<u8, i8>(2, -6, 0);
test_s::<u8, i8>(3, -6, 0);
test_s::<u8, i8>(4, -6, 0);
test_s::<u8, i8>(5, -6, 1);
test_s::<u8, i8>(6, -6, 0);
test_s::<u8, i8>(7, -6, 1);
test_s::<u8, i8>(8, -6, 0);
test_s::<u8, i8>(9, -6, 0);
test_s::<u8, i8>(10, -6, 0);
test_s::<u8, i8>(11, -6, 1);
test_s::<u8, i8>(12, -6, 0);
test_s::<u8, i8>(13, -6, -1);
test_s::<u8, i8>(14, -6, 0);
test_s::<u8, i8>(15, -6, 0);
test_s::<u8, i8>(16, -6, 0);
test_s::<u8, i8>(17, -6, -1);
test_s::<u8, i8>(18, -6, 0);
test_s::<u8, i8>(19, -6, -1);
test_s::<u8, i8>(20, -6, 0);
test_s::<u8, i8>(21, -6, 0);
test_s::<u8, i8>(22, -6, 0);
test_s::<u8, i8>(23, -6, -1);
test_s::<u8, i8>(-1, -2, -1);
test_s::<u8, i8>(-2, -2, 0);
test_s::<u8, i8>(-3, -2, 1);
test_s::<u8, i8>(-4, -2, 0);
test_s::<u8, i8>(-5, -2, 1);
test_s::<u8, i8>(-6, -2, 0);
test_s::<u8, i8>(-7, -2, -1);
test_s::<u8, i8>(-1, -4, -1);
test_s::<u8, i8>(-2, -4, 0);
test_s::<u8, i8>(-3, -4, -1);
test_s::<u8, i8>(-1, -6, 1);
test_s::<u8, i8>(-2, -6, 0);
test_s::<u8, i8>(-3, -6, 0);
test_s::<u8, i8>(-4, -6, 0);
test_s::<u8, i8>(-5, -6, 1);
test_s::<u8, i8>(-6, -6, 0);
test_s::<u8, i8>(-7, -6, 1);
test_s::<u8, i8>(-8, -6, 0);
test_s::<u8, i8>(-9, -6, 0);
test_s::<u8, i8>(-10, -6, 0);
test_s::<u8, i8>(-11, -6, 1);
test_s::<u8, i8>(-12, -6, 0);
test_s::<u8, i8>(-13, -6, -1);
test_s::<u8, i8>(-14, -6, 0);
test_s::<u8, i8>(-15, -6, 0);
test_s::<u8, i8>(-16, -6, 0);
test_s::<u8, i8>(-17, -6, -1);
test_s::<u8, i8>(-18, -6, 0);
test_s::<u8, i8>(-19, -6, -1);
test_s::<u8, i8>(-20, -6, 0);
test_s::<u8, i8>(-21, -6, 0);
test_s::<u8, i8>(-22, -6, 0);
test_s::<u8, i8>(-23, -6, -1);
test_s::<u16, i16>(1001, -9908, -1);
test_s::<u16, i16>(10909, -9908, -1);
test_s::<u16, i16>(-8907, -9908, 1);
}
fn jacobi_symbol_properties_helper_unsigned<T: PrimitiveUnsigned>() {
unsigned_pair_gen_var_40::<T>().test_properties(|(a, n)| {
let s = a.jacobi_symbol(n);
assert_eq!(a.legendre_symbol(n), s);
assert_eq!(a.kronecker_symbol(n), s);
assert_eq!(jacobi_symbol_unsigned_simple(a, n), s);
assert_eq!(jacobi_symbol_unsigned_fast_1(a, n), s);
assert_eq!(jacobi_symbol_unsigned_fast_2_1(a, n), s);
assert_eq!(jacobi_symbol_unsigned_fast_2_2(a, n), s);
assert_eq!(jacobi_symbol_unsigned_fast_2_3(a, n), s);
assert_eq!(jacobi_symbol_unsigned_fast_2_4(a, n), s);
assert!(s.le_abs(&1i8));
if let Some(b) = a.checked_add(n) {
assert_eq!(b.jacobi_symbol(n), s);
}
if let Some(b) = a.checked_sub(n) {
assert_eq!(b.jacobi_symbol(n), s);
}
assert_eq!(s != 0, a.coprime_with(n));
if let Some(b) = a.checked_mul(T::TWO) {
let n_mod_8: u8 = n.mod_power_of_2(3).wrapping_into();
assert_eq!(
b.jacobi_symbol(n),
if n_mod_8 == 1 || n_mod_8 == 7 { s } else { -s }
);
}
});
unsigned_pair_gen_var_41::<T>().test_properties(|(m, n)| {
let n_mod_4: u8 = n.mod_power_of_2(2).wrapping_into();
let m_mod_4: u8 = m.mod_power_of_2(2).wrapping_into();
assert_eq!(
m.jacobi_symbol(n) * n.jacobi_symbol(m),
if n_mod_4 == 1 || m_mod_4 == 1 { 1 } else { -1 }
);
});
unsigned_triple_gen_var_22::<T>().test_properties(|(a, b, n)| {
if let Some(c) = a.checked_mul(b) {
assert_eq!(c.jacobi_symbol(n), a.jacobi_symbol(n) * b.jacobi_symbol(n));
}
});
unsigned_triple_gen_var_23::<T>().test_properties(|(a, m, n)| {
if let Some(o) = m.checked_mul(n) {
assert_eq!(a.jacobi_symbol(o), a.jacobi_symbol(m) * a.jacobi_symbol(n));
}
});
unsigned_gen_var_22::<T>().test_properties(|n| {
if n != T::ONE {
assert_eq!(T::ZERO.jacobi_symbol(n), 0);
assert_eq!(n.jacobi_symbol(n), 0);
}
assert_eq!(T::ONE.jacobi_symbol(n), 1);
assert_eq!(n.jacobi_symbol(T::ONE), 1);
let n_mod_4: u8 = n.mod_power_of_2(2).wrapping_into();
assert_eq!(
(n - T::ONE).jacobi_symbol(n),
if n_mod_4 == 1 { 1 } else { -1 }
);
let n_mod_8: u8 = n.mod_power_of_2(3).wrapping_into();
assert_eq!(
T::TWO.jacobi_symbol(n),
if n_mod_8 == 1 || n_mod_8 == 7 { 1 } else { -1 }
);
});
}
fn jacobi_symbol_properties_double_helper_unsigned<
T: PrimitiveUnsigned,
D: HasHalf<Half = T> + JoinHalves + PrimitiveUnsigned,
>() {
unsigned_quadruple_gen_var_12::<T>().test_properties(|(x_1, x_0, y_1, y_0)| {
let s = jacobi_symbol_unsigned_double_simple::<T, D>(x_1, x_0, y_1, y_0);
assert_eq!(jacobi_symbol_unsigned_double_fast_1(x_1, x_0, y_1, y_0), s,);
assert_eq!(jacobi_symbol_unsigned_double_fast_2(x_1, x_0, y_1, y_0), s,);
});
}
fn jacobi_symbol_properties_helper_signed<
U: PrimitiveUnsigned + WrappingFrom<S>,
S: ModPowerOf2<Output = U> + PrimitiveSigned + UnsignedAbs<Output = U> + WrappingFrom<U>,
>() {
signed_pair_gen_var_8::<U, S>().test_properties(|(a, n)| {
let s = a.jacobi_symbol(n);
assert_eq!(a.legendre_symbol(n), s);
assert_eq!(a.kronecker_symbol(n), s);
assert!(s.le_abs(&1i8));
if let Some(b) = a.checked_add(n) {
assert_eq!(b.jacobi_symbol(n), s);
}
if let Some(b) = a.checked_sub(n) {
assert_eq!(b.jacobi_symbol(n), s);
}
assert_eq!(s != 0, a.unsigned_abs().coprime_with(n.unsigned_abs()));
if let Some(b) = a.checked_mul(S::TWO) {
let n_mod_8: u8 = n.mod_power_of_2(3).wrapping_into();
assert_eq!(
b.jacobi_symbol(n),
if n_mod_8 == 1 || n_mod_8 == 7 { s } else { -s }
);
}
if let Some(b) = a.checked_neg() {
let n_mod_4: u8 = n.mod_power_of_2(2).wrapping_into();
assert_eq!(b.jacobi_symbol(n), if n_mod_4 == 1 { s } else { -s });
}
});
signed_pair_gen_var_9::<U, S>().test_properties(|(m, n)| {
let n_mod_4: u8 = n.mod_power_of_2(2).wrapping_into();
let m_mod_4: u8 = m.mod_power_of_2(2).wrapping_into();
assert_eq!(
m.jacobi_symbol(n) * n.jacobi_symbol(m),
if n_mod_4 == 1 || m_mod_4 == 1 { 1 } else { -1 }
);
});
signed_triple_gen_var_6::<U, S>().test_properties(|(a, b, n)| {
if let Some(c) = a.checked_mul(b) {
assert_eq!(c.jacobi_symbol(n), a.jacobi_symbol(n) * b.jacobi_symbol(n));
}
});
signed_triple_gen_var_7::<U, S>().test_properties(|(a, m, n)| {
if let Some(o) = m.checked_mul(n) {
assert_eq!(a.jacobi_symbol(o), a.jacobi_symbol(m) * a.jacobi_symbol(n));
}
});
signed_gen_var_13::<U, S>().test_properties(|n| {
if n != S::ONE {
assert_eq!(S::ZERO.jacobi_symbol(n), 0);
assert_eq!(n.jacobi_symbol(n), 0);
}
assert_eq!(S::ONE.jacobi_symbol(n), 1);
assert_eq!(n.jacobi_symbol(S::ONE), 1);
let n_mod_4: u8 = n.mod_power_of_2(2).wrapping_into();
assert_eq!(
S::NEGATIVE_ONE.jacobi_symbol(n),
if n_mod_4 == 1 { 1 } else { -1 }
);
let n_mod_8: u8 = n.mod_power_of_2(3).wrapping_into();
assert_eq!(
S::TWO.jacobi_symbol(n),
if n_mod_8 == 1 || n_mod_8 == 7 { 1 } else { -1 }
);
});
}
#[test]
fn jacobi_symbol_properties() {
apply_fn_to_unsigneds!(jacobi_symbol_properties_helper_unsigned);
jacobi_symbol_properties_double_helper_unsigned::<u8, u16>();
jacobi_symbol_properties_double_helper_unsigned::<u16, u32>();
jacobi_symbol_properties_double_helper_unsigned::<u32, u64>();
jacobi_symbol_properties_double_helper_unsigned::<u64, u128>();
apply_fn_to_unsigned_signed_pairs!(jacobi_symbol_properties_helper_signed);
}
fn kronecker_symbol_properties_helper_unsigned<T: PrimitiveUnsigned>() {
unsigned_pair_gen_var_27::<T>().test_properties(|(a, n)| {
let s = a.kronecker_symbol(n);
assert!(s.le_abs(&1i8));
assert_eq!(s != 0, a.coprime_with(n));
let n_mod_4: u8 = n.mod_power_of_2(2).wrapping_into();
if n_mod_4 == 2 {
if let Some(four_n) = n.checked_mul(T::from(4u8)) {
if let Some(b) = a.checked_add(four_n) {
assert_eq!(b.kronecker_symbol(n), s);
}
if let Some(b) = a.checked_sub(four_n) {
assert_eq!(b.kronecker_symbol(n), s);
}
}
} else {
if let Some(b) = a.checked_add(n) {
assert_eq!(b.kronecker_symbol(n), s);
}
if let Some(b) = a.checked_sub(n) {
assert_eq!(b.kronecker_symbol(n), s);
}
}
let a_mod_4: u8 = a.mod_power_of_2(2).wrapping_into();
if a != T::ZERO && a_mod_4 != 3 {
if a_mod_4 == 2 {
if let Some(four_a) = a.checked_mul(T::from(4u8)) {
if let Some(m) = n.checked_add(four_a) {
assert_eq!(a.kronecker_symbol(m), s);
}
if let Some(m) = n.checked_sub(four_a) {
assert_eq!(a.kronecker_symbol(m), s);
}
}
} else {
if let Some(m) = n.checked_add(a) {
assert_eq!(a.kronecker_symbol(m), s);
}
if let Some(m) = n.checked_sub(a) {
assert_eq!(a.kronecker_symbol(m), s);
}
}
}
});
unsigned_triple_gen_var_19::<T>().test_properties(|(x, y, z)| {
if let Some(p) = x.checked_mul(y) {
assert_eq!(
p.kronecker_symbol(z),
x.kronecker_symbol(z) * y.kronecker_symbol(z)
);
}
if let Some(p) = y.checked_mul(z) {
assert_eq!(
x.kronecker_symbol(p),
x.kronecker_symbol(y) * x.kronecker_symbol(z)
);
}
});
unsigned_pair_gen_var_42::<T>().test_properties(|(m, n)| {
let n_odd = if n == T::ZERO {
T::ONE
} else {
n >> n.trailing_zeros()
};
let m_odd = if m == T::ZERO {
T::ONE
} else {
m >> m.trailing_zeros()
};
let n_odd_mod_4: u8 = n_odd.mod_power_of_2(2).wrapping_into();
let m_odd_mod_4: u8 = m_odd.mod_power_of_2(2).wrapping_into();
let p = if n_odd_mod_4 == 1 || m_odd_mod_4 == 1 {
1
} else {
-1
};
assert_eq!(m.kronecker_symbol(n) * n.kronecker_symbol(m), p);
});
unsigned_gen().test_properties(|n| {
if n != T::ONE {
assert_eq!(T::ZERO.kronecker_symbol(n), 0);
assert_eq!(n.kronecker_symbol(n), 0);
}
assert_eq!(T::ONE.kronecker_symbol(n), 1);
assert_eq!(n.kronecker_symbol(T::ONE), 1);
});
}
fn kronecker_symbol_properties_helper_signed<
U: PrimitiveUnsigned + WrappingFrom<S>,
S: ModPowerOf2<Output = U> + PrimitiveSigned + UnsignedAbs<Output = U> + WrappingFrom<U>,
>() {
signed_pair_gen::<S>().test_properties(|(a, n)| {
let s = a.kronecker_symbol(n);
assert!(s.le_abs(&1i8));
assert_eq!(s != 0, a.unsigned_abs().coprime_with(n.unsigned_abs()));
let n_mod_4: u8 = n.mod_power_of_2(2).wrapping_into();
if n_mod_4 == 2 {
if let Some(four_n) = n.checked_mul(S::from(4i8)) {
if let Some(b) = a.checked_add(four_n) {
if n > S::ZERO || a.sign() == b.sign() {
assert_eq!(b.kronecker_symbol(n), s);
}
}
if let Some(b) = a.checked_sub(four_n) {
if n > S::ZERO || a.sign() == b.sign() {
assert_eq!(b.kronecker_symbol(n), s);
}
}
}
} else {
if let Some(b) = a.checked_add(n) {
if n > S::ZERO || a.sign() == b.sign() {
assert_eq!(b.kronecker_symbol(n), s);
}
}
if let Some(b) = a.checked_sub(n) {
if n > S::ZERO || a.sign() == b.sign() {
assert_eq!(b.kronecker_symbol(n), s);
}
}
}
let a_mod_4: u8 = a.mod_power_of_2(2).wrapping_into();
if a != S::ZERO && a_mod_4 != 3 {
if let Some(abs_a) = a.checked_abs() {
if a_mod_4 == 2 {
if let Some(four_abs_a) = abs_a.checked_mul(S::from(4i8)) {
if let Some(m) = n.checked_add(four_abs_a) {
assert_eq!(a.kronecker_symbol(m), s);
}
if let Some(m) = n.checked_sub(four_abs_a) {
assert_eq!(a.kronecker_symbol(m), s);
}
}
} else {
if let Some(m) = n.checked_add(abs_a) {
assert_eq!(a.kronecker_symbol(m), s);
}
if let Some(m) = n.checked_sub(abs_a) {
assert_eq!(a.kronecker_symbol(m), s);
}
}
}
}
let m = a;
if let Some(m_abs) = m.checked_abs() {
let m_odd = if m == S::ZERO {
S::ONE
} else {
m >> m.trailing_zeros()
};
let m_odd_mod_4: u8 = m_odd.mod_power_of_2(2).wrapping_into();
let m_star = if m_odd_mod_4 == 1 { m } else { -m };
assert_eq!(m_star.kronecker_symbol(n), n.kronecker_symbol(m_abs));
}
});
signed_triple_gen::<S>().test_properties(|(x, y, z)| {
if !(z == S::NEGATIVE_ONE && (x == S::ZERO && y < S::ZERO || x < S::ZERO && y == S::ZERO)) {
if let Some(p) = x.checked_mul(y) {
assert_eq!(
p.kronecker_symbol(z),
x.kronecker_symbol(z) * y.kronecker_symbol(z)
);
}
}
let y_odd_mod_4: u8 = if y == S::ZERO {
0
} else {
(y >> y.trailing_zeros()).mod_power_of_2(2).wrapping_into()
};
let z_odd_mod_4: u8 = if z == S::ZERO {
0
} else {
(z >> z.trailing_zeros()).mod_power_of_2(2).wrapping_into()
};
if !(x == S::NEGATIVE_ONE
&& (y == S::ZERO && z_odd_mod_4 == 3 || y_odd_mod_4 == 3 && z == S::ZERO))
{
if let Some(p) = y.checked_mul(z) {
assert_eq!(
x.kronecker_symbol(p),
x.kronecker_symbol(y) * x.kronecker_symbol(z)
);
}
}
});
signed_pair_gen_var_10::<U, S>().test_properties(|(m, n)| {
let n_odd = if n == S::ZERO {
S::ONE
} else {
n >> n.trailing_zeros()
};
let m_odd = if m == S::ZERO {
S::ONE
} else {
m >> m.trailing_zeros()
};
let n_odd_mod_4: u8 = n_odd.mod_power_of_2(2).wrapping_into();
let m_odd_mod_4: u8 = m_odd.mod_power_of_2(2).wrapping_into();
let p = if n_odd_mod_4 == 1 || m_odd_mod_4 == 1 {
1
} else {
-1
};
assert_eq!(
m.kronecker_symbol(n) * n.kronecker_symbol(m),
if m < S::ZERO && n < S::ZERO { -p } else { p }
);
if let Some(m_abs) = m.checked_abs() {
assert_eq!(m.kronecker_symbol(n) * n.kronecker_symbol(m_abs), p);
}
});
signed_gen().test_properties(|n| {
if n != S::ONE && n != S::NEGATIVE_ONE {
assert_eq!(S::ZERO.kronecker_symbol(n), 0);
assert_eq!(n.kronecker_symbol(n), 0);
}
assert_eq!(S::ONE.kronecker_symbol(n), 1);
assert_eq!(n.kronecker_symbol(S::ONE), 1);
let n_odd = if n == S::ZERO {
S::ONE
} else {
n >> n.trailing_zeros()
};
let n_odd_mod_4: u8 = n_odd.mod_power_of_2(2).wrapping_into();
assert_eq!(
S::NEGATIVE_ONE.kronecker_symbol(n),
if n_odd_mod_4 == 1 { 1 } else { -1 }
);
assert_eq!(
n.kronecker_symbol(S::NEGATIVE_ONE),
if n >= S::ZERO { 1 } else { -1 }
);
});
}
#[test]
fn kronecker_symbol_properties() {
apply_fn_to_unsigneds!(kronecker_symbol_properties_helper_unsigned);
apply_fn_to_unsigned_signed_pairs!(kronecker_symbol_properties_helper_signed);
}