// return two solutions (x1, x2) for Quadratic Residue problem x^2 = a (mod p), where p is an odd prime
// if a is Quadratic Nonresidues, return None
return two solutions (x1, x2) for Quadratic Residue problem x^2 = a (mod p), where p is an odd prime
if a is Quadratic Nonresidues, return None
return two solutions ( x1 x2 ) for Quadratic Residue problem x^2 = a ( mod p ) where p is an odd prime if a is Quadratic Nonresidues return None
pub fn cipolla(a: u32, p: u32, seed: Option<u64>) -> Option<(u32, u32)> {
    // The params should be kept in u32 range for multiplication overflow issue
    // But inside we use u64 for convenience
    let a = a as u64;
    let p = p as u64;
    if a == 0 {
        return Some((0, 0));
    }
    if !is_residue(a, p) {
        return None;
    }
    let seed = match seed {
        Some(seed) => seed,
        None => SystemTime::now()
            .duration_since(UNIX_EPOCH)
            .unwrap()
            .as_secs(),
    };
    let mut rng = PCG32::new_default(seed);
    let r = loop {
        let r = rng.get_u64() % p;
        if r == 0 || !is_residue((p + r * r - a) % p, p) {
            break r;
        }
    };
    let filed = Rc::new(CustomFiniteFiled::new(p, (p + r * r - a) % p));
    let comp = CustomComplexNumber::new(r, 1, filed);
    let power = (p + 1) >> 1;
    let x0 = CustomComplexNumber::fast_power(comp, power).real as u32;
    let x1 = p as u32 - x0 as u32;
    if x0 < x1 {
        Some((x0, x1))
    } else {
        Some((x1, x0))
    }
}
pub fn cipolla ( a : u32 , p : u32 , seed : Option < u64 > ) -> Option < ( u32 , u32 ) > { // The params should be kept in u32 range for multiplication overflow issue // But inside we use u64 for convenience let a = a as u64 ; let p = p as u64 ; if a == 0 { return Some ( ( 0 , 0 ) ) ; } if ! is_residue ( a , p ) { return None ; } let seed = match seed { Some ( seed ) => seed , None => SystemTime :: now ( ) . duration_since ( UNIX_EPOCH ) . unwrap ( ) . as_secs ( ) , } ; let mut rng = PCG32 :: new_default ( seed ) ; let r = loop { let r = rng . get_u64 ( ) % p ; if r == 0 || ! is_residue ( ( p + r * r - a ) % p , p ) { break r ; } } ; let filed = Rc :: new ( CustomFiniteFiled :: new ( p , ( p + r * r - a ) % p ) ) ; let comp = CustomComplexNumber :: new ( r , 1 , filed ) ; let power = ( p + 1 ) >> 1 ; let x0 = CustomComplexNumber :: fast_power ( comp , power ) . real as u32 ; let x1 = p as u32 - x0 as u32 ; if x0 < x1 { Some ( ( x0 , x1 ) ) } else { Some ( ( x1 , x0 ) ) } }
return two solutions (x1, x2) for Quadratic Residue problem x^2 = a (mod p), where p is an odd prime
if a is Quadratic Nonresidues, return None
return two solutions ( x1 x2 ) for Quadratic Residue problem x^2 = a ( mod p ) where p is an odd prime if a is Quadratic Nonresidues return None
a
u32
p
u32
seed
Option<u64>