E051: Semiprimes: balanced vs. unbalanced factorization timing

Preview figure for E051
Preview figure for E051

Tags: number-theory, quantitative-exploration, visualization, factorization, semiprime See: Valid Tags.

Highlights

  • Generates small semiprimes \(n=pq\) in balanced and unbalanced regimes.

  • Factors them using trial division + Pollard’s rho and records timings.

  • Visualizes time distributions to make “balanced is harder” tangible.

Goal

Compare how factorization difficulty changes when one prime factor is much smaller than the other.

Background (quick refresher)

Research question

For semiprimes of similar overall size, how does Pollard-rho timing differ between balanced \((p\approx q)\) and unbalanced \((p\ll q)\) cases?

Experiment design

  • Generate balanced semiprimes with roughly equal factor bit lengths.

  • Generate unbalanced semiprimes with a fixed small factor size.

  • Factor each using trial division pre-pass + Pollard’s rho, measuring wall-clock time.

  • Plot boxplots and a size-vs-time scatter.

Reproducibility

  • params.json records the run settings.

  • report.md summarizes the key findings.

  • figures/*.png contains the plots for the run.

Interpreting the results

  • Timings are noisy: random instance structure matters a lot at this size range.

  • The trend should still show unbalanced instances often factoring faster (small factor is easier to find).

  • This is an educational-scale experiment, not a cryptographic benchmark.

Published run snapshot

If this experiment is included in the docs gallery, include the published snapshot (report + params).

Parameters

  • sample_count: 24

  • balanced_bits: 44

  • small_factor_bits: 16

  • trial_division_bound: 2000

Summary

  • balanced median time: 0.000874s

  • unbalanced median time: 0.000167s

Samples (first 10)

category

n

p

q

time (s)

balanced

10224642949621

3203503

3191707

0.001547

balanced

12056190493199

3746843

3217693

0.001153

balanced

10809763013969

3214223

3363103

0.000652

balanced

8179752869357

3696163

2213039

0.000886

balanced

9425664304583

3074779

3065477

0.000645

balanced

8405168684519

2187287

3842737

0.000957

balanced

4970172113219

2333939

2129521

0.000170

balanced

11418890464403

2893439

3946477

0.000101

balanced

6511871939171

2301829

2828999

0.000162

balanced

6363658603031

2811649

2263319

0.000877

unbalanced

8129387573543

56681

143423503

0.000348

unbalanced

12416116674211

58771

211262641

0.000130

unbalanced

8269233337793

33721

245225033

0.000070

unbalanced

7449408569203

45083

165237641

0.000094

unbalanced

6463784298977

44623

144853199

0.000140

unbalanced

5067033575867

33457

151449131

0.000276

unbalanced

9340248965111

49157

190008523

0.000177

unbalanced

7151136875947

45823

156059989

0.000106

unbalanced

8838375880759

51169

172729111

0.000247

unbalanced

12038405385443

61651

195266993

0.000152
params.json (snapshot)
{
  "balanced_bits": 44,
  "mr_bases": [
    2,
    3,
    5,
    7,
    11,
    13,
    17
  ],
  "sample_count": 24,
  "small_factor_bits": 16,
  "trial_division_bound": 2000
}

References

See Rivest et al. [1978], The OEIS Foundation Inc. [2025].