Struct Factoring 

pub struct Factoring { /* private fields */ }

The Integer Factoring problem.

Given a number to factor, find two ordered integers that multiply to give the target number. Variables represent the bits of the two factors. Factor widths may be supplied explicitly or derived from the target bit length.

Example

use problemreductions::models::misc::Factoring;
use problemreductions::{Problem, BruteForce};

// Factor 6 using the derived 2-bit factor widths.
let problem = Factoring::new(6);

let solver = BruteForce::new();
let solutions = solver.find_all_witnesses(&problem).unwrap();

// The canonical factor order finds 2*3=6.
for (a, b) in &solutions {
    assert_eq!(a * b, num_bigint::BigUint::from(6u32));
}

Implementations

impl Factoring

pub fn new<T: ToBigUint>(target: T) -> Self

Create a Factoring problem with widths derived from the target.

Arguments

• target - The number to factor

pub fn with_factor_bits<T: ToBigUint>(target: T, m: usize, n: usize) -> Self

Create a Factoring problem with explicit maximum factor widths.

The first factor is canonicalized as the smaller factor, so m must not exceed n. Explicit widths may admit the trivial factorization (1, target).

pub fn m(&self) -> usize

Get the maximum number of bits for the smaller factor.

pub fn n(&self) -> usize

Get the maximum number of bits for the larger factor.

pub fn num_bits_first(&self) -> usize

Get the maximum number of bits for the smaller factor (alias for m()).

pub fn num_bits_second(&self) -> usize

Get the maximum number of bits for the larger factor (alias for n()).

pub fn target(&self) -> &BigUint

Get the target number to factor.

pub fn target_bits(&self) -> usize

Number of bits needed to represent the target (1 for zero).

pub fn is_valid_solution(&self, solution: &(BigUint, BigUint)) -> bool

Check if a configuration is a valid factorization.

pub fn is_valid_factorization(&self, solution: &(BigUint, BigUint)) -> bool

Check if the configuration is a valid factorization.

Trait Implementations

impl BruteForceProblem for Factoring

fn dimensions(&self) -> Vec<usize>

Cardinality of each coordinate in the brute-force search space.

fn num_variables(&self) -> usize

Number of coordinates in the brute-force search space.

impl Clone for Factoring

fn clone(&self) -> Factoring

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Factoring

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl DeclaredVariant for Factoring

impl<'de> Deserialize<'de> for Factoring

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for Factoring

const NAME: &'static str = "Factoring"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Solution = (BigUint, BigUint)

Mathematical witness type for this problem.

type Value = Or

The evaluation value type.

fn parameter_names() -> &'static [&'static str]

Canonical parameter names for this problem model.

fn parameters(&self) -> ProblemParameters

Measure the complete canonical parameters of this concrete instance.

fn evaluate(&self, solution: &Self::Solution) -> Result<Or, EvaluationError>

Evaluate the problem on a solution.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<CircuitSAT> for Factoring

type Result = ReductionFactoringToCircuit

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<ILP<i64>> for Factoring

type Result = ReductionFactoringToILP

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl Serialize for Factoring

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.