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

problemreductions/models/misc/
factoring.rs
