problemreductions/models/misc/
factoring.rs

1//! Integer Factoring problem implementation.
2//!
3//! The Factoring problem represents integer factorization as a computational problem.
4//! Given a number N, find two factors (a, b) such that a * b = N.
5
6use crate::registry::{ConstructionError, CreateSpec, ProblemSchemaEntry};
7use crate::traits::Problem;
8use crate::types::Or;
9use num_bigint::{BigUint, ToBigUint};
10use num_traits::{One, Zero};
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "Factoring",
16        display_name: "Factoring",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Misc,
20        module_path: module_path!(),
21        description: "Factor a composite integer into two factors",
22        fields: FactoringCreateSpec::FIELDS,
23    }
24}
25
26/// The Integer Factoring problem.
27///
28/// Given a number to factor, find two ordered integers that multiply to give
29/// the target number. Variables represent the bits of the two factors. Factor
30/// widths may be supplied explicitly or derived from the target bit length.
31///
32/// # Example
33///
34/// ```
35/// use problemreductions::models::misc::Factoring;
36/// use problemreductions::{Problem, BruteForce};
37///
38/// // Factor 6 using the derived 2-bit factor widths.
39/// let problem = Factoring::new(6);
40///
41/// let solver = BruteForce::new();
42/// let solutions = solver.find_all_witnesses(&problem).unwrap();
43///
44/// // The canonical factor order finds 2*3=6.
45/// for (a, b) in &solutions {
46///     assert_eq!(a * b, num_bigint::BigUint::from(6u32));
47/// }
48/// ```
49#[derive(Debug, Clone, Serialize)]
50pub struct Factoring {
51    /// Number of bits for the first factor.
52    m: usize,
53    /// Number of bits for the second factor.
54    n: usize,
55    /// The number to factor.
56    #[serde(with = "super::biguint_serde::decimal_biguint")]
57    target: BigUint,
58}
59
60#[derive(Debug, Deserialize, crate::CreateSpec)]
61struct FactoringCreateSpec {
62    /// Number to factor.
63    #[serde(with = "super::biguint_serde::decimal_biguint")]
64    target: BigUint,
65    /// Optional maximum bit width of the smaller factor.
66    m: Option<usize>,
67    /// Optional maximum bit width of the larger factor.
68    n: Option<usize>,
69}
70
71impl TryFrom<FactoringCreateSpec> for Factoring {
72    type Error = ConstructionError;
73
74    fn try_from(spec: FactoringCreateSpec) -> Result<Self, Self::Error> {
75        match (spec.m, spec.n) {
76            (None, None) => Ok(Self::from_target(spec.target)),
77            (Some(m), Some(n)) if m <= n => Ok(Self {
78                m,
79                n,
80                target: spec.target,
81            }),
82            (Some(m), Some(n)) => Err(format!(
83                "first factor width m={m} must not exceed second factor width n={n}"
84            )
85            .into()),
86            _ => Err("factor widths m and n must be provided together".into()),
87        }
88    }
89}
90
91impl<'de> Deserialize<'de> for Factoring {
92    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
93    where
94        D: serde::Deserializer<'de>,
95    {
96        let spec = FactoringCreateSpec::deserialize(deserializer)?;
97        Self::try_from(spec).map_err(serde::de::Error::custom)
98    }
99}
100
101impl Factoring {
102    /// Create a Factoring problem with widths derived from the target.
103    ///
104    /// # Arguments
105    /// * `target` - The number to factor
106    pub fn new<T: ToBigUint>(target: T) -> Self {
107        let target = target
108            .to_biguint()
109            .expect("Factoring target must be nonnegative");
110        Self::from_target(target)
111    }
112
113    fn from_target(target: BigUint) -> Self {
114        let target_bits =
115            usize::try_from(target.bits().max(1)).expect("BigUint bit length fits usize");
116        let smaller_width = target_bits.div_ceil(2);
117        let larger_width = target_bits.saturating_sub(1);
118        let (m, n) = (
119            smaller_width.min(larger_width),
120            smaller_width.max(larger_width),
121        );
122        Self { m, n, target }
123    }
124
125    /// Create a Factoring problem with explicit maximum factor widths.
126    ///
127    /// The first factor is canonicalized as the smaller factor, so `m` must
128    /// not exceed `n`. Explicit widths may admit the trivial factorization
129    /// `(1, target)`.
130    pub fn with_factor_bits<T: ToBigUint>(target: T, m: usize, n: usize) -> Self {
131        assert!(
132            m <= n,
133            "first factor width m must not exceed second factor width n"
134        );
135        let target = target
136            .to_biguint()
137            .expect("Factoring target must be nonnegative");
138        Self { m, n, target }
139    }
140
141    /// Get the maximum number of bits for the smaller factor.
142    pub fn m(&self) -> usize {
143        self.m
144    }
145
146    /// Get the maximum number of bits for the larger factor.
147    pub fn n(&self) -> usize {
148        self.n
149    }
150
151    /// Get the maximum number of bits for the smaller factor (alias for `m()`).
152    pub fn num_bits_first(&self) -> usize {
153        self.m()
154    }
155
156    /// Get the maximum number of bits for the larger factor (alias for `n()`).
157    pub fn num_bits_second(&self) -> usize {
158        self.n()
159    }
160
161    /// Get the target number to factor.
162    pub fn target(&self) -> &BigUint {
163        &self.target
164    }
165
166    /// Number of bits needed to represent the target (`1` for zero).
167    pub fn target_bits(&self) -> usize {
168        usize::try_from(self.target.bits().max(1)).expect("BigUint bit length fits usize")
169    }
170
171    /// Read the two factors from a configuration.
172    ///
173    /// The first `m` bits represent the first factor,
174    /// the next `n` bits represent the second factor.
175    fn decode_factors(&self, config: &[usize]) -> (BigUint, BigUint) {
176        let a = bits_to_biguint(&config[..self.m]);
177        let b = bits_to_biguint(&config[self.m..self.m + self.n]);
178        (a, b)
179    }
180
181    /// Check if a configuration is a valid factorization.
182    pub fn is_valid_solution(&self, solution: &(BigUint, BigUint)) -> bool {
183        self.is_valid_factorization(solution)
184    }
185
186    /// Check if the configuration is a valid factorization.
187    pub fn is_valid_factorization(&self, solution: &(BigUint, BigUint)) -> bool {
188        let (left, right) = solution;
189        left.bits() <= u64::try_from(self.m).expect("factor width fits u64")
190            && right.bits() <= u64::try_from(self.n).expect("factor width fits u64")
191            && left <= right
192            && left * right == self.target
193    }
194}
195
196/// Convert a bit vector (little-endian) to an integer.
197fn bits_to_biguint(bits: &[usize]) -> BigUint {
198    bits.iter()
199        .enumerate()
200        .filter(|(_, bit)| **bit == 1)
201        .fold(BigUint::zero(), |value, (index, _)| {
202            value + (BigUint::one() << index)
203        })
204}
205
206/// Convert an integer to a bit vector (little-endian).
207#[allow(dead_code)]
208fn int_to_bits(n: &BigUint, num_bits: usize) -> Vec<usize> {
209    (0..num_bits)
210        .map(|index| usize::from(n.bit(u64::try_from(index).expect("bit index fits u64"))))
211        .collect()
212}
213
214/// Check if the given factors correctly factorize the target.
215#[cfg(test)]
216pub(crate) fn is_factoring(target: &BigUint, a: &BigUint, b: &BigUint) -> bool {
217    a * b == *target
218}
219
220impl Problem for Factoring {
221    const NAME: &'static str = "Factoring";
222    type Solution = (BigUint, BigUint);
223    type Value = Or;
224
225    crate::problem_parameters![
226        ("num_bits_first", num_bits_first),
227        ("num_bits_second", num_bits_second),
228        ("target_bits", target_bits),
229    ];
230
231    fn evaluate(&self, solution: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
232        Ok(Or(self.is_valid_factorization(solution)))
233    }
234
235    fn variant() -> Vec<(&'static str, &'static str)> {
236        crate::variant_params![]
237    }
238}
239
240impl crate::solvers::BruteForceProblem for Factoring {
241    fn dimensions(&self) -> Vec<usize> {
242        vec![2; self.m + self.n]
243    }
244}
245
246crate::declare_variants! {
247    default Factoring => "exp((num_bits_first + num_bits_second)^(1/3) * log(num_bits_first + num_bits_second)^(2/3))" create FactoringCreateSpec,
248}
249
250crate::register_brute_force! {
251    Factoring decode |problem: &Factoring, indices: Vec<usize>| problem.decode_factors(&indices),
252}
253
254#[cfg(feature = "example-db")]
255pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
256    vec![crate::example_db::specs::ModelExampleSpec {
257        id: "factoring",
258        instance: Box::new(Factoring::new(15)),
259        optimal_config: serde_json::to_value((BigUint::from(3u32), BigUint::from(5u32)))
260            .expect("solution serialization must succeed"),
261        optimal_value: serde_json::json!(true),
262    }]
263}
264
265#[cfg(test)]
266#[path = "../../unit_tests/models/misc/factoring.rs"]
267mod tests;
problemreductions/models/misc/factoring.rs

problemreductions/models/misc/
factoring.rs
