Cracking RSA keys by brute force, on all twelve threads

The required plot: bit length of each prime on the x axis, seconds to find a factor on the y axis, each point the average of three runs. Below 22 bits the crack is over before the JIT has warmed up; above it the time roughly doubles with every bit.

Results

Measured October 21, 2026 with nothing else running. The program prints only two integers per line, the bit length and the milliseconds, exactly as the assignment asked; the full output files are linked at the bottom.

Environment

• CPU AMD Ryzen 5 5600, 6 cores / 12 threads, 3.5 GHz
• RAM 48 GB
• OS Windows 11 Pro
• Java Oracle JDK 26.0.2.1, plain javac / java, no flags
• Threads new ForkJoinPool(), so the pool's parallelism is Runtime.availableProcessors() = 12
• Timer System.currentTimeMillis around the crack only; making the key is not timed

Extra credit: 29 to 32 bits, and what comes after

The assignment's extra credit was to push the bit length higher and estimate the sizes that are out of reach. Four more lengths, one run each, took 67 minutes of wall-clock time with every core busy:

Estimating the rest

Chaining all the points from 22 to 32 bits, the time grows by ×2.07 per bit (geometric mean of the bit-to-bit ratios, counting only pairs where both times are over a second; unrounded, ×2.072). Starting from the measured 37.8 minutes at 32 bits, at the unrounded rate (with ×2.07 the 64-bit row would read 928,000 years):

Do the results match expectations?

Yes, once the times are big enough to measure. Each extra bit doubles the width of the range the search has to cover (from √n up to max = 2^(bits+1) − 1), so the time should roughly double per bit. Measured growth per bit:

A geometric mean of neighbouring ratios telescopes to the ratio of the two end points, so each figure really rests on its first and last time (×1.94 = (82151 / 1557)^1/6). A least-squares line through log₂(time) over the same points, which uses every point, gives ×1.88, ×2.07 and ×2.10. Either way the answer is about ×2.

On the log-scale plot the points from 22 bits up sit on a straight line next to the dotted “doubles every bit” guide, which is what this growth looks like.

Why the small sizes are noisy

Below about a second the numbers bounce around: 18 bits took 8 ms in the single run and 17 bits took 225 ms. Two reasons, both ones the assignment warned about. The first cracks also pay for class loading and the JIT compiler warming up. And where the factor happens to land in the range decides how much of it the threads burn through before one of them hits it. Averaging three runs smooths that but does not remove it: the single 28-bit run took 138 s and the three-run average was 82 s, and the jump from 28 to 29 bits (×3.3) compares an average with a single run. The same luck is why the bit-to-bit ratios wander between ×1.1 and ×3.5 even though the trend is ×2.

Why it is not exactly ×2

Two smaller effects, each about 4% per bit, pull in opposite directions and cancel. Primes get sparser as the numbers grow (the density falls as bits/(bits+1), which on its own would make the growth ×1.92 per bit instead of ×2), and each candidate costs more because BigInteger.nextProbablePrime runs a primality test on bigger numbers (the cost per candidate rises by about the same factor, (bits+1)/bits). Their product is ×2.00, so the doubling is still the expectation. There is also something the instructor flagged in a comment, “It's likely overly large. Can it be smaller?”: the code searches up to max = 2^(bits+1) − 1, while the larger factor q is always below 2^bits and √n is at least 2^bits−0.5, so at least the top three quarters of the range is work that can never succeed. I left max alone so these timings are for the code as given.

How the crack works

The program, Rsa.java from the course page, makes two random primes of the requested bit length with BigInteger.probablePrime, multiplies them into n, and then forgets them. The crack starts at n.sqrt() and walks upward through probable primes, because one of the two factors must be at or above √n. To use every core, the range is handed to a RecursiveAction that keeps cutting it in half, forking one half to the pool and computing the other itself, until a piece is under 1,000 wide, and then just loops through it. The thread that finds a divisor flips a shared flag, cont, guarded by static synchronized methods, and every other thread checks that flag each time round its loop and stops.

protected void compute() {
    BigInteger diff = max.subtract(min);
    if (diff.compareTo(THRESHOLD) < 0) {               // small enough: just loop through it
        BigInteger currentPrime = min;
        do {
            if (n.mod(currentPrime).equals(BigInteger.ZERO)) {
                endCont(currentPrime);                  // found it; tell every thread to stop
                break;
            }
            currentPrime = currentPrime.nextProbablePrime();
        } while (getCont() && currentPrime.compareTo(max) <= 0);
    }
    else if (getCont()) {                               // still searching: split in half
        BigInteger mid = (max.add(min)).divide(BigInteger.TWO);
        ForkJoinRsaTask taskA = new ForkJoinRsaTask(n, min, mid);
        ForkJoinRsaTask taskB = new ForkJoinRsaTask(n, mid.add(BigInteger.ONE), max);
        taskA.fork();                                   // hand one half to the pool
        taskB.compute();                                // do the other half ourselves
        taskA.join();
    }
}

The same divide-and-conquer shape as a multithreaded quicksort: fork one side, recurse on the other, join. The pool's work-stealing keeps all twelve threads fed, which is why the order the pieces get searched in, and so the time to the lucky hit, varies from run to run.

What I changed

Every change is marked // HW5 in the source. The thread coordination is the instructor's; I did not touch it.

• A loop over bit lengths. The body of the old main became a crack(bitLength, random, pool) method that returns the milliseconds, and main calls it for 16 through 28 bits (or whatever the command line says).
• Averaging. Each bit length is cracked three times and only the average prints, under Average results:; a run count of 1 prints Results: instead.
• One pool for the whole program instead of a new ForkJoinPool per key.
• Verify before trusting the time. The finder now remembers the factor as well as flipping the flag, and crack checks that it divides n and equals p or q before the time counts. Carried over from HW3: verify every run.
• Quiet output. The chatty prints are commented out so only the two integers print.
• Small housekeeping. The command line is checked (min-bits under 2, max-bits under min-bits, runs under 1, a non-number or more than three arguments print the usage line and exit); the pool is shut down when the loop is done; and a failed verification prints CRACK FAILED and stops the program with exit status 1 instead of reporting that time.

Usage: java Rsa for the assignment's run, java Rsa 16 28 1 for one run per length, java Rsa 29 32 1 for the extra credit.

Code and files

Also: environment.txt, the 16 to 28 run log, and make_plot.py. The starting point was Rsa.java from the CSC 482 course page (J. Hastings), kept unchanged apart from the marked lines.

Sources

• Rsa.java, CSC 482 course page (J. Hastings), johnhastings.herokuapp.com/classes/csc482/homework/Rsa.java
• CSC 482 unit 5 notes: Euclidian Algorithm, Modular Arithmetic
• Oracle Java docs: java.math.BigInteger (probablePrime, nextProbablePrime, sqrt), java.util.concurrent.ForkJoinPool and RecursiveAction
• RSA Factoring Challenge, en.wikipedia.org/wiki/RSA_Factoring_Challenge (RSA-250, 2020)
• AI: the loop, averaging, verification check, plot script, write-up and this page were done with Claude (Anthropic), per the course AI policy.