Synthetic benchmark from long gemini session for >170 TFLOPS FP8

benchmark_fp8_ptx.cu

#include <iostream>
#include <cstdint>
#include <cuda_runtime.h>

#define CUDA_CHECK(status) \
    do { \
        cudaError_t err = (status); \
        if (err != cudaSuccess) { \
            std::cerr << "[CUDA Error] " << cudaGetErrorString(err) \
                      << " (" << err << ") at line " << __LINE__ << std::endl; \
            exit(EXIT_FAILURE); \
        } \
    } while (0)

#define UNROLL_FACTOR 32

__global__ void __launch_bounds__(256, 2) fp8_ptx_peak_kernel_optimized(int64_t iterations) {
    uint32_t a[4] = {0x3c003c00, 0x3c003c00, 0x3c003c00, 0x3c003c00};
    uint32_t b[2] = {0x3c003c00, 0x3c003c00};
    
    // 4 independent sets of accumulators to break latency dependency chain
    float c0[4] = {0.0f, 0.0f, 0.0f, 0.0f};
    float c1[4] = {0.0f, 0.0f, 0.0f, 0.0f};
    float c2[4] = {0.0f, 0.0f, 0.0f, 0.0f};
    float c3[4] = {0.0f, 0.0f, 0.0f, 0.0f};

    for (int64_t i = 0; i < iterations; ++i) {
        #pragma unroll
        for (int u = 0; u < UNROLL_FACTOR; ++u) {
            asm volatile (
                "mma.sync.aligned.kind::f8f6f4.m16n8k32.row.col.f32.e4m3.e4m3.f32 {%0,%1,%2,%3}, {%4,%5,%6,%7}, {%8,%9}, {%0,%1,%2,%3};\n"
                "mma.sync.aligned.kind::f8f6f4.m16n8k32.row.col.f32.e4m3.e4m3.f32 {%10,%11,%12,%13}, {%4,%5,%6,%7}, {%8,%9}, {%10,%11,%12,%13};\n"
                "mma.sync.aligned.kind::f8f6f4.m16n8k32.row.col.f32.e4m3.e4m3.f32 {%14,%15,%16,%17}, {%4,%5,%6,%7}, {%8,%9}, {%14,%15,%16,%17};\n"
                "mma.sync.aligned.kind::f8f6f4.m16n8k32.row.col.f32.e4m3.e4m3.f32 {%18,%19,%20,%21}, {%4,%5,%6,%7}, {%8,%9}, {%18,%19,%20,%21};\n"
                : "+f"(c0[0]), "+f"(c0[1]), "+f"(c0[2]), "+f"(c0[3]),
                  "+f"(c1[0]), "+f"(c1[1]), "+f"(c1[2]), "+f"(c1[3]),
                  "+f"(c2[0]), "+f"(c2[1]), "+f"(c2[2]), "+f"(c2[3]),
                  "+f"(c3[0]), "+f"(c3[1]), "+f"(c3[2]), "+f"(c3[3])
                : "r"(a[0]), "r"(a[1]), "r"(a[2]), "r"(a[3]),
                  "r"(b[0]), "r"(b[1])
            );
        }
    }

    if (threadIdx.x == 0 && c0[0] == 12345.0f) {
        printf("Sink: %f\n", c0[0] + c1[0] + c2[0] + c3[0]);
    }
}

int main() {
    CUDA_CHECK(cudaFree(0));

    int device = 0;
    cudaDeviceProp prop;
    CUDA_CHECK(cudaGetDeviceProperties(&prop, device));

    std::cout << "Benchmarking Device: " << prop.name << " (" << prop.multiProcessorCount << " SMs)" << std::endl;

    int threads_per_block = 256;
    int num_blocks = prop.multiProcessorCount * 8; // Higher occupancy
    int64_t iterations = 50000;

    // Warmup
    fp8_ptx_peak_kernel_optimized<<<num_blocks, threads_per_block>>>(iterations / 10);
    CUDA_CHECK(cudaDeviceSynchronize());

    cudaEvent_t start, stop;
    CUDA_CHECK(cudaEventCreate(&start));
    CUDA_CHECK(cudaEventCreate(&stop));

    CUDA_CHECK(cudaEventRecord(start));
    fp8_ptx_peak_kernel_optimized<<<num_blocks, threads_per_block>>>(iterations);
    CUDA_CHECK(cudaEventRecord(stop));
    CUDA_CHECK(cudaEventSynchronize(stop));

    float ms = 0.0f;
    CUDA_CHECK(cudaEventElapsedTime(&ms, start, stop));

    int total_warps = (num_blocks * threads_per_block) / 32;
    // 4 MMA instructions per unroll loop step
    double total_mma_ops = (double)total_warps * iterations * UNROLL_FACTOR * 4.0;
    double total_flops = total_mma_ops * 8192.0;

    double seconds = ms / 1000.0;
    double tflops = (total_flops / seconds) / 1e12;

    std::cout << "Execution Time: " << ms << " ms" << std::endl;
    std::cout << "Raw Peak FP8 Tensor Core Performance: " << tflops << " TFLOPS" << std::endl;

    CUDA_CHECK(cudaEventDestroy(start));
    CUDA_CHECK(cudaEventDestroy(stop));

    return 0;
}

Unrelated.

hermann@7600x:~/llama.cpp$ HIP_VISIBLE_DEVICES=0,1,2,3,4,5,6,7 ./build/bin/llama-cli
-m hf/BF16/Qwen3.8-27B-BF16-00001-of-00002.gguf
--no-mmap
-c 32768
-fa on
-sm layer
-ts 1,1,1,1,1,1,1,2
--cache-type-k f16
--cache-type-v f16
-ngl 99
--jinja
-p "Hello! Give me a summary of fast integer factorization techniques."

Loading model...

▄▄ ▄▄
██ ██
██ ██ ▀▀█▄ ███▄███▄ ▀▀█▄ ▄████ ████▄ ████▄
██ ██ ▄█▀██ ██ ██ ██ ▄█▀██ ██ ██ ██ ██ ██
██ ██ ▀█▄██ ██ ██ ██ ▀█▄██ ██ ▀████ ████▀ ████▀
██ ██
▀▀ ▀▀

build : b10489-169e4a7ff
model : hf/BF16/Qwen3.8-27B-BF16-00001-of-00002.gguf
ftype : BF16
modalities : text

available commands:
/exit or Ctrl+C stop or exit
/regen regenerate the last response
/clear clear the chat history
/read add a text file
/glob add text files using globbing pattern

Hello! Give me a summary of fast integer factorization techniques.

[Start thinking]

We need to respond to user: "Hello! Give me a summary of fast integer factorization techniques." Need final answer. Need summarize fast integer factorization techniques. Could include algorithms: trial division, Pollard rho, Pollard p-1, ECM, quadratic sieve, number field sieve, general number field sieve, special number field sieve, Coppersmith-Winograd? Also mention complexity, applicability, use in practice, maybe modern records. Need be accurate.

Need likely provide concise but detailed. User asks summary. We can organize by small/medium/large, deterministic vs probabilistic, algebraic number theory. Mention no known polynomial-time classical; quantum Shor polynomial time. Include bit complexity.

Let's craft. Need maybe mention factorization of smooth integers? "fast integer factorization techniques" maybe computational number theory.

Content:

• Problem: factor N into primes.
• Trial division: O(N^{1/2}) bit? Actually trial division up to sqrt(N) in bit length n: O(2^{n/2}/poly) not polynomial; only tiny.
• Fermat's method: finds factors close; O(|N-a^2|) iterations, useful if factors close.
• Pollard's rho: random walk, expected O(p^{1/2}) group operations where p smallest factor; good for factors up to ~40-50 bits? Actually p up to 10^12? Need phrase.
• Pollard p-1: if p-1 B-smooth, find p in O(B log N) operations; good when p-1 smooth.
• Elliptic Curve Method (ECM): finds small/medium prime factors (roughly 20-80 bits, record maybe 80-100 bits) expected O(exp(1/2 sqrt(ln p ln ln p))) group ops. Very fast for small factors; used before GNFS.
• Algebraic methods for large N:
  • Quadratic Sieve (QS): best for ~100-160 decimal digits? General number field sieve better beyond ~150 digits. Complexity subexponential: L_N[1/2, sqrt(2)] for QS? More precisely QS: exp((sqrt(2)+o(1)) sqrt(ln N ln ln N)).
  • Special Number Field Sieve (SNFS): for N with special form a^b ± c (small c), complexity L_N[1/3, (64/9)^{1/3}]? Actually SNFS exponent (64/9)^{1/3} ≈ 1.923, L[1/3,1.923]. GNFS: L_N[1/3, (64/9)^{1/3}] same for generic? Wait standard: GNFS and SNFS have L[1/3, (64/9)^{1/3}]? Special NFS can be faster with smaller constant; general NFS exponent same? Let's verify.

Number field sieve:
L_N[α,c] = exp((c+o(1))(ln N)^α (ln ln N)^{1-α}).
QS: α=1/2, c=sqrt(2) ≈1.414.
NFS: α=1/3, c=(64/9)^{1/3} ≈1.923. This is for both GNFS and SNFS? SNFS same asymptotic exponent but lower constant? I think SNFS complexity often stated exp((64/9)^{1/3} + o(1) (ln N)^{1/3} (ln ln N)^{2/3}) too. Special NFS may have lower constant depending on polynomial; but asymptotic same as GNFS? Some sources: SNFS L_N[1/3, (64/9)^{1/3}], GNFS L_N[1/3, (64/9)^{1/3}]? Yes. But special NFS often faster in practice by factor maybe 2-10, and can handle numbers like Mersenne (2^p-1) much larger.

• General Number Field Sieve: current fastest for large generic integers (hundreds digits). Steps: polynomial selection, sieving (smooth relations), linear algebra over GF(2), root extraction. Practical limits: 200+ decimal digits? As of 2020s factoring RSA-240 (795 bits ~ 239 decimal digits) in 2020? RSA-250? Need not specify. General 230 digits. Mention memory intensive.
• Special NFS: for numbers of form a^b ± c (Mersenne, Fermat? Fermat numbers F_n = 2^{2^n}+1 have special form, but huge; SNFS for Mersenne primes? Actually SNFS used for Mersenne composites? Yes N=2^p-1.
• Cramer's algorithm? Not common.
• Other: SQUFOF (Shanks's Square Forms Factorization) for 64-bit? Fast for small/medium.
• Dixon's method? predecessor.
• Self-initializing? Not needed.
• Algebraic number theory: Lenstra-Pomerance? Maybe ECM.
• Quantum: Shor's algorithm: polynomial time O(n^3) bit operations, exponential speedup, breaks RSA; not classically fast.
• Lattice/continued fractions? Continued fraction method: complexity exp(c sqrt(ln N ln ln N))? predecessor to QS. Maybe mention.
• Special cases: difference of squares, algebraic factorization, cyclotomic, Aurifeuillean? For specific forms.
• Also for integers with known smoothness: BSGS? No.
• Need maybe include "fast" in context: use multiple techniques: pre-factor small primes, Pollard rho/p-1/ECM, then QS/NFS.
• Could include table of technique, finds, complexity, use.

Need ensure not overstate. Let's think through complexities.

Definitions: bit length n = log2 N, decimal digits d ~ n/log2(10). Trial division to sqrt(N): O(sqrt N) time = exp(Theta(n)).
Fermat: if N = a^2 - b^2, factors a±b; number iterations ~ (p-q)^2/(4N)? If p and q close, fast. Complexity O(|p-q|^2/N) maybe; if factors within O(sqrt N) then okay.
Pollard rho: For smallest prime p, expected O(sqrt p) modular multiplications; memory O(1). Good up to p ~ 10^12-10^18 depending implementation.
Pollard p-1: Stage 1 O(B log N), stage 2 O(B' log N / ln B')? If p-1 B-smooth, find p. Good for p with smooth p-1.
ECM: For prime p, expected O(exp(1/2 sqrt(ln p ln ln p))) group ops with memory O(exp(1/4 sqrt...? Actually memory maybe less). Finds factors p up to about 60-80 decimal digits? Need careful: ECM can find 70-digit factors? The record? ECM has found factors with up to 77 decimal digits? As of 2020, ECM found 77-digit factors? Actually ECM can factor 70+ digit primes; used to remove small factors from 200-digit numbers. It is best for factors up to ~50-70 decimal digits? Let's phrase: very effective for factors up to a few tens of digits (often 20–80 decimal digits, depending on resources).
QS: factoring generic N with ~100-150 decimal digits. Complexity L[1/2, sqrt(2)].
NFS: best for large generic N, >150 digits. Complexity L[1/3, 1.923].
SNFS: for special form a^b ± c; same asymptotic but lower constant; can factor Mersenne/Fermat-like numbers much larger.
Coppersmith? There is Coppersmith's algorithm for finding small roots, not factorization? Could be used to factor if small factor? Not general.
Maybe mention "fast integer factorization" in cryptography: RSA security relies on hardness; best classical algorithms subexponential.

Potential issue: "fast" could be in programming contest: quick factorization for 64-bit? But user asks general. Provide summary.

Need maybe include practical pipeline:

1. Remove small primes (trial division / wheel).
2. Use Miller-Rabin primality test; if prime done.
3. Use Pollard rho, p-1, ECM for small factors.
4. If remaining composite large, use QS or NFS (depending size/form).
5. If special form, use algebraic factorization/SNFS.

Need maybe mention parallelism: NFS sieving linear algebra parallelizable.

Need maybe include examples of current limits: As of 2020s, GNFS can factor ~800-bit (240 decimal digit) integers with large clusters; SNFS can handle much larger Mersenne forms? But careful: Factoring Mersenne composites with SNFS maybe 1000+ bits? There are records: SNFS factored 1024-bit Mersenne? Not sure. General NFS record RSA-240 (795 bits). Special NFS for Mersenne? There is factorization of 1024-bit Mersenne? Actually Mersenne composites may be factored by SNFS. But avoid exact records.

Let's craft final with headings, table. Need be clear.

Potential complexities:

• L_N notation definition.
• For QS: L_N[1/2, sqrt(2)].
• For NFS: L_N[1/3, (64/9)^{1/3}].
• ECM: not L_N but in terms of p: O(exp(0.5 sqrt(log p log log p))).
• Pollard rho: O(sqrt p).
• Pollard p-1: O(B log N) if p-1 B-smooth.
• Trial division: O(N^{1/2}/poly) or exp(n/ln 2).
• Fermat: O(|p-q|^2/N) group? More exact: iterations ≈ (p-q)^2/(4N) if p<q? Let's derive: N=pq, a=ceil(sqrt N), b^2=a^2-N. If p and q close, a≈(p+q)/2. b=(q-p)/2. Number iterations from sqrt N to (p+q)/2 is ((p+q)^2/4 - pq)/2? (q-p)^2/(8)? Actually a0 = sqrt N ~ sqrt pq; a_target=(p+q)/2. Difference ≈ ((p+q)^2 - 4pq)/(4)?? Let's compute: ((p+q)^2/4 - pq) = (p^2+2pq+q^2-4pq)/4=(p-q)^2/4. That's a - sqrt N? Since sqrt N≈(p+q)/2 - (p-q)^2/(8(p+q))? Difference about (p-q)^2/(8N?) Hmm not needed. Just say fast when factors close.

Could include "SQUFOF" for 64-bit: often fastest for medium-sized factors under 64 bits? Complexity O(N^{1/4})? SQUFOF expected O(N^{1/4})? Actually SQUFOF finds factor p in O(sqrt p) too? It is a variant of Fermat, good for 32/64-bit. But maybe too much.

Need final answer likely: "Hello! Here's a summary..." Good.

Let's ensure no false claims:

• ECM expected complexity: O(e^(1/2 sqrt(ln p ln ln p))) modular operations; memory O(e^(1/4 sqrt(...)))? Actually ECM uses O(e^(1/4 sqrt(...))) memory? Not necessary.
• QS complexity: exp((sqrt(2)+o(1)) sqrt(ln N ln ln N)). Yes.
• NFS complexity: exp(((64/9)^(1/3)+o(1)) (ln N)^(1/3) (ln ln N)^(2/3)). Yes.
• For SNFS, complexity may be L_N[1/3, (64/9)^(1/3)] but with smaller constant; for Mersenne numbers there are optimized forms. Maybe say "asymptotically similar to GNFS but with a smaller constant and very efficient for certain forms." That's safe.
• "No known classical polynomial-time algorithm". Yes.
• "Shor's algorithm polynomial time". Yes.

Need maybe mention "fast" relative to size:

• < 64 bits: trial division, Pollard rho/SQUFOF.
• 64–128 bits: Pollard rho/ECM? Actually 128-bit semiprime with 64-bit factors: Pollard rho can do sqrt(2^64)=2^32 operations, feasible. ECM also.
• 128–256 bits: ECM for small factors, QS/NFS for full factorization. 1024-bit RSA requires NFS huge.

• 200 decimal digits: GNFS for generic.

Potential table columns: Method, best for, rough complexity/behavior, notes.

Let's craft final with enough detail but not too long. The desired oververbosity 9 means detailed. We can include "practical pipeline".

Need maybe mention "integer factorization techniques" could include "fast" for arbitrary precision in libraries: GMP, PARI, CADO-NFS, msieve. Could mention tools: yafu, msieve, CADO-NFS, PARI/GP, GMP-ECM, NTRU? Maybe optional.

Let's structure:

1. Intro and complexity notation.
2. Quick methods for small factors.
3. Sieving/large methods.
4. Special forms and quantum.
5. Practical choice/pipeline.
6. Table.

Need be precise with bit lengths:

• Pollard rho good for smallest prime factor p up to ~2^40? Actually 2^40 sqrt = 2^20 ~ million; 2^50 sqrt=2^25 ~33 million; 2^60 sqrt=2^30 ~1 billion maybe seconds; 2^64 sqrt=2^32 ~4 billion maybe minutes/hours. Good for 64-bit factors. But in practice optimized can find 2^50-2^60 quickly. Phrase: "often best for factors up to about 40–64 bits, depending on hardware".
• ECM best for factors up to ~70 decimal digits? 70 decimal digits ~233 bits. ECM can find 200-bit factors maybe with many curves. It is used for small factors of RSA-2048? For 2048-bit RSA, factors are 1024 bits, ECM not useful for full factorization but can find accidental small factors. The phrase "up to a few tens of decimal digits" (e.g., 20–70 digits) safe.
• QS best for numbers up to ~100-150 decimal digits. Actually QS can factor 100-digit easily, 150-digit possible but NFS better. Use "roughly 80–140 decimal digits" maybe.
• GNFS best for 150+ digits. "hundreds of decimal bits?" Need not exact.

Let's consider if user expects "fast integer factorization techniques" from algorithms class: maybe mention quadratic sieve, number field sieve, elliptic curve. We'll include.

Need maybe mention "smoothness" concept: methods find factors by discovering smooth values and relations.

Let's write final:

Let N be n-bit. A common measure is L_N[α,c]...

Then table.

Potential pitfalls:

• Pollard p-1 complexity stage 2: O(B' log N / log B')? Let's not over-specific.

• ECM complexity: maybe O(exp(1/2 sqrt(ln p ln ln p))) group operations per curve; to find a factor p, need some number of curves; heuristic.

• Fermat method: complexity O(sqrt N) worst-case, but fast if p and q close. It is not generally "fast" unless close.

• Trial division: if using precomputed primes up to x, finds small factors.

• SQUFOF: O(N^{1/4})? Let's verify. Shanks's square forms factorization has heuristic complexity O(N^{1/4})? For N with small factor p, complexity O(p^{1/2})? Actually SQUFOF is a square forms algorithm; expected O(N^{1/4}) to factor N? I recall SQUFOF is faster than Fermat and Pollard rho for 64-bit? It has heuristic O(N^{1/4}) = O(sqrt p) if p ~ sqrt N? If p is small, maybe O(p^{1/2})? Let's check: SQUFOF expected time O(N^{1/4}) to find a factor. For N ~ p^2, that's O(p^{1/2}), same as Pollard rho. Good. We can mention "often very fast for 32/64-bit integers".

• Continued fraction method: predecessor to QS, complexity exp(c sqrt(ln N ln ln N)) with larger constant than QS. Could mention as historical.

• Dixon's method: O(exp(1/2 sqrt(ln N ln ln N)))? Actually Dixon's random method has same complexity as QS? It was first subexponential? Let's not include.

• Algebraic number field sieve steps: polynomial selection, sieving, linear algebra, root extraction. Could mention.

• Special forms: cyclotomic factorization, Aurifeuillean, algebraic identities; e.g., a^n ± b^n.

• Quantum: Shor.

Need maybe mention "fast integer factorization" in cryptographic context: RSA key sizes. Could say "For RSA-sized numbers (2048-bit), classical factorization is infeasible with current GNFS; estimated resources enormous." Maybe not necessary but useful.

Let's craft final in a friendly tone.

Double-check complexities:
L_N[α,c] = exp((c+o(1)) (ln N)^α (ln ln N)^{1-α}). For QS α=1/2, c=√2. For NFS α=1/3, c=(64/9)^{1/3}. Good.
ECM: expected O(exp(1/2 sqrt(ln p ln ln p))) modular operations. Some sources: ECM complexity O(e^{(1/2+o(1))√(ln p ln ln p)}). Yes.
Pollard p-1: if p-1 is B-smooth, stage 1 O(B log N) modular exponentiations/multiplications. Stage 2 maybe O(B' log N / ln B'). Good.

Need maybe mention "probability" for Pollard rho/ECM; deterministic primality tests separate. Factorization algorithms often randomized; can fail but repeat.

Let's prepare final:

Hello! Here's a high-level summary...

Complexity notation...

1. Small-factor methods
- Trial division
- Fermat
- Pollard rho
- Pollard p-1
- SQUFOF
- ECM

2. General large-number methods
- Continued fraction (historical)
- Quadratic sieve
- General Number Field Sieve
- Special Number Field Sieve

3. Special algebraic forms
- cyclotomic, Aurifeuillean, etc.

4. Quantum
- Shor

Practical pipeline...
Table...

Need maybe avoid too much. But desired oververbosity high, so detailed.

Let's think of exact phrasing for SNFS: "SNFS applies when N = a^b ± c with small a,c (or related forms), e.g., Mersenne numbers 2^p - 1 or numbers close to a perfect power. It uses a simpler polynomial and can be much faster than GNFS for such N, but is not applicable to arbitrary RSA moduli." Good.

Could mention "GNFS can be parallelized, but linear algebra memory bottleneck".

Could include "Current classical frontier: factoring ~700–800 bit generic integers with GNFS is a major cluster computation; 1024+ bit RSA is infeasible." Is that accurate? RSA-240 795 bits factored in 2020. In 2025 maybe RSA-250? I think no. 829-bit? There may be new record? Let's be cautious: "around 800-bit generic integers have been factored". Good.

Need maybe mention "NFS is the algorithm behind RSA security estimates". Good.

Let's ensure not to imply SNFS asymptotically faster than GNFS in L exponent if not. We can say "same subexponential form but smaller constants and much easier polynomial selection". For Mersenne, specialized NFS can factor larger bit lengths than GNFS.

Potential addition: "For 32-bit integers, trial division up to 2^16 or Pollard rho enough; for 64-bit, Pollard rho/SQUFOF; for 128-bit semiprimes with 64-bit factors, Pollard rho feasible; for 256-bit, ECM/QS/NFS." Maybe include.

Need maybe mention "integer factorization vs primality testing". Could mention Miller-Rabin first.

Let's draft final with table. Ensure final answer only. Use markdown.

One more nuance: "fast integer factorization techniques" might ask for "summary" not exhaustive. We can keep around 1000-1500 words? Oververbosity 9 but not too huge. Let's aim ~1200-1600 words.

Let's formulate:

Let N be n-bit, n = log2 N.

Technique | What it finds | Heuristic/complexity | Use

Maybe table after prose.

Let's include "Smoothness" in QS/NFS: find many values x such that f(x) is B-smooth, build relations, solve linear system over GF(2), get square relation. For NFS, use number fields to reduce size of numbers being sieved.

ECM details: works on elliptic curves over Z/NZ; for a prime factor p, curve group order divisible by p with high probability; repeated multiplication collapses mod p, gcd reveals p. Good for small factors.

Pollard rho details: random map f(x)=x^2+c mod N; Floyd/Brent cycle detection; gcd(|x-y|, N). Good for small factors.

Pollard p-1 details: compute a^M mod N with M multiple of lcm(1..B); if p-1 divides M, gcd(a^M-1,N) yields p.

SQUFOF: continued fraction / square forms; low memory, fast for 64-bit.

Fermat: write N=a^2-b^2. Good if p and q close.

Quadratic sieve: choose m≈√N, sieve values m^2 - N for smoothness, linear algebra over GF(2), produce square congruence.

GNFS: choose polynomial f,g with common root mod N? More precisely f(a) ≡ 0 mod N; use norm forms in number field and integers to find smooth pairs. Sieve over two surfaces. Linear algebra. Root extraction.

Special NFS: for N = a^b ± c, choose f(x)=x^b ∓ c? Norm forms simpler.

Special algebraic factorization: if N has algebraic form, factor symbolically before numeric: x^n±y^n, cyclotomic polynomials, Aurifeuillean.

Quantum: Shor's algorithm finds order and factors in polynomial time; requires fault-tolerant quantum computer.

Practical pipeline:

if N small: trial division
Miller-Rabin
Pollard p-1/rho/SQUFOF
ECM for medium factors
if composite and large: QS if <=~100-140 digits; GNFS if larger generic; SNFS if special form

Need maybe mention "libraries: CADO-NFS, msieve, PARI/GP, yafu, GMP-ECM, NTL". Could include as note.

Let's write final. Ensure no analysis. final.
[End thinking]

Hello! Here’s a high-level summary of the main fast integer factorization techniques, roughly ordered from “small numbers / small factors” to “large cryptographic-sized numbers.”

---

1. Complexity notation

For large integers, factorization algorithms are usually described using the subexponential notation

[
L_N[\alpha, c] =
\exp\left((c+o(1))(\ln N)^\alpha (\ln \ln N)^{1-\alpha}\right).
]

A smaller (\alpha) is much better. The best classical general-purpose factorization algorithm, the Number Field Sieve, has

[
L_N[1/3, (64/9)^{1/3}],
]

which is subexponential but still far beyond polynomial time.

---

2. Small-factor and quick methods

These are useful before attempting a full large-scale factorization.

---

Trial division

Idea: Test divisibility by small primes: (2,3,5,7,\dots)

Complexity:
If you divide up to (\sqrt{N}), worst-case time is roughly

[
O(\sqrt{N})
]

or exponential in the bit-length of (N).

Use:
Good only for tiny integers, or for removing very small prime factors from larger numbers.

---

Fermat’s method

Idea: Write

[
N = a^2 - b^2 = (a-b)(a+b).
]

Start near (a = \lceil \sqrt{N} \rceil) and increase (a) until (a^2 - N) is a perfect square.

Complexity:
Worst case is poor, but it is very fast when the two factors are close together.

Use:
Useful if (N = pq) with (p \approx q). Not generally fast for arbitrary integers.

---

Pollard’s rho algorithm

Idea: Simulate a random walk modulo (N):

[
x_{i+1} = f(x_i) \pmod{N},
]

usually (f(x)=x^2+c). Detect a cycle using Floyd’s or Brent’s cycle-finding method. If (x \ne y \pmod N) but (x \equiv y \pmod p) for a prime factor (p), then

[
\gcd(x-y, N)
]

may reveal (p).

Complexity:
For a smallest prime factor (p), expected time is about

[
O(\sqrt{p})
]

modular operations.

Use:
Very effective for finding small or medium-sized prime factors, often up to around 40–64 bits, depending on implementation and hardware.

---

Pollard’s (p-1) method

Idea: If (p) is a prime factor of (N) and (p-1) is smooth, meaning its prime factors are all small, then for a suitable multiple (M) of (1,2,\dots,B),

[
a^M \equiv 1 \pmod p.
]

Then

[
\gcd(a^M - 1, N)
]

may reveal (p).

Complexity:
If (p-1) is (B)-smooth, roughly

[
O(B \log N)
]

modular multiplications/exponentiations in stage 1, with an optional stage 2 to extend the smoothness bound.

Use:
Fast when (p-1) has only small prime factors. Common as a quick pre-factorization step.

---

SQUFOF

SQUFOF stands for Shanks’s Square Forms Factorization.

Idea: A continued-fraction-based method related to Fermat’s method. It searches for a square form representation of (N).

Complexity:
Heuristic time is around

[
O(N^{1/4})
]

for general use, and very fast in practice for 32-bit and 64-bit integers.

Use:
Often one of the fastest methods for 64-bit integers, especially when Pollard rho is not needed.

---

Elliptic Curve Method, ECM

Idea: Use elliptic curves modulo (N). For a prime factor (p) of (N), with reasonable probability, the group order of a random elliptic curve modulo (p) is smooth enough that repeated point multiplication collapses modulo (p). Taking a gcd then reveals (p).

Complexity:
For a prime factor (p), heuristic expected cost is about

[
\exp\left(\frac12 \sqrt{\ln p \ln \ln p}\right)
]

group operations.

Use:
ECM is one of the best methods for finding medium-sized prime factors, often in the range of tens of decimal digits, e.g. 20–70 digit factors depending on resources. It is commonly used to remove small factors before running larger algorithms such as the Number Field Sieve.

---

3. General large-integer factorization

For large arbitrary integers, the main classical methods are sieve-based.

---

Continued Fraction Method

Idea: Use continued fractions of (\sqrt{N}) to find relations that produce a square congruence modulo (N).

Complexity:
Subexponential, similar in shape to the Quadratic Sieve but with worse constants.

Use:
Historically important, but mostly superseded by the Quadratic Sieve.

---

Quadratic Sieve, QS

Idea: Choose (m \approx \sqrt{N}). Sieve values of

[
m^2 - N
]

to find many values that are (B)-smooth, meaning they factor only over a small prime set. These smooth values give multiplicative relations. Combine them to create a square congruence:

[
x^2 \equiv y^2 \pmod N.
]

Then

[
\gcd(x-y, N)
]

may reveal a factor.

Complexity:

[
L_N[1/2, \sqrt{2}]

\exp\left((\sqrt{2}+o(1))\sqrt{\ln N \ln \ln N}\right).
]

Use:
The Quadratic Sieve is the standard method for medium-sized integers, often up to around 80–140 decimal digits, depending on resources. It was long the record holder and is still used for smaller large integers.

---

General Number Field Sieve, GNFS

Idea: The General Number Field Sieve is currently the fastest classical algorithm for factoring large arbitrary integers.

It uses algebraic number theory. Roughly:

1. Choose polynomials defining a number field.
2. Sieve for smooth relations in both an integer and a number-field setting.
3. Use linear algebra over (\mathbb{F}_2) to combine relations.
4. Produce a nontrivial square congruence modulo (N).
5. Extract a factor via a gcd.

Complexity:

[
L_N\left[1/3, (64/9)^{1/3}\right]

\exp\left(
\left((64/9)^{1/3}+o(1)\right)
(\ln N)^{1/3}(\ln \ln N)^{2/3}
\right).
]

Use:
GNFS is the main classical algorithm for factoring large generic integers, especially RSA-sized or larger numbers. Factoring around 700–800-bit generic integers is possible only with large distributed computing efforts.

Practical notes:

• Highly parallelizable during sieving.
• Memory-intensive during the linear algebra phase.
• The most important classical algorithm for RSA security estimates.

---

4. Special-form factorization

Some integers have algebraic structure that can be exploited.

---

Special Number Field Sieve, SNFS

Idea: If (N) has a special form, for example

[
N = a^b \pm c
]

with small (a) and (c), then the polynomial choice in the Number Field Sieve is much simpler.

Complexity:
Asymptotically similar to GNFS:

[
L_N\left[1/3, (64/9)^{1/3}\right],
]

but with smaller constants and often much faster in practice.

Use:
Especially useful for numbers like:

• Mersenne numbers: (2^p - 1)
• Fermat-like numbers
• Numbers close to a perfect power
• Certain cyclotomic forms

SNFS can factor special-form numbers much larger than arbitrary numbers of the same bit length.

---

Algebraic factorization

If (N) can be written in a special algebraic form, it may factor symbolically before any numerical factorization is attempted.

Examples:

[
x^n - y^n = (x-y)(x^{n-1}+x^{n-2}y+\cdots+y^{n-1}),
]

[
x^n + y^n
]

for odd (n),

and various cyclotomic or Aurifeuillean identities.

Use:
Very fast when applicable, but only for integers with exploitable algebraic structure.

---

5. Quantum factorization

Shor’s algorithm

Idea: Use a quantum computer to find the period of a function modulo (N), then derive a nontrivial square root of (1) modulo (N), giving a factor.

Complexity:
Polynomial in the bit-length of (N), roughly (O(n^3)) with standard implementations, up to constants and circuit overhead.

Use:
Shor’s algorithm would break RSA and many other public-key cryptosystems, but requires a large, fault-tolerant quantum computer. It is not currently practical at cryptographic scale.

---

6. Practical factorization pipeline

In practice, one usually tries methods in order of increasing cost:

1. Trial division
   Remove very small prime factors.

2. Primality test
   Use Miller–Rabin, AKS, BPSW, etc., to check whether the number is prime.

3. Quick algebraic checks
   Check for perfect powers, cyclotomic forms, Fermat differences, etc.

4. Pollard’s rho / SQUFOF
   Find small-to-medium factors efficiently.

5. Pollard (p-1)
   Useful if (p-1) is likely smooth.

6. Elliptic Curve Method
   Find medium-sized prime factors.

7. Quadratic Sieve
   Factor medium-sized arbitrary integers.

8. General Number Field Sieve
   Factor large arbitrary integers.

9. Special Number Field Sieve
   Use if the integer has special algebraic form.

10. Quantum, if available
    Shor’s algorithm is polynomial-time but not currently practical at scale.

---

7. Quick comparison table

Method	Best for	Approximate behavior
Trial division	Very small factors	(O(\sqrt N)) worst case
Fermat	Close factors	Fast if (p \approx q)
Pollard rho	Small/medium prime factors	(O(\sqrt p)) for smallest factor (p)
Pollard (p-1)	Factors with smooth (p-1)	Fast if (p-1) is smooth
SQUFOF	32/64-bit integers	Very fast in practice
ECM	Medium prime factors, tens of digits	(\exp(0.5\sqrt{\ln p \ln \ln p}))
Continued Fraction	Medium integers, historical	Subexponential
Quadratic Sieve	~80–140 digit arbitrary integers	(L_N[1/2,\sqrt2])
GNFS	Large arbitrary integers	(L_N[1/3,(64/9)^{1/3}])
SNFS	Special-form integers	Similar to GNFS, often much faster in practice
Shor’s algorithm	Quantum setting	Polynomial time classically infeasible

---

Bottom line

For small integers, use trial division, Pollard rho, SQUFOF, or Fermat.
For medium-sized factors, ECM is often the workhorse.
For large arbitrary integers, the General Number Field Sieve is the current classical champion.
For special forms, the Special Number Field Sieve or algebraic identities can be dramatically faster.
And for the quantum future, Shor’s algorithm is the theoretical polynomial-time method.

[ Prompt: 23.2 t/s | Generation: 9.6 t/s ]