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

problemreductions/models/algebraic/
quadratic_congruences.rs
