ark_feanor/
prime_field.rs

1//! Prime field specializations that enable division and field operations.
2
3use ark_ff::{Field, PrimeField, BigInteger};
4use feanor_math::divisibility::*;
5use feanor_math::pid::*;
6use crate::field_wrapper::ArkFieldWrapper;
7
8/// Marker trait to indicate that an arkworks field implements PrimeField
9pub trait IsPrimeField: Field {
10    fn field_characteristic() -> num_bigint::BigUint;
11}
12
13impl<F: PrimeField> IsPrimeField for F {
14    fn field_characteristic() -> num_bigint::BigUint {
15        // Convert arkworks BigInt to num_bigint::BigUint
16        let modulus_bytes = F::MODULUS.to_bytes_le();
17        num_bigint::BigUint::from_bytes_le(&modulus_bytes)
18    }
19}
20
21// Implement DivisibilityRing for prime fields (allows division by non-zero elements)
22impl<F: PrimeField> DivisibilityRing for ArkFieldWrapper<F> {
23    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
24        if rhs.is_zero() {
25            None
26        } else {
27            rhs.inverse().map(|inv| *lhs * inv)
28        }
29    }
30
31    fn is_unit(&self, el: &Self::Element) -> bool {
32        !el.is_zero()
33    }
34}
35
36// Implement Domain (no zero divisors)
37impl<F: PrimeField> Domain for ArkFieldWrapper<F> {}
38
39// Implement PrincipalIdealRing (every ideal is principal)
40impl<F: PrimeField> PrincipalIdealRing for ArkFieldWrapper<F> {
41    fn ideal_gen(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element {
42        // In a field, the GCD is either 0 (if both are zero) or 1
43        if lhs.is_zero() && rhs.is_zero() {
44            F::zero()
45        } else {
46            // At least one is non-zero, so GCD is 1
47            F::one()
48        }
49    }
50
51    fn extended_ideal_gen(&self, lhs: &Self::Element, rhs: &Self::Element)
52        -> (Self::Element, Self::Element, Self::Element) {
53        // In a field, the GCD is either 0 (if both are zero) or 1
54        if lhs.is_zero() && rhs.is_zero() {
55            (F::zero(), F::one(), F::zero())
56        } else if lhs.is_zero() {
57            (*rhs, F::zero(), F::one())
58        } else if rhs.is_zero() {
59            (*lhs, F::one(), F::zero())
60        } else {
61            // Both non-zero, GCD is 1
62            // We need to find a, b such that a*lhs + b*rhs = 1
63            // Since we're in a field: 1 = lhs * (1/lhs) + rhs * 0
64            let lhs_inv = lhs.inverse().unwrap();
65            (F::one(), lhs_inv, F::zero())
66        }
67    }
68
69    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
70        self.checked_left_div(lhs, rhs)
71    }
72}
73
74// Implement EuclideanRing
75impl<F: PrimeField> EuclideanRing for ArkFieldWrapper<F> {
76    fn euclidean_div_rem(&self, lhs: Self::Element, rhs: &Self::Element)
77        -> (Self::Element, Self::Element) {
78        if rhs.is_zero() {
79            panic!("Division by zero");
80        }
81        let quotient = lhs * rhs.inverse().unwrap();
82        (quotient, F::zero())
83    }
84
85    fn euclidean_deg(&self, el: &Self::Element) -> Option<usize> {
86        if el.is_zero() {
87            None
88        } else {
89            Some(0)
90        }
91    }
92}
93
94// Finally, implement Field trait from feanor-math
95impl<F: PrimeField> feanor_math::field::Field for ArkFieldWrapper<F> {
96    fn div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element {
97        if rhs.is_zero() {
98            panic!("Division by zero");
99        }
100        *lhs * rhs.inverse().expect("Division by zero")
101    }
102}
103
104// Helper trait to extract field properties
105pub trait FieldProperties {
106    /// Get the characteristic of the field as a BigUint
107    fn field_characteristic_biguint(&self) -> num_bigint::BigUint;
108
109    /// Check if the field is a prime field
110    fn is_prime_field(&self) -> bool;
111
112    /// Get the field size (number of elements)
113    fn field_size(&self) -> num_bigint::BigUint;
114}
115
116impl<F: PrimeField> FieldProperties for ArkFieldWrapper<F> {
117    fn field_characteristic_biguint(&self) -> num_bigint::BigUint {
118        F::field_characteristic()
119    }
120
121    fn is_prime_field(&self) -> bool {
122        true
123    }
124
125    fn field_size(&self) -> num_bigint::BigUint {
126        // For prime fields, size = characteristic
127        self.field_characteristic_biguint()
128    }
129}
130
131#[cfg(test)]
132mod tests {
133    use super::*;
134    use ark_bls12_381::Fr;
135    use feanor_math::ring::RingBase;
136    use feanor_math::field::Field;
137
138    #[test]
139    fn test_division() {
140        let field = ArkFieldWrapper::<Fr>::new();
141        
142        let a = field.from_int(10);
143        let b = field.from_int(5);
144        let c = field.div(&a, &b);
145        let expected = field.from_int(2);
146        assert!(field.eq_el(&c, &expected));
147    }
148
149    #[test]
150    fn test_inverse() {
151        let field = ArkFieldWrapper::<Fr>::new();
152        
153        let a = field.from_int(7);
154        let a_inv = field.checked_left_div(&field.one(), &a).unwrap();
155        let product = field.mul_ref(&a, &a_inv);
156        assert!(field.is_one(&product));
157    }
158
159    #[test]
160    fn test_is_unit() {
161        let field = ArkFieldWrapper::<Fr>::new();
162        
163        assert!(!field.is_unit(&field.zero()));
164        assert!(field.is_unit(&field.one()));
165        assert!(field.is_unit(&field.from_int(42)));
166    }
167
168    #[test]
169    #[should_panic(expected = "Division by zero")]
170    fn test_division_by_zero() {
171        let field = ArkFieldWrapper::<Fr>::new();
172        let a = field.from_int(5);
173        let _ = field.div(&a, &field.zero());
174    }
175}
ark_feanor/prime_field.rs

ark_feanor/
prime_field.rs
