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::{FieldInfo, ProblemSchemaEntry};
7use crate::traits::{OptimizationProblem, Problem};
8use crate::types::{Direction, SolutionSize};
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "Factoring",
14        module_path: module_path!(),
15        description: "Factor a composite integer into two factors",
16        fields: &[
17            FieldInfo { name: "m", type_name: "usize", description: "Bits for first factor" },
18            FieldInfo { name: "n", type_name: "usize", description: "Bits for second factor" },
19            FieldInfo { name: "target", type_name: "u64", description: "Number to factor" },
20        ],
21    }
22}
23
24/// The Integer Factoring problem.
25///
26/// Given a number to factor, find two integers that multiply to give
27/// the target number. Variables represent the bits of the two factors.
28///
29/// # Example
30///
31/// ```
32/// use problemreductions::models::misc::Factoring;
33/// use problemreductions::{Problem, Solver, BruteForce};
34///
35/// // Factor 6 with 2-bit factors (allowing factors 0-3)
36/// let problem = Factoring::new(2, 2, 6);
37///
38/// let solver = BruteForce::new();
39/// let solutions = solver.find_all_best(&problem);
40///
41/// // Should find: 2*3=6 or 3*2=6
42/// for sol in &solutions {
43///     let (a, b) = problem.read_factors(sol);
44///     assert_eq!(a * b, 6);
45/// }
46/// ```
47#[derive(Debug, Clone, Serialize, Deserialize)]
48pub struct Factoring {
49    /// Number of bits for the first factor.
50    m: usize,
51    /// Number of bits for the second factor.
52    n: usize,
53    /// The number to factor.
54    target: u64,
55}
56
57impl Factoring {
58    /// Create a new Factoring problem.
59    ///
60    /// # Arguments
61    /// * `m` - Number of bits for the first factor
62    /// * `n` - Number of bits for the second factor
63    /// * `target` - The number to factor
64    pub fn new(m: usize, n: usize, target: u64) -> Self {
65        Self { m, n, target }
66    }
67
68    /// Get the number of bits for the first factor.
69    pub fn m(&self) -> usize {
70        self.m
71    }
72
73    /// Get the number of bits for the second factor.
74    pub fn n(&self) -> usize {
75        self.n
76    }
77
78    /// Get the number of bits for the first factor (alias for `m()`).
79    pub fn num_bits_first(&self) -> usize {
80        self.m()
81    }
82
83    /// Get the number of bits for the second factor (alias for `n()`).
84    pub fn num_bits_second(&self) -> usize {
85        self.n()
86    }
87
88    /// Get the target number to factor.
89    pub fn target(&self) -> u64 {
90        self.target
91    }
92
93    /// Read the two factors from a configuration.
94    ///
95    /// The first `m` bits represent the first factor,
96    /// the next `n` bits represent the second factor.
97    pub fn read_factors(&self, config: &[usize]) -> (u64, u64) {
98        let a = bits_to_int(&config[..self.m]);
99        let b = bits_to_int(&config[self.m..self.m + self.n]);
100        (a, b)
101    }
102
103    /// Check if a configuration is a valid factorization.
104    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
105        self.is_valid_factorization(config)
106    }
107
108    /// Check if the configuration is a valid factorization.
109    pub fn is_valid_factorization(&self, config: &[usize]) -> bool {
110        let (a, b) = self.read_factors(config);
111        a * b == self.target
112    }
113}
114
115/// Convert a bit vector (little-endian) to an integer.
116fn bits_to_int(bits: &[usize]) -> u64 {
117    bits.iter().enumerate().map(|(i, &b)| (b as u64) << i).sum()
118}
119
120/// Convert an integer to a bit vector (little-endian).
121#[allow(dead_code)]
122fn int_to_bits(n: u64, num_bits: usize) -> Vec<usize> {
123    (0..num_bits).map(|i| ((n >> i) & 1) as usize).collect()
124}
125
126/// Check if the given factors correctly factorize the target.
127#[cfg(test)]
128pub(crate) fn is_factoring(target: u64, a: u64, b: u64) -> bool {
129    a * b == target
130}
131
132impl Problem for Factoring {
133    const NAME: &'static str = "Factoring";
134    type Metric = SolutionSize<i32>;
135
136    fn dims(&self) -> Vec<usize> {
137        vec![2; self.m + self.n]
138    }
139
140    fn evaluate(&self, config: &[usize]) -> SolutionSize<i32> {
141        let (a, b) = self.read_factors(config);
142        let product = a * b;
143        // Distance from target (0 means exact match)
144        let distance = if product > self.target {
145            (product - self.target) as i32
146        } else {
147            (self.target - product) as i32
148        };
149        SolutionSize::Valid(distance)
150    }
151
152    fn variant() -> Vec<(&'static str, &'static str)> {
153        crate::variant_params![]
154    }
155}
156
157impl OptimizationProblem for Factoring {
158    type Value = i32;
159
160    fn direction(&self) -> Direction {
161        Direction::Minimize
162    }
163}
164
165crate::declare_variants! {
166    Factoring => "exp((m + n)^(1/3) * log(m + n)^(2/3))",
167}
168
169#[cfg(test)]
170#[path = "../../unit_tests/models/misc/factoring.rs"]
171mod tests;
problemreductions/models/misc/factoring.rs

problemreductions/models/misc/
factoring.rs
