Skip to content

Sqrt does not work properly for fields F_p where p = 5 mod 8 #1030

@juja256

Description

@juja256

Sqrt computation hangs forever for custom fields where p = 5 mod 8 in the current version of ark_ff

Minimum reproducible example:

use ark_ff::{fields::{Fp256, MontBackend, MontConfig}, BigInteger, Field, PrimeField};

// custom field with p = 5 mod 8
#[derive(MontConfig)]
#[modulus = "7237005577332262213973186563042994240857116359379907606001950938285454250989"]
#[generator = "5"]
pub struct FqConfig;
pub type Fq = Fp256<MontBackend<FqConfig, 4>>;

// this code just runs infinitely
#[test]
fn test_sqrt() {
    for i in 0..10000 {
        let a = Fq::from(i);
        let b = a * a;
        let c = b.sqrt().unwrap();
        assert!(c == a || c == -a);
    }
}

We have already proposed a solution in PR for this fields.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions