golden_ecc.rs

golden_ecc.rs

use std::f64::consts::PI;
use std::fmt;
use std::str::FromStr;

// =====================================================================
// 1. secp256k1 Curve Constants
// =====================================================================
// Field Prime p = 2^256 - 2^32 - 977
// 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
const P: [u64; 4] = [
    0xFFFF_FFFE_FFFF_FC2F, // Corrected Limb 0 (2^64 - 2^32 - 977)
    0xFFFF_FFFF_FFFF_FFFF,
    0xFFFF_FFFF_FFFF_FFFF,
    0xFFFF_FFFF_FFFF_FFFF,
];

// Generator Point G (X, Y)
const G_X: [u64; 4] = [
    0x59F2_815B_16F8_1798,
    0x029B_FCDB_2DCE_28D9,
    0x55A0_6295_CE87_0B07,
    0x79BE_667E_F9DC_BBAC,
];

const G_Y: [u64; 4] = [
    0x9C47_D08F_FB10_D4B8,
    0xFD17_B448_A685_5419,
    0x5DA4_FBFC_0E11_08A8,
    0x483A_DA77_26A3_C465,
];

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct U256(pub [u64; 4]);

impl U256 {
    const ZERO: Self = U256([0, 0, 0, 0]);

    fn from_u64(val: u64) -> Self {
        U256([val, 0, 0, 0])
    }

    fn from_hex(hex: &str) -> Self {
        let clean = hex.trim_start_matches("0x");
        let padded = format!("{:0>64}", clean);
        let mut limbs = [0u64; 4];
        for i in 0..4 {
            let start = (3 - i) * 16;
            let end = start + 16;
            limbs[i] = u64::from_str_radix(&padded[start..end], 16).unwrap_or(0);
        }
        U256(limbs)
    }

    fn is_zero(&self) -> bool {
        self.0 == [0, 0, 0, 0]
    }

    fn bit(&self, index: usize) -> u8 {
        if index >= 256 {
            return 0;
        }
        let word = self.0[index / 64];
        ((word >> (index % 64)) & 1) as u8
    }

    fn add_mod(&self, rhs: &Self, m: &Self) -> Self {
        let (r0, c0) = self.0[0].overflowing_add(rhs.0[0]);
        let (r1, c1) = add_with_carry(self.0[1], rhs.0[1], c0);
        let (r2, c2) = add_with_carry(self.0[2], rhs.0[2], c1);
        let (r3, c3) = add_with_carry(self.0[3], rhs.0[3], c2);
        let res = U256([r0, r1, r2, r3]);

        if c3 || res.gte(m) {
            res.sub_no_underflow(m)
        } else {
            res
        }
    }

    fn add_unbounded(&self, rhs: &Self) -> Self {
        let (r0, c0) = self.0[0].overflowing_add(rhs.0[0]);
        let (r1, c1) = add_with_carry(self.0[1], rhs.0[1], c0);
        let (r2, c2) = add_with_carry(self.0[2], rhs.0[2], c1);
        let (r3, _) = add_with_carry(self.0[3], rhs.0[3], c2);
        U256([r0, r1, r2, r3])
    }

    fn sub_mod(&self, rhs: &Self, m: &Self) -> Self {
        if self.gte(rhs) {
            self.sub_no_underflow(rhs)
        } else {
            let tmp = m.sub_no_underflow(rhs);
            self.add_mod(&tmp, m)
        }
    }

    fn sub_no_underflow(&self, rhs: &Self) -> Self {
        let (r0, b0) = self.0[0].overflowing_sub(rhs.0[0]);
        let (r1, b1) = sub_with_borrow(self.0[1], rhs.0[1], b0);
        let (r2, b2) = sub_with_borrow(self.0[2], rhs.0[2], b1);
        let (r3, _) = sub_with_borrow(self.0[3], rhs.0[3], b2);
        U256([r0, r1, r2, r3])
    }

    fn mul_mod(&self, rhs: &Self, m: &Self) -> Self {
        let mut res = U256::ZERO;
        let mut base = *self;
        for i in 0..256 {
            if rhs.bit(i) == 1 {
                res = res.add_mod(&base, m);
            }
            base = base.add_mod(&base, m);
        }
        res
    }

    fn pow_mod(&self, exp: &Self, m: &Self) -> Self {
        let mut res = U256::from_u64(1);
        let mut base = *self;
        for i in 0..256 {
            if exp.bit(i) == 1 {
                res = res.mul_mod(&base, m);
            }
            base = base.mul_mod(&base, m);
        }
        res
    }

    fn inv_mod(&self, m: &Self) -> Self {
        // Fermat's Little Theorem: a^(p-2) mod p
        let p_minus_2 = m.sub_no_underflow(&U256::from_u64(2));
        self.pow_mod(&p_minus_2, m)
    }

    // Modular Square Root for p ≡ 3 mod 4: y = w^((p+1)/4) mod p
    fn sqrt_mod(&self, m: &Self) -> Option<Self> {
        let p_plus_1 = m.add_mod(&U256::from_u64(1), &U256([u64::MAX, u64::MAX, u64::MAX, u64::MAX]));
        let exp = U256([
            (p_plus_1.0[0] >> 2) | (p_plus_1.0[1] << 62),
            (p_plus_1.0[1] >> 2) | (p_plus_1.0[2] << 62),
            (p_plus_1.0[2] >> 2) | (p_plus_1.0[3] << 62),
            p_plus_1.0[3] >> 2,
        ]);

        let y = self.pow_mod(&exp, m);
        let check = y.mul_mod(&y, m);
        if check == *self {
            Some(y)
        } else {
            None
        }
    }

    fn gte(&self, rhs: &Self) -> bool {
        for i in (0..4).rev() {
            if self.0[i] > rhs.0[i] {
                return true;
            }
            if self.0[i] < rhs.0[i] {
                return false;
            }
        }
        true
    }

    fn to_hex(&self) -> String {
        format!(
            "{:016x}{:016x}{:016x}{:016x}",
            self.0[3], self.0[2], self.0[1], self.0[0]
        )
    }
}

impl fmt::LowerHex for U256 {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.to_hex())
    }
}

impl FromStr for U256 {
    type Err = ();

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        Ok(U256::from_hex(s))
    }
}

fn add_with_carry(a: u64, b: u64, carry: bool) -> (u64, bool) {
    let (res1, c1) = a.overflowing_add(b);
    let (res2, c2) = res1.overflowing_add(carry as u64);
    (res2, c1 || c2)
}

fn sub_with_borrow(a: u64, b: u64, borrow: bool) -> (u64, bool) {
    let (res1, b1) = a.overflowing_sub(b);
    let (res2, b2) = res1.overflowing_sub(borrow as u64);
    (res2, b1 || b2)
}

// =====================================================================
// 2. Point Arithmetic
// =====================================================================
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Point {
    x: U256,
    y: U256,
}

fn point_add(p1: Option<Point>, p2: Option<Point>, modulus: &U256) -> Option<Point> {
    let p1 = match p1 {
        Some(p) => p,
        None => return p2,
    };
    let p2 = match p2 {
        Some(p) => p,
        None => return Some(p1),
    };

    if p1.x == p2.x && p1.y != p2.y {
        return None;
    }

    let slope = if p1.x == p2.x {
        let x_sq = p1.x.mul_mod(&p1.x, modulus);
        let num = U256::from_u64(3).mul_mod(&x_sq, modulus);
        let den = U256::from_u64(2).mul_mod(&p1.y, modulus).inv_mod(modulus);
        num.mul_mod(&den, modulus)
    } else {
        let num = p2.y.sub_mod(&p1.y, modulus);
        let den = p2.x.sub_mod(&p1.x, modulus).inv_mod(modulus);
        num.mul_mod(&den, modulus)
    };

    let s_sq = slope.mul_mod(&slope, modulus);
    let x3 = s_sq.sub_mod(&p1.x, modulus).sub_mod(&p2.x, modulus);
    let y3 = slope
        .mul_mod(&p1.x.sub_mod(&x3, modulus), modulus)
        .sub_mod(&p1.y, modulus);

    Some(Point { x: x3, y: y3 })
}

fn point_mul_256(pt: Point, scalar: &U256, modulus: &U256) -> Option<Point> {
    let mut res: Option<Point> = None;
    let mut addend = Some(pt);

    for i in 0..256 {
        if scalar.bit(i) == 1 {
            res = point_add(res, addend, modulus);
        }
        addend = point_add(addend, addend, modulus);
    }

    res
}

// =====================================================================
// 3. Main Execution
// =====================================================================
fn main() {
    let modulus = U256(P);
    let g = Point {
        x: U256(G_X),
        y: U256(G_Y),
    };

    let phi = (1.0 + 5.0_f64.sqrt()) / 2.0;
    let golden_angle_deg = 360.0 * (1.0 - (1.0 / phi));
    let golden_angle_rad = golden_angle_deg * (PI / 180.0);

    println!("=====================================================================");
    println!("Golden Angle: {:.6}° ({:.6} rad)", golden_angle_deg, golden_angle_rad);
    println!("=====================================================================\n");

    // Arbitrary 256-bit Start and Stop boundaries
    let start_idx = U256::from_hex("0x00000000000000000000000000000000000000000000000000000000000186a0"); // 100,000
    let count = 5;

    println!("--- METHOD 1: Large Range Scalar Multiplication (k * G) ---");
    let mut current_idx = start_idx;
    for step in 0..count {
        let scalar_k = current_idx.mul_mod(&U256::from_u64(137507764), &modulus);
        let point = point_mul_256(g, &scalar_k, &modulus).expect("Valid point");

        // Verify y^2 == x^3 + 7 mod p
        let y_sq = point.y.mul_mod(&point.y, &modulus);
        let x_cb = point.x.mul_mod(&point.x, &modulus).mul_mod(&point.x, &modulus);
        let rhs = x_cb.add_mod(&U256::from_u64(7), &modulus);
        let is_valid = y_sq == rhs;

        println!("Step {:02} | Index Hex: 0x{:x}", step + 1, current_idx);
        println!("  Scalar k Hex: 0x{:x}", scalar_k);
        println!("  secp256k1 X : 0x{:x}", point.x);
        println!("  secp256k1 Y : 0x{:x}", point.y);
        println!("  Curve Valid : {}\n", is_valid);

        current_idx = current_idx.add_unbounded(&U256::from_u64(1));
    }

    println!("--- METHOD 2: Direct X Candidate Validation for Large X ---");
    let mut candidate_x = U256::from_hex("0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798"); // Generator X
    for step in 11111..=11122 {
        let x_cb = candidate_x.mul_mod(&candidate_x, &modulus).mul_mod(&candidate_x, &modulus);
        let rhs = x_cb.add_mod(&U256::from_u64(7), &modulus);

        if let Some(y) = rhs.sqrt_mod(&modulus) {
            println!("Valid Candidate #{}", step);
            println!("  X: 0x{:x}", candidate_x);
            println!("  Y: 0x{:x}\n", y);
        }
        candidate_x = candidate_x.add_unbounded(&U256::from_u64(1));
    }
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=d2800fe44c8a8d4374d5fc45cf98d22a