Is this number prime

Primality testing is cheap. Factoring is expensive. Most of internet security rides on the gap between them.

1. 01
   num-prime gives you Miller-Rabin (probabilistic, fast) and Baillie-PSW (no known counterexamples) as one call. The same crate exposes factorize for the hard direction — and the contrast in runtime between the two is exactly the gap that secures the internet.

   use num_bigint::BigUint;
   use num_prime::nt_funcs::{is_prime, factorize};
   
   fn prime_check(n: &BigUint) -> bool {
       is_prime(n, None).probably() // microseconds, even at 4096 bits
   }
   
   fn try_factor(n: &BigUint) -> std::collections::BTreeMap<BigUint, usize> {
       factorize(n.clone()) // fast for small n, infeasible for cryptographic n
   }

2. 02
   BTreeMap<K, V> from the standard library is a sorted associative map — a key-value store like HashMap, but with keys kept in sorted order. Implemented as a B-tree (the multi-way balanced tree used in databases and filesystems), it offers O(log n) lookups, inserts, and deletes, plus efficient range queries. HashMap is faster on average — O(1) lookup — but gives no order guarantee. The factorization here uses BTreeMap<BigUint, usize> so the result is sorted by prime: 60 = 2² × 3 × 5 comes back as the keys 2, 3, 5 in that order, which is what a reader expects. Reach for BTreeMap when you need ordering, range scans, or deterministic iteration; reach for HashMap for raw lookup speed.

   use std::collections::{BTreeMap, HashMap};
   
   // BTreeMap — keys kept in sorted order:
   let mut counts: BTreeMap<&str, i32> = BTreeMap::new();
   counts.insert("zebra", 1);
   counts.insert("apple", 2);
   counts.insert("mango", 3);
   
   for (k, v) in &counts {
       println!("{}: {}", k, v);
       // apple: 2     ← sorted alphabetically
       // mango: 3
       // zebra: 1
   }
   
   // HashMap — no order guarantee:
   let mut counts: HashMap<&str, i32> = HashMap::new();
   counts.insert("zebra", 1);
   counts.insert("apple", 2);
   counts.insert("mango", 3);
   
   for (k, v) in &counts {
       println!("{}: {}", k, v);
       // mango: 3     ← order depends on the hash, not on insertion order
       // apple: 2
       // zebra: 1
   }
   
   // Range queries — only available because BTreeMap keys are sorted:
   let in_range: Vec<_> = counts.range("apple".."mango").collect();
   
   // Performance comparison:
   //   BTreeMap     O(log n) lookup / insert / delete.
   //                ordered iteration, range queries.
   //   HashMap      O(1) average lookup / insert / delete.
   //                no order, faster in absolute terms.
   //
   // Page 21 uses BTreeMap so the factorization output is deterministic
   // and reads naturally: factorize(60) = {2 → 2, 3 → 1, 5 → 1}.

3. 03
   factorize is one line at the callsite; the algorithms behind it are not. The function combines several classical methods, picking which to use based on the size of the input. Trial division strips small prime factors by trying 2, 3, 5, 7, 11, … up to roughly √n — fast for small n, hopeless beyond about 30 digits. Pollard's rho is a probabilistic cycle-detection algorithm that finds factors via a pseudo-random sequence; sub-exponential expected time, practical to about 25–30 digits per call. Pollard's p−1 finds factors p where p−1 has only small prime factors — sometimes blazingly fast, sometimes useless. The elliptic curve method generalises Pollard p−1 and is the tool of choice for peeling off medium-sized factors. For very large composites, the quadratic sieve and the general number field sieve are the asymptotically best known classical algorithms. None of these is polynomial-time. GNFS, the fastest, has runtime exp((1.92 + o(1)) · (ln n)^(1/3) · (ln ln n)^(2/3)) — sub-exponential, but still growing much faster than any polynomial in the digit count. That's the whole bet: a 2048-bit RSA modulus would take longer than the age of the universe to factor on current hardware with GNFS. Calling factorize on a small number returns instantly; calling it on a cryptographic number simply does not return.

   // What factorize() does internally, simplified:
   //
   // fn factorize(mut n: BigUint) -> BTreeMap<BigUint, usize> {
   //     let mut factors = BTreeMap::new();
   //
   //     // 1. Strip small prime factors by trial division.
   //     for p in [2, 3, 5, 7, 11, 13, ...] {
   //         while n % p == 0 {
   //             *factors.entry(p).or_insert(0) += 1;
   //             n /= p;
   //         }
   //         if p * p > n { break; }
   //     }
   //
   //     // 2. If the remaining cofactor is > 1, run probabilistic methods.
   //     while n > 1 {
   //         if is_prime(&n).probably() {
   //             *factors.entry(n.clone()).or_insert(0) += 1;
   //             break;
   //         }
   //         let factor = pollard_rho(&n)            // try fast methods first
   //                     .or(pollard_p_minus_1(&n))
   //                     .or(ecm(&n))                 // medium-size factors
   //                     .or(quadratic_sieve(&n));    // heavy artillery
   //         while n % &factor == 0 {
   //             *factors.entry(factor.clone()).or_insert(0) += 1;
   //             n /= &factor;
   //         }
   //     }
   //     factors
   // }
   
   
   // Timing on consumer hardware (very rough):
   //
   //   20-digit number          milliseconds
   //   40-digit number          seconds
   //   60-digit number          minutes to hours
   //   100-digit number         days to weeks (distributed)
   //   200-digit number         years on a research cluster
   //   600+ digits (RSA-2048)   longer than the universe has existed
   //
   // The exponential-vs-polynomial gap between primality testing (page 5)
   // and factoring is the entire foundation of RSA, TLS, code-signing,
   // and most of the public-key cryptography on the internet.