problemreductions/models/algebraic/
quadratic_congruences.rs

1//! Quadratic Congruences problem implementation.
2//!
3//! Given non-negative integers `a`, `b`, and `c` with `b > 0` and `a < b`,
4//! determine whether there exists a positive integer `x < c` such that
5//! `x² ≡ a (mod b)`.
6//!
7//! The witness integer `x` is encoded as a little-endian binary vector so the
8//! model can represent arbitrarily large instances while still fitting the
9//! crate's `Vec<usize>` configuration interface.
10
11use crate::registry::{FieldInfo, ProblemSchemaEntry};
12use crate::traits::Problem;
13use crate::types::Or;
14use num_bigint::{BigUint, ToBigUint};
15use num_traits::{One, Zero};
16use serde::de::Error as _;
17use serde::{Deserialize, Deserializer, Serialize};
18
19inventory::submit! {
20    ProblemSchemaEntry {
21        name: "QuadraticCongruences",
22        display_name: "Quadratic Congruences",
23        aliases: &[],
24        dimensions: &[],
25        category: crate::registry::ProblemCategory::Algebraic,
26        module_path: module_path!(),
27        description: "Decide whether x² ≡ a (mod b) has a solution for x in {1, ..., c-1}",
28        fields: &[
29            FieldInfo { name: "a", type_name: "BigUint", description: "a" },
30            FieldInfo { name: "b", type_name: "BigUint", description: "b" },
31            FieldInfo { name: "c", type_name: "BigUint", description: "c" },
32        ],
33    }
34}
35
36/// Quadratic Congruences problem.
37///
38/// Given non-negative integers `a`, `b`, `c` with `b > 0` and `a < b`,
39/// determine whether there exists a positive integer `x < c` such that
40/// `x² ≡ a (mod b)`.
41///
42/// The configuration encodes `x` in little-endian binary:
43/// `config[i] ∈ {0,1}` is the coefficient of `2^i`.
44#[derive(Debug, Clone, Serialize)]
45pub struct QuadraticCongruences {
46    /// Quadratic residue target.
47    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
48    a: BigUint,
49    /// Modulus.
50    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
51    b: BigUint,
52    /// Search-space bound; feasible witnesses satisfy `1 <= x < c`.
53    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
54    c: BigUint,
55}
56
57fn bit_length(value: &BigUint) -> usize {
58    if value.is_zero() {
59        0
60    } else {
61        let bytes = value.to_bytes_be();
62        let msb = *bytes.first().expect("nonzero BigUint has bytes");
63        8 * (bytes.len() - 1) + (8 - msb.leading_zeros() as usize)
64    }
65}
66
67impl QuadraticCongruences {
68    fn validate_inputs(
69        a: &BigUint,
70        b: &BigUint,
71        c: &BigUint,
72    ) -> Result<(), crate::registry::ConstructionError> {
73        if b.is_zero() {
74            return Err("Modulus b must be positive".to_string().into());
75        }
76        if c.is_zero() {
77            return Err("Bound c must be positive".to_string().into());
78        }
79        if a >= b {
80            return Err(format!("Residue a ({a}) must be less than modulus b ({b})").into());
81        }
82        Ok(())
83    }
84
85    /// Create a new QuadraticCongruences instance, returning an error instead of
86    /// panicking when the inputs are invalid.
87    pub fn try_new<A, B, C>(a: A, b: B, c: C) -> Result<Self, crate::registry::ConstructionError>
88    where
89        A: ToBigUint,
90        B: ToBigUint,
91        C: ToBigUint,
92    {
93        let a = a
94            .to_biguint()
95            .ok_or_else(|| "Residue a must be nonnegative".to_string())?;
96        let b = b
97            .to_biguint()
98            .ok_or_else(|| "Modulus b must be nonnegative".to_string())?;
99        let c = c
100            .to_biguint()
101            .ok_or_else(|| "Bound c must be nonnegative".to_string())?;
102        Self::validate_inputs(&a, &b, &c)?;
103        Ok(Self { a, b, c })
104    }
105
106    /// Create a new QuadraticCongruences instance.
107    ///
108    /// # Panics
109    ///
110    /// Panics if `b == 0`, `c == 0`, or `a >= b`.
111    pub fn new<A, B, C>(a: A, b: B, c: C) -> Self
112    where
113        A: ToBigUint,
114        B: ToBigUint,
115        C: ToBigUint,
116    {
117        Self::try_new(a, b, c).unwrap_or_else(|msg| panic!("{msg}"))
118    }
119
120    /// Get the quadratic residue target `a`.
121    pub fn a(&self) -> &BigUint {
122        &self.a
123    }
124
125    /// Get the modulus `b`.
126    pub fn b(&self) -> &BigUint {
127        &self.b
128    }
129
130    /// Get the search-space bound `c`.
131    pub fn c(&self) -> &BigUint {
132        &self.c
133    }
134
135    /// Number of bits needed to encode the residue target.
136    pub fn bit_length_a(&self) -> usize {
137        bit_length(&self.a)
138    }
139
140    /// Number of bits needed to encode the modulus.
141    pub fn bit_length_b(&self) -> usize {
142        bit_length(&self.b)
143    }
144
145    /// Number of bits needed to encode the search bound.
146    pub fn bit_length_c(&self) -> usize {
147        bit_length(&self.c)
148    }
149
150    fn witness_bit_length(&self) -> usize {
151        if self.c <= BigUint::one() {
152            0
153        } else {
154            bit_length(&(&self.c - BigUint::one()))
155        }
156    }
157
158    /// Encode a witness integer `x` as a little-endian binary configuration.
159    pub fn encode_witness(&self, x: &BigUint) -> Option<Vec<usize>> {
160        if x.is_zero() || x >= &self.c {
161            return None;
162        }
163
164        let num_bits = self.witness_bit_length();
165        let mut remaining = x.clone();
166        let mut config = Vec::with_capacity(num_bits);
167
168        for _ in 0..num_bits {
169            config.push(if (&remaining & BigUint::one()).is_zero() {
170                0
171            } else {
172                1
173            });
174            remaining >>= 1usize;
175        }
176
177        if remaining.is_zero() {
178            Some(config)
179        } else {
180            None
181        }
182    }
183
184    /// Decode a little-endian binary configuration into its witness integer `x`.
185    pub fn decode_witness(&self, config: &[usize]) -> Option<BigUint> {
186        if config.len() != self.witness_bit_length() || config.iter().any(|&digit| digit > 1) {
187            return None;
188        }
189
190        let mut value = BigUint::zero();
191        let mut weight = BigUint::one();
192        for &digit in config {
193            if digit == 1 {
194                value += &weight;
195            }
196            weight <<= 1usize;
197        }
198        Some(value)
199    }
200}
201
202#[derive(Deserialize)]
203struct QuadraticCongruencesData {
204    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
205    a: BigUint,
206    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
207    b: BigUint,
208    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
209    c: BigUint,
210}
211
212impl<'de> Deserialize<'de> for QuadraticCongruences {
213    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
214    where
215        D: Deserializer<'de>,
216    {
217        let data = QuadraticCongruencesData::deserialize(deserializer)?;
218        Self::try_new(data.a, data.b, data.c).map_err(D::Error::custom)
219    }
220}
221
222impl Problem for QuadraticCongruences {
223    const NAME: &'static str = "QuadraticCongruences";
224    type Solution = BigUint;
225    type Value = Or;
226
227    crate::problem_parameters![
228        ("bit_length_a", bit_length_a),
229        ("bit_length_b", bit_length_b),
230        ("bit_length_c", bit_length_c),
231    ];
232
233    fn variant() -> Vec<(&'static str, &'static str)> {
234        crate::variant_params![]
235    }
236
237    fn evaluate(&self, x: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
238        Ok({
239            if x.is_zero() || x >= self.c() {
240                return Ok(Or(false));
241            }
242
243            let satisfies = (x * x) % self.b() == self.a().clone();
244            Or(satisfies)
245        })
246    }
247}
248
249impl crate::solvers::BruteForceProblem for QuadraticCongruences {
250    fn dimensions(&self) -> Vec<usize> {
251        let num_bits = self.witness_bit_length();
252        if num_bits == 0 {
253            Vec::new()
254        } else {
255            vec![2; num_bits]
256        }
257    }
258}
259
260crate::declare_variants! {
261    default QuadraticCongruences => "2^bit_length_c",
262}
263
264crate::register_brute_force! {
265    QuadraticCongruences decode |problem: &QuadraticCongruences, indices: Vec<usize>| problem.decode_witness(&indices).expect("enumerated quadratic-congruence bits are valid"),
266}
267
268#[cfg(feature = "example-db")]
269pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
270    let instance = QuadraticCongruences::new(4u32, 15u32, 10u32);
271    let optimal_config = BigUint::from(2u32);
272
273    vec![crate::example_db::specs::ModelExampleSpec {
274        id: "quadratic_congruences",
275        instance: Box::new(instance),
276        optimal_config: serde_json::to_value(optimal_config)
277            .expect("solution serialization must succeed"),
278        optimal_value: serde_json::json!(true),
279    }]
280}
281
282#[cfg(test)]
283#[path = "../../unit_tests/models/algebraic/quadratic_congruences.rs"]
284mod tests;
problemreductions/models/algebraic/quadratic_congruences.rs

problemreductions/models/algebraic/
quadratic_congruences.rs
