batch_add_affine.hpp

Go to the documentation of this file.

#ifndef SECP256K1_BATCH_ADD_AFFINE_HPP
#define SECP256K1_BATCH_ADD_AFFINE_HPP
 
#include "field.hpp"
#include <cstddef>
#include <vector>
 
namespace secp256k1::fast {
 
// ============================================================================
// AFFINE BATCH ADDITION -- Fastest CPU pipeline for sequential ECC search
// ============================================================================
//
// ## THE IDEA
// Given a base point P = (x_base, y_base) in AFFINE coordinates and N
// precomputed offsets T[0..N-1] = (x_i, y_i) also in AFFINE, compute
// all N sums: result[i] = P + T[i], returning AFFINE X-coordinates.
//
// ## WHY THIS IS FAST
// Standard Jacobian mixed-add: P += G costs 7M + 4S = ~354 ns/point
// with subsequent batch Z-inverse adding ~62 ns -> total ~463 ns/point.
//
// Affine batch add uses Montgomery batch inversion on dx values:
//   dx[i] = x_T[i] - x_base               -> 1 sub
//   batch_inverse(dx, N)                    -> 3(N-1) mul + 1 inv ~= 69 ns/pt
//   lambda[i]  = (y_T[i] - y_base) * dx_inv[i]  -> 1 mul
//   x3[i] = lambda[i]^2 - x_base - x_T[i]        -> 1 sqr + 2 sub
//   y3[i] = lambda[i] * (x_base - x3[i]) - y_base -> 2 mul + 1 sub
//
// Cost: ~6M + 1S per point ~= 150 ns/point -> 3x faster than Jacobian!
//
// ## USE CASE
// Satoshi puzzle / vanity search: walk through key range sequentially.
// Pre-compute T[i] = i*G in affine, then for each batch:
//   1. P_base = start_scalar * G (compute once per batch)
//   2. result[i] = P_base + T[i]  (affine batch add -- this function!)
//   3. Check result X-coordinates against target(s)
//   4. P_base += B*G (advance by batch size)
//
// ============================================================================
 
struct alignas(64) AffinePointCompact {
    FieldElement x;
    FieldElement y;
};
 
// ============================================================================
// Core batch addition API
// ============================================================================
 
void batch_add_affine_x(
    const FieldElement& base_x,
    const FieldElement& base_y,
    const AffinePointCompact* offsets,
    FieldElement* out_x,
    std::size_t count,
    std::vector<FieldElement>& scratch);
 
void batch_add_affine_xy(
    const FieldElement& base_x,
    const FieldElement& base_y,
    const AffinePointCompact* offsets,
    FieldElement* out_x,
    FieldElement* out_y,
    std::size_t count,
    std::vector<FieldElement>& scratch);
 
void batch_add_affine_x(
    const FieldElement& base_x,
    const FieldElement& base_y,
    const AffinePointCompact* offsets,
    FieldElement* out_x,
    std::size_t count);
 
// ============================================================================
// Precomputed Generator Table
// ============================================================================
 
std::vector<AffinePointCompact> precompute_g_multiples(std::size_t count);
 
std::vector<AffinePointCompact> precompute_point_multiples(
    const FieldElement& qx, const FieldElement& qy, std::size_t count);
 
// ============================================================================
// Full search pipeline helpers
// ============================================================================
 
void batch_add_affine_x_bidirectional(
    const FieldElement& base_x,
    const FieldElement& base_y,
    const AffinePointCompact* offsets_fwd,
    const AffinePointCompact* offsets_bwd,
    FieldElement* out_x_fwd,
    FieldElement* out_x_bwd,
    std::size_t count,
    std::vector<FieldElement>& scratch);
 
std::vector<AffinePointCompact> negate_affine_table(
    const AffinePointCompact* table, std::size_t count);
 
// ============================================================================
// Y-parity extraction (for compressed pubkey byte without full Y)
// ============================================================================
 
void batch_add_affine_x_with_parity(
    const FieldElement& base_x,
    const FieldElement& base_y,
    const AffinePointCompact* offsets,
    FieldElement* out_x,
    uint8_t* out_parity,
    std::size_t count,
    std::vector<FieldElement>& scratch);
 
} // namespace secp256k1::fast
 
#endif // SECP256K1_BATCH_ADD_AFFINE_HPP