# mayiding/gnfs architecture

> Architecture diagram of the GitHub repository mayiding/gnfs, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-09-28). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/mayiding/gnfs
- Repository: https://github.com/mayiding/gnfs

## Overview

GNFS is a C++20 integer-factorization product with a CLI and a macOS Workbench. The main workflow accepts an integer, selects a factoring method, and returns factors; the GNFS route spans polynomial selection through square-root extraction. The README documents the adaptive trial-division, Pollard-rho, SIQS, and GNFS routes. The graph focuses on runtime architecture; unsampled implementation details are represented only where the README or sampled interfaces support them.

Main entry points: [`src/api/pipeline.cpp`](https://github.com/mayiding/gnfs/blob/main/src/api/pipeline.cpp) (GNFS Pipeline), [`src/api/factorizer.cpp`](https://github.com/mayiding/gnfs/blob/main/src/api/factorizer.cpp) (Factorizer API), [`src/cli/main.cpp`](https://github.com/mayiding/gnfs/blob/main/src/cli/main.cpp) (CLI), [`apps/macos/GNFSWorkbench/GNFSWorkbench`](https://github.com/mayiding/gnfs/tree/main/apps/macos/GNFSWorkbench/GNFSWorkbench) (macOS Workbench)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_entry["User Interfaces"]
  node_cli["CLI<br/>[main.cpp]"]
  node_workbench["macOS Workbench"]
end

subgraph group_dispatch["Method Dispatch"]
  node_factorizer["Factorizer API<br/>[factorizer.cpp]"]
  node_pipeline["GNFS Pipeline<br/>[pipeline.cpp]"]
  node_trial["Trial Division<br/>[trial_division.hpp]"]
  node_rho["Pollard Rho"]
  node_siqs["SIQS<br/>[siqs.hpp]"]
end

subgraph group_gnfs["GNFS Collection"]
  node_poly["Polynomial Selection"]
  node_factorbase["Factor Base<br/>[builder.cpp]"]
  node_sieve["Lattice Sieve<br/>[lattice_sieve.cpp]"]
  node_cofactor["Cofactorization<br/>[cofactorizer.hpp]"]
  node_relations["Relation Collection<br/>[collector.hpp]"]
end

subgraph group_solve["Relation Solving"]
  node_filter["Relation Reduction"]
  node_matrix["Matrix Construction<br/>[matrix_builder.cpp]"]
  node_linear["Linear Algebra<br/>[block_lanczos.hpp]"]
  node_sqrt["Square Roots<br/>[algebraic_sqrt.cpp]"]
end

subgraph group_support["Factorization Support"]
  node_result["Factor Result<br/>[result.hpp]"]
end

node_user(("User"))

node_user -->|"provides integer"| node_cli
node_cli -->|"runs pipeline"| node_pipeline
node_pipeline -->|"dispatches method"| node_factorizer
node_factorizer -->|"uses when selected"| node_trial
node_factorizer -->|"uses when selected"| node_rho
node_factorizer -->|"uses when selected"| node_siqs
node_factorizer -->|"uses for GNFS"| node_pipeline
node_pipeline -->|"selects polynomial"| node_poly
node_pipeline -->|"builds factor base"| node_factorbase
node_pipeline -->|"collects relations"| node_sieve
node_pipeline -->|"factors cofactors"| node_cofactor
node_pipeline -->|"gathers relations"| node_relations
node_pipeline -->|"reduces relations"| node_filter
node_pipeline -->|"builds matrix"| node_matrix
node_pipeline -->|"solves dependencies"| node_linear
node_pipeline -->|"extracts roots"| node_sqrt
node_pipeline -->|"returns factors"| node_result
node_user -->|"starts run"| node_workbench

click node_cli "https://github.com/mayiding/gnfs/blob/main/src/cli/main.cpp"
click node_workbench "https://github.com/mayiding/gnfs/tree/main/apps/macos/GNFSWorkbench/GNFSWorkbench"
click node_factorizer "https://github.com/mayiding/gnfs/blob/main/src/api/factorizer.cpp"
click node_pipeline "https://github.com/mayiding/gnfs/blob/main/src/api/pipeline.cpp"
click node_trial "https://github.com/mayiding/gnfs/blob/main/include/gnfs/cofactor/trial_division.hpp"
click node_rho "https://github.com/mayiding/gnfs/blob/main/include/gnfs/cofactor/brent_pollard_rho.hpp"
click node_siqs "https://github.com/mayiding/gnfs/blob/main/include/gnfs/siqs/siqs.hpp"
click node_poly "https://github.com/mayiding/gnfs/blob/main/include/gnfs/polynomial/selector_dispatch.hpp"
click node_factorbase "https://github.com/mayiding/gnfs/blob/main/src/factor_base/builder.cpp"
click node_sieve "https://github.com/mayiding/gnfs/blob/main/src/sieve/lattice_sieve.cpp"
click node_cofactor "https://github.com/mayiding/gnfs/blob/main/include/gnfs/cofactor/cofactorizer.hpp"
click node_relations "https://github.com/mayiding/gnfs/blob/main/include/gnfs/relation/collector.hpp"
click node_filter "https://github.com/mayiding/gnfs/blob/main/include/gnfs/relation/reduction_engine.hpp"
click node_matrix "https://github.com/mayiding/gnfs/blob/main/src/linalg/matrix_builder.cpp"
click node_linear "https://github.com/mayiding/gnfs/blob/main/include/gnfs/linalg/block_lanczos.hpp"
click node_sqrt "https://github.com/mayiding/gnfs/blob/main/src/sqrt/algebraic_sqrt.cpp"
click node_result "https://github.com/mayiding/gnfs/blob/main/include/gnfs/api/result.hpp"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_cli,node_workbench,node_user toneBlue
class node_factorizer,node_pipeline,node_trial,node_rho,node_siqs toneAmber
class node_poly,node_factorbase,node_sieve,node_cofactor,node_relations toneMint
class node_filter,node_matrix,node_linear,node_sqrt toneRose
class node_result toneIndigo
```

## Components

### User Interfaces

- [CLI](https://github.com/mayiding/gnfs/blob/main/src/cli/main.cpp): `src/cli/main.cpp`
- [macOS Workbench](https://github.com/mayiding/gnfs/tree/main/apps/macos/GNFSWorkbench/GNFSWorkbench): `apps/macos/GNFSWorkbench/GNFSWorkbench`

### Method Dispatch

- [Factorizer API](https://github.com/mayiding/gnfs/blob/main/src/api/factorizer.cpp): `src/api/factorizer.cpp`
- [GNFS Pipeline](https://github.com/mayiding/gnfs/blob/main/src/api/pipeline.cpp): `src/api/pipeline.cpp`
- [Trial Division](https://github.com/mayiding/gnfs/blob/main/include/gnfs/cofactor/trial_division.hpp): `include/gnfs/cofactor/trial_division.hpp`
- [Pollard Rho](https://github.com/mayiding/gnfs/blob/main/include/gnfs/cofactor/brent_pollard_rho.hpp): `include/gnfs/cofactor/brent_pollard_rho.hpp`
- [SIQS](https://github.com/mayiding/gnfs/blob/main/include/gnfs/siqs/siqs.hpp): `include/gnfs/siqs/siqs.hpp`

### GNFS Collection

- [Polynomial Selection](https://github.com/mayiding/gnfs/blob/main/include/gnfs/polynomial/selector_dispatch.hpp): `include/gnfs/polynomial/selector_dispatch.hpp`
- [Factor Base](https://github.com/mayiding/gnfs/blob/main/src/factor_base/builder.cpp): `src/factor_base/builder.cpp`
- [Lattice Sieve](https://github.com/mayiding/gnfs/blob/main/src/sieve/lattice_sieve.cpp): `src/sieve/lattice_sieve.cpp`
- [Cofactorization](https://github.com/mayiding/gnfs/blob/main/include/gnfs/cofactor/cofactorizer.hpp): `include/gnfs/cofactor/cofactorizer.hpp`
- [Relation Collection](https://github.com/mayiding/gnfs/blob/main/include/gnfs/relation/collector.hpp): `include/gnfs/relation/collector.hpp`

### Relation Solving

- [Relation Reduction](https://github.com/mayiding/gnfs/blob/main/include/gnfs/relation/reduction_engine.hpp): `include/gnfs/relation/reduction_engine.hpp`
- [Matrix Construction](https://github.com/mayiding/gnfs/blob/main/src/linalg/matrix_builder.cpp): `src/linalg/matrix_builder.cpp`
- [Linear Algebra](https://github.com/mayiding/gnfs/blob/main/include/gnfs/linalg/block_lanczos.hpp): `include/gnfs/linalg/block_lanczos.hpp`
- [Square Roots](https://github.com/mayiding/gnfs/blob/main/src/sqrt/algebraic_sqrt.cpp): `src/sqrt/algebraic_sqrt.cpp`

### Factorization Support

- [Factor Result](https://github.com/mayiding/gnfs/blob/main/include/gnfs/api/result.hpp): `include/gnfs/api/result.hpp`

### Other components

- **User**

## Connections

- User → CLI: provides integer
- CLI → GNFS Pipeline: runs pipeline
- GNFS Pipeline → Factorizer API: dispatches method
- Factorizer API → Trial Division: uses when selected
- Factorizer API → Pollard Rho: uses when selected
- Factorizer API → SIQS: uses when selected
- Factorizer API → GNFS Pipeline: uses for GNFS
- GNFS Pipeline → Polynomial Selection: selects polynomial
- GNFS Pipeline → Factor Base: builds factor base
- GNFS Pipeline → Lattice Sieve: collects relations
- GNFS Pipeline → Cofactorization: factors cofactors
- GNFS Pipeline → Relation Collection: gathers relations
- GNFS Pipeline → Relation Reduction: reduces relations
- GNFS Pipeline → Matrix Construction: builds matrix
- GNFS Pipeline → Linear Algebra: solves dependencies
- GNFS Pipeline → Square Roots: extracts roots
- GNFS Pipeline → Factor Result: returns factors
- User → macOS Workbench: starts run