Skip to main content

factor_via_order

Function factor_via_order 

Source
pub fn factor_via_order(
    n: &BigInt,
    tries: usize,
    bound: u64,
    seed: u64,
) -> Option<BigInt>
Expand description

Factoring via order-finding — the classical shell of Shor’s algorithm. Draw bases a, find each order (bounded by bound), and split n when the order is even with a nontrivial root. None if no trial succeeded within tries/bound. Classically O(√order) per base (exponential in bit length); this is exactly the step Shor’s quantum Fourier transform makes polynomial.