The Number Field Sieve

Every time you open a website over HTTPS, your browser and the server agree on a secret using RSA or a cousin — a system whose security rests on one ancient question: given a huge number $N$, can you find its prime factors?

For centuries that question seemed impenetrable. Then, starting in the 1970s, a series of increasingly clever sieves chipped away at it — until 1990, when Arjen Lenstra, Hendrik Lenstra Jr., Mark Manasse and John Pollard published the Number Field Sieve (NFS): the first factoring algorithm to break the exponential barrier and enter the world of sub-exponential time.

The NFS is the reason key lengths in RSA grew from 512 bits to 1024 and then to 2048. It is the algorithm that shattered every factoring record for composites over roughly 100 digits — and it is still the fastest classical method we know today. Yet RSA-2048 remains unbroken. Understanding why reveals a profound gap between "faster than brute force" and "actually fast enough."

The algorithm's status is open — no one has proved it is optimal, no one has found something fundamentally faster classically, and the problem it attacks (integer factoring) has no known proof that it is hard. It sits in a fascinating grey zone: faster than anything else we have, yet still hopeless against the keys protecting your data.

The Number Field Sieve's secret weapon is smooth numbers — integers whose prime factors are all small. The sieve step scans a huge range of candidates and keeps only those that factor entirely over a factor base of small primes (up to bound $B$). Those smooth values become rows in a giant matrix; when enough rows are collected, linear algebra over $\mathbb{F}_2$ spits out a factorization.

<p class="hint">The NFS sieve step hunts for <b>B-smooth numbers</b> — integers whose largest prime factor is ≤ B. Drag the slider to change B and see how many of the first 200 positive integers qualify. More smooth numbers = more "relations" to feed the linear-algebra step.</p>
<div class="controls">
  <label for="bSlider">Smoothness bound B = <strong id="bVal">20</strong></label>
  <input id="bSlider" type="range" min="2" max="97" value="20" step="1">
</div>
<div class="stats" id="stats"></div>
<div id="grid" class="grid"></div>
<div class="btns">
  <button id="btnFactor" type="button">Factor a highlighted number</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<div class="output" id="output"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; flex-direction: column; gap: .3rem; margin-bottom: .6rem; }
.controls label { font-size: .92rem; font-weight: 600; }
input[type=range] { width: 100%; accent-color: #1d3557; }
.stats { font-size: .9rem; margin-bottom: .6rem; color: #1d3557; font-weight: 700; min-height: 1.3em; }
.grid { display: grid; grid-template-columns: repeat(20, 1fr); gap: 2px; margin-bottom: .7rem; }
.cell {
  aspect-ratio: 1;
  display: flex; align-items: center; justify-content: center;
  font-size: .62rem; font-weight: 700; border-radius: 3px;
  cursor: pointer; user-select: none; transition: background .12s;
  border: 1px solid transparent;
}
.cell.smooth { background: #1d3557; color: #fff; }
.cell.rough  { background: #dde3e9; color: #888; }
.cell.selected { outline: 2.5px solid #e63946; outline-offset: 1px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.output { font-size: .88rem; min-height: 1.4em; font-family: ui-monospace, monospace; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Demo: B-smooth number sieve — the first harvesting step in the Number Field Sieve.
// A number n is B-smooth if every prime factor of n is <= B.
// We trial-divide n by primes up to B; if the remainder is 1, n is B-smooth.

const LIMIT = 200;

// Sieve of Eratosthenes up to LIMIT to get small primes
function sievePrimes(max) {
  const sieve = new Uint8Array(max + 1).fill(1);
  sieve[0] = sieve[1] = 0;
  for (let i = 2; i * i <= max; i++) {
    if (sieve[i]) for (let j = i * i; j <= max; j += i) sieve[j] = 0;
  }
  return Array.from({ length: max + 1 }, (_, i) => i).filter(i => sieve[i]);
}

const ALL_PRIMES = sievePrimes(LIMIT);

// Returns true if n is B-smooth (all prime factors <= B)
function isSmooth(n, B) {
  let x = n;
  for (const p of ALL_PRIMES) {
    if (p > B) break;
    while (x % p === 0) x = Math.floor(x / p);
  }
  return x === 1;
}

// Returns the prime factorization of n as a string
function factorize(n) {
  const factors = [];
  let x = n;
  for (const p of ALL_PRIMES) {
    if (p * p > x) break;
    let exp = 0;
    while (x % p === 0) { x = Math.floor(x / p); exp++; }
    if (exp > 0) factors.push(exp === 1 ? `${p}` : `${p}^${exp}`);
  }
  if (x > 1) factors.push(`${x}`);
  return factors.join(' × ');
}

let B = 20;
let selected = null;

const slider  = document.getElementById('bSlider');
const bVal    = document.getElementById('bVal');
const grid    = document.getElementById('grid');
const stats   = document.getElementById('stats');
const output  = document.getElementById('output');

function render() {
  bVal.textContent = B;
  grid.innerHTML = '';
  let smoothCount = 0;

  for (let n = 1; n <= LIMIT; n++) {
    const smooth = isSmooth(n, B);
    if (smooth) smoothCount++;

    const cell = document.createElement('div');
    cell.className = 'cell ' + (smooth ? 'smooth' : 'rough');
    if (n === selected) cell.classList.add('selected');
    cell.title = n;
    cell.textContent = n;
    cell.addEventListener('click', () => {
      selected = (selected === n) ? null : n;
      render();
      if (selected !== null) showFactor(selected);
      else output.textContent = '';
    });
    grid.appendChild(cell);
  }

  const pct = ((smoothCount / LIMIT) * 100).toFixed(1);
  stats.textContent =
    fmt('%smoothCount% / %LIMIT% numbers are %B%-smooth  (%pct%%)', { smoothCount: smoothCount, LIMIT: LIMIT, B: B, pct: pct });
}

function showFactor(n) {
  const smooth = isSmooth(n, B);
  const fact = factorize(n);
  const largest = Math.max(...fact.split(' × ').map(f => {
    const base = parseInt(f.split('^')[0]);
    return isNaN(base) ? 1 : base;
  }));
  output.textContent = fmt('%n% = %fact%  →  largest prime factor: %largest%  %v%', { n: n, fact: fact, largest: largest, v: smooth ? `✓ ${B}-smooth` : `✗ not ${B}-smooth (${largest} > ${B})` });
}

slider.addEventListener('input', () => {
  B = parseInt(slider.value);
  render();
  if (selected !== null) showFactor(selected);
});

document.getElementById('btnFactor').addEventListener('click', () => {
  // Pick a random smooth number to highlight
  const smoothNums = Array.from({ length: LIMIT }, (_, i) => i + 1)
    .filter(n => isSmooth(n, B));
  if (smoothNums.length === 0) {
    output.textContent = 'No B-smooth numbers found. Try increasing B.';
    return;
  }
  selected = smoothNums[Math.floor(Math.random() * smoothNums.length)];
  render();
  showFactor(selected);
});

document.getElementById('btnReset').addEventListener('click', () => {
  selected = null;
  output.textContent = '';
  render();
});

render();

<p class="hint">The NFS sieve step hunts for <b>B-smooth numbers</b> — integers whose largest prime factor is ≤ B. Drag the slider to change B and see how many of the first 200 positive integers qualify. More smooth numbers = more "relations" to feed the linear-algebra step.</p>
<div class="controls">
  <label for="bSlider">Smoothness bound B = <strong id="bVal">20</strong></label>
  <input id="bSlider" type="range" min="2" max="97" value="20" step="1">
</div>
<div class="stats" id="stats"></div>
<div id="grid" class="grid"></div>
<div class="btns">
  <button id="btnFactor" type="button">Factor a highlighted number</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<div class="output" id="output"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; flex-direction: column; gap: .3rem; margin-bottom: .6rem; }
.controls label { font-size: .92rem; font-weight: 600; }
input[type=range] { width: 100%; accent-color: #1d3557; }
.stats { font-size: .9rem; margin-bottom: .6rem; color: #1d3557; font-weight: 700; min-height: 1.3em; }
.grid { display: grid; grid-template-columns: repeat(20, 1fr); gap: 2px; margin-bottom: .7rem; }
.cell {
  aspect-ratio: 1;
  display: flex; align-items: center; justify-content: center;
  font-size: .62rem; font-weight: 700; border-radius: 3px;
  cursor: pointer; user-select: none; transition: background .12s;
  border: 1px solid transparent;
}
.cell.smooth { background: #1d3557; color: #fff; }
.cell.rough  { background: #dde3e9; color: #888; }
.cell.selected { outline: 2.5px solid #e63946; outline-offset: 1px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.output { font-size: .88rem; min-height: 1.4em; font-family: ui-monospace, monospace; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Demo: B-smooth number sieve — the first harvesting step in the Number Field Sieve.
// A number n is B-smooth if every prime factor of n is <= B.
// We trial-divide n by primes up to B; if the remainder is 1, n is B-smooth.

const LIMIT = 200;

// Sieve of Eratosthenes up to LIMIT to get small primes
function sievePrimes(max) {
  const sieve = new Uint8Array(max + 1).fill(1);
  sieve[0] = sieve[1] = 0;
  for (let i = 2; i * i <= max; i++) {
    if (sieve[i]) for (let j = i * i; j <= max; j += i) sieve[j] = 0;
  }
  return Array.from({ length: max + 1 }, (_, i) => i).filter(i => sieve[i]);
}

const ALL_PRIMES = sievePrimes(LIMIT);

// Returns true if n is B-smooth (all prime factors <= B)
function isSmooth(n, B) {
  let x = n;
  for (const p of ALL_PRIMES) {
    if (p > B) break;
    while (x % p === 0) x = Math.floor(x / p);
  }
  return x === 1;
}

// Returns the prime factorization of n as a string
function factorize(n) {
  const factors = [];
  let x = n;
  for (const p of ALL_PRIMES) {
    if (p * p > x) break;
    let exp = 0;
    while (x % p === 0) { x = Math.floor(x / p); exp++; }
    if (exp > 0) factors.push(exp === 1 ? `${p}` : `${p}^${exp}`);
  }
  if (x > 1) factors.push(`${x}`);
  return factors.join(' × ');
}

let B = 20;
let selected = null;

const slider  = document.getElementById('bSlider');
const bVal    = document.getElementById('bVal');
const grid    = document.getElementById('grid');
const stats   = document.getElementById('stats');
const output  = document.getElementById('output');

function render() {
  bVal.textContent = B;
  grid.innerHTML = '';
  let smoothCount = 0;

  for (let n = 1; n <= LIMIT; n++) {
    const smooth = isSmooth(n, B);
    if (smooth) smoothCount++;

    const cell = document.createElement('div');
    cell.className = 'cell ' + (smooth ? 'smooth' : 'rough');
    if (n === selected) cell.classList.add('selected');
    cell.title = n;
    cell.textContent = n;
    cell.addEventListener('click', () => {
      selected = (selected === n) ? null : n;
      render();
      if (selected !== null) showFactor(selected);
      else output.textContent = '';
    });
    grid.appendChild(cell);
  }

  const pct = ((smoothCount / LIMIT) * 100).toFixed(1);
  stats.textContent =
    fmt('%smoothCount% / %LIMIT% numbers are %B%-smooth  (%pct%%)', { smoothCount: smoothCount, LIMIT: LIMIT, B: B, pct: pct });
}

function showFactor(n) {
  const smooth = isSmooth(n, B);
  const fact = factorize(n);
  const largest = Math.max(...fact.split(' × ').map(f => {
    const base = parseInt(f.split('^')[0]);
    return isNaN(base) ? 1 : base;
  }));
  output.textContent = fmt('%n% = %fact%  →  largest prime factor: %largest%  %v%', { n: n, fact: fact, largest: largest, v: smooth ? `✓ ${B}-smooth` : `✗ not ${B}-smooth (${largest} > ${B})` });
}

slider.addEventListener('input', () => {
  B = parseInt(slider.value);
  render();
  if (selected !== null) showFactor(selected);
});

document.getElementById('btnFactor').addEventListener('click', () => {
  // Pick a random smooth number to highlight
  const smoothNums = Array.from({ length: LIMIT }, (_, i) => i + 1)
    .filter(n => isSmooth(n, B));
  if (smoothNums.length === 0) {
    output.textContent = 'No B-smooth numbers found. Try increasing B.';
    return;
  }
  selected = smoothNums[Math.floor(Math.random() * smoothNums.length)];
  render();
  showFactor(selected);
});

document.getElementById('btnReset').addEventListener('click', () => {
  selected = null;
  output.textContent = '';
  render();
});

render();

Slide the bound $B$ and watch how many of the first 200 integers are $B$-smooth. A tiny $B$ catches almost nothing; a large $B$ catches more numbers but makes the linear-algebra step slower. The real NFS tunes $B$ to the optimal value $e^{(\ln N)^{1/3}(\ln\ln N)^{2/3}}$ — the sweet spot that produces its famous sub-exponential running time.

This interplay between "collect enough smooth relations" and "keep the factor base manageable" is the core tension in every sieve-based factoring algorithm, from the ancient Quadratic Sieve to the NFS.

How fast is the Number Field Sieve? The answer requires a unit of measure invented just for factoring algorithms: L-notation.

$$L_N[\alpha, c] = e^{(c + o(1))(\ln N)^{\alpha}(\ln \ln N)^{1-\alpha}}$$

This interpolates between polynomial time ($\alpha = 0$) and fully exponential ($\alpha = 1$). The NFS achieves $\alpha = 1/3$, sitting tantalizingly between the two:

• Trial division is fully exponential: $L_N[1, 1] \approx \sqrt{N}$ operations.
• Quadratic Sieve (Dixon/Pomerance) reaches $L_N[1/2, 1]$ — a massive improvement, used to break RSA-512 in 1999.
• General NFS (GNFS) achieves $L_N[1/3, 1.923]$ — the current classical record, conjectured optimal among sieve methods.

The constant $c \approx 1.923$ in the GNFS exponent comes from optimizing the smoothness bound. No polynomial-time classical algorithm for factoring is known — and crucially, no one has proved that one cannot exist. Factoring is not known to be NP-complete either; it lives in a peculiar limbo inside NP $\cap$ co-NP but seemingly below NP-complete.

What this means for RSA-2048: A 2048-bit number has $\ln N \approx 1418$. Plugging into $L_N[1/3, 1.923]$ gives roughly $2^{112}$ operations — far beyond any classical computer. The best factoring record (RSA-250, 829 bits, 2020) required roughly 2700 CPU-core-years. RSA-2048 would need on the order of $10^{20}$ times more — an absurdity even at planetary scale. The only known threat is Shor's algorithm on a sufficiently large quantum computer, which runs in polynomial time $O((\log N)^3)$.

So the NFS holds a paradoxical place: it is the most powerful factoring tool in the classical world, yet it is precisely the NFS that tells us RSA-2048 is safe — because even the best attack fails by an incomprehensible margin.

The Number Field Sieve is not just an academic curiosity — it has direct, measurable consequences for every system that uses RSA or Diffie-Hellman:

• Key-size policy: NIST and other bodies publish minimum key lengths based on NFS projections. The jump from 1024-bit to 2048-bit RSA keys happened precisely because NFS made 1024-bit feel uncomfortably close. Current guidance pegs 2048 bits at roughly 112 bits of security through 2030.
• Factoring records: RSA-129 (1994, 17 years after its publication as a 40-year challenge), RSA-512 (1999), RSA-768 (2010), RSA-240 (2019) and RSA-250 (2020) all fell to variants of the NFS. Each record refined our understanding of where the next key-size threshold must lie.
• Discrete logarithm: the NFS generalizes to the Function Field Sieve and the Tower Number Field Sieve, breaking discrete-log problems over finite fields — the foundation of classic Diffie-Hellman. This forced the cryptographic community away from small-prime-field DH entirely.
• Post-quantum urgency: Shor's quantum algorithm factors in polynomial time. The NFS tells us exactly how large RSA keys must be to survive classical attacks; Shor tells us those same keys are worthless against a sufficiently large quantum computer. The combination is why NIST standardized new post-quantum algorithms in 2024.
• Factoring and P vs NP: if P = NP, factoring falls instantly (since it is in NP). The NFS's stubborn sub-exponential barrier is indirect evidence — though not proof — that factoring is genuinely hard and P ≠ NP.

The Number Field Sieve is a masterpiece of twentieth-century mathematics: it fused algebraic number theory, linear algebra over finite fields, and careful computational optimization to produce the fastest classical factoring algorithm known. It shattered records, reshaped key-size recommendations, and forced the cryptographic community to take quantum computing seriously.

Yet its greatest achievement may be the guarantee it provides. Because we understand the NFS so well — its running time, its constants, its limits — we can say with confidence that RSA-2048 is safe against any classical attack anyone can mount today or in the foreseeable future.

What the NFS cannot tell us is whether factoring is inherently hard. That question — whether there is some polynomial-time classical algorithm hiding undiscovered — remains open, intertwined with P vs NP and one of the deepest unsolved problems in mathematics and computer science.

The silence on the other side of that question is what keeps 2048-bit keys safe. For now.