ecm

Elliptic Curve factorization - code and slides
git clone https://git.tronto.net/ecm
Download | Log | Files | Refs | README

main.rs (2877B)

      1 use std::env;
      2 use std::fmt;
      3 use std::cmp;
      4 use rand::Rng;
      5 use num_integer::Integer;
      6 use num_traits::identities::{Zero, One};
      7 use num_bigint::{BigInt, RandomBits};
      8 
      9 #[derive(Clone)]
     10 enum Point {
     11     NonZero((BigInt, BigInt)),
     12     Zero
     13 }
     14 
     15 impl fmt::Display for Point {
     16     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
     17         match self {
     18             Point::NonZero((x, y)) => write!(f, "({x}, {y})"),
     19             Point::Zero => write!(f, "∞")
     20         }
     21     }
     22 }
     23 
     24 fn inverse_mod(a: &BigInt, n: &BigInt) -> Result<BigInt, BigInt> {
     25     let egcd = a.extended_gcd(n);
     26     if egcd.gcd.is_one() { Ok(egcd.x) } else { Err(egcd.gcd) }
     27 }
     28 
     29 fn ec_sum(p: &Point, q: &Point, a: &BigInt, n: &BigInt) -> Result<Point, BigInt> {
     30     // TODO: this should use references
     31     let (px, py) = if let Point::NonZero((x, y)) = p {
     32         (x, y)
     33     } else {
     34         return Ok(q.clone());
     35     };
     36 
     37     let (qx, qy) = if let Point::NonZero((x, y)) = q {
     38         (x, y)
     39     } else {
     40         return Ok(p.clone());
     41     };
     42 
     43     if ((px - qx) % n).is_zero() && ((py + qy) % n).is_zero() {
     44         return Ok(Point::Zero);
     45     }
     46 
     47     let k = if px != qx {
     48         (py - qy) * inverse_mod(&(px - qx), n)?
     49     } else {
     50         (3 * px * px + a) * inverse_mod(&(py + qy), n)?
     51     };
     52 
     53     let x = &k * &k - px - qx;
     54     let y = k * (px - &x) - py;
     55 
     56     Ok(Point::NonZero((x.clone() % n, y.clone() % n)))
     57 }
     58 
     59 fn ec_mul(m: &BigInt, p: &Point, a: &BigInt, n: &BigInt) -> Result<Point, BigInt> {
     60     if m.is_zero() {
     61         return Ok(Point::Zero);
     62     }
     63 
     64     if (m % BigInt::from(2)).is_zero() {
     65         ec_mul(&(m / 2), &ec_sum(p, p, a, n)?, a, n)
     66     } else {
     67         ec_sum(p, &ec_mul(&(m - 1), p, a, n)?, a, n)
     68     }
     69 }
     70 
     71 
     72 // Elliptic curve factorization method
     73 // If n is prime, this method goes into an infinite loop
     74 fn find_factor(n: &BigInt) -> BigInt {
     75     let mut rng = rand::thread_rng();
     76     let bound = cmp::max(n.sqrt().sqrt().sqrt() + 2, BigInt::from(256));
     77 
     78     loop {
     79         let a = rng.sample::<BigInt, _>(RandomBits::new(256)) % n;
     80         let x = rng.sample::<BigInt, _>(RandomBits::new(256)) % n;
     81         let y = rng.sample::<BigInt, _>(RandomBits::new(256)) % n;
     82         let mut p = Point::NonZero((x, y));
     83 
     84         let mut m = BigInt::from(2);
     85         while m < bound && !matches!(p, Point::Zero) {
     86             match ec_mul(&m, &p, &a, n) {
     87                 Err(f) => {
     88                     println!("Factor {f} found with a = {a}, m = {m} and p = {p}");
     89                     return f;
     90                 },
     91                 Ok(new_p) => p = new_p
     92             }
     93             m += 1;
     94         }
     95     }
     96 }
     97 
     98 fn main() {
     99     let args: Vec<String> = env::args().collect();
    100     if let Ok(n) = args[1].parse::<BigInt>() {
    101         let f = find_factor(&n);
    102         println!("{} = {} * {}", &n, &f, &n / &f);
    103     } else {
    104         println!("Invalid argument {} (cannot convert to number)", args[1]);
    105     }
    106 }