CSC 482 - Homework 5 - Multithreaded RSA cracking Charleigh Roberts Language: Java (Oracle JDK 26.0.2.1), run from the command line Machine: AMD Ryzen 5 5600, 6 cores / 12 threads, 48 GB RAM, Windows 11 Pro (results\environment.txt) Starting code: Rsa.java from the course page (J. Hastings); the changes are marked // HW5 in Rsa.java. WHAT THE PROGRAM DOES Rsa.java makes two random primes p and q of the given bit length, multiplies them into the RSA modulus n, and then brute-forces a factor: it starts at sqrt(n) and steps upward through probable primes, splitting the search range in half over and over into ForkJoin tasks until each piece is small enough to loop through. The first thread to find a prime that divides n sets a shared "cont" flag so the other threads stop. The time measured is only the crack, not making the key. MY CHANGES (all marked // HW5 in Rsa.java) - main loops over the bit lengths (16..28 by default); the body of the old main is now crack() - every bit length is cracked 3 times and only the average prints, in the format the assignment asked for ("Average results:" then "bits ms" lines) - command line: java Rsa [min-bits] [max-bits] [runs]; runs=1 prints "Results:" instead - one ForkJoinPool for the whole program instead of a new one per key - the finder remembers the factor, and crack() checks that it divides n and equals p or q before the time is counted (carried over from HW3: verify every run) - the chatty output is commented out so only the two integers print - 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 (fjPool.shutdown()) - if a verification fails, the program prints CRACK FAILED and stops with exit status 1 instead of reporting that time HOW TO RUN javac Rsa.java (do this first: the .class files here are from JDK 26 and will not load on an older JRE; the source itself needs Java 9 or newer) java Rsa -> 16..28 bits, 3 runs each, prints averages (results\average-results-16-28.txt) java Rsa 16 28 1 -> 16..28 bits, one run each (results\results-16-28-single.txt) java Rsa 29 32 1 -> extra credit, one run each, about 67 minutes (results\extra-credit-29-32.txt) python make_plot.py results\average-results-16-28.txt [results\extra-credit-29-32.txt] -> results\HW5-plot.png (seconds), results\HW5-plot-log.png (log scale), results\HW5-plot-extra.png (everything on linear axes, extra credit only), and a growth table + estimates on the console RESULTS (Oct 21, 2026, nothing else running) Single run Average of 3 runs bits ms bits ms seconds 16 226 16 238 0.24 17 225 17 106 0.11 18 8 18 143 0.14 19 207 19 364 0.36 20 541 20 427 0.43 21 780 21 235 0.24 22 1168 22 1557 1.56 23 2682 23 3850 3.85 24 3159 24 4843 4.84 25 9964 25 5181 5.18 26 35066 26 18004 18.00 27 52923 27 37254 37.25 28 137682 28 82151 82.15 Whole run: single pass 4 min 5 s, three-run pass 7 min 44 s. The 28-bit average (82.2 s) landed almost on top of the assignment's example (82.3 s). Rsa.java's header comment was finished after the last run (saved 17:03, run ended 16:59), so on Oct 23 I reran this exact source to tie the timings to it: the 26/27/28-bit averages came out 20902 / 36018 / 78171 ms against the 18004 / 37254 / 82151 above (+16%, -3%, -5%). Extra credit, one run each (java Rsa 29 32 1, 66 min 46 s for all four): bits ms time 29 268824 4 min 29 s 30 424362 7 min 4 s 31 1045343 17 min 25 s 32 2267644 37 min 48 s DO THE RESULTS MATCH EXPECTATIONS? Yes, once the times are big enough to measure. Each extra bit doubles the size of the number range the search has to cover (from sqrt(n) up to max = 2^(bits+1)-1), so the time should roughly double per bit. Measured growth per bit (geometric mean of the ratios between neighbouring bit lengths, only counting pairs where both times are over 1 second): 22..28 bits, averages of 3 runs x1.94 29..32 bits, single runs x2.04 22..32 bits, all points chained x2.07 expected from the range doubling x2.00 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 (x1.94 = (82151/1557)^(1/6)). A least-squares line through log2(time) over the same points, which uses every point, gives x1.88, x2.07 and x2.10. Either way the answer is about x2. 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. Below about 1 second the numbers bounce around (18 bits took 8 ms in the single run, 17 bits took 225 ms) for two reasons 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 the range 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 (x3.3) compares an average with a single run. The same luck is why the ratios wander between x1.1 and x3.5 from one bit to the next even though the trend is x2. 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 x1.92 per bit instead of x2), 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 x2.00, so the doubling is still the expectation. Also, the original code searches up to max = 2^(bits+1)-1, while the larger factor q is always below 2^bits and sqrt(n) is at least 2^(bits-0.5), so at least the top three quarters of the range is work that can never succeed; the instructor's comment "It's likely overly large. Can it be smaller?" is pointing at this. I left max alone so the timings are for the code as given. EXTRA CREDIT - higher bit lengths Before running it I estimated 32 bits at about 39 minutes from the 28-bit average. Measured: 37 min 48 s, so the estimate was within 3%. (The honest footnote: that estimate used x2.3 per bit, which I later found included the noisy jump from 21 to 22 bits. With the clean x1.94 the estimate would have been 19 minutes, and the 28-to-32 stretch actually grew x2.29 per bit. Both are "about double" with one-run noise on top; the lesson is that a single run at each size is a wide error bar.) Estimates from the measured 32-bit time, at the chained rate unrounded, x2.072 per bit (x2.00 in brackets; with the rounded x2.07 the last row would read 928,000 years): 36 bits ~ 12 hours (10 hours) 40 bits ~ 9 days (7 days) 48 bits ~ 8 years (5 years) 64 bits ~ 950,000 years (310,000 years) That is the point of the assignment's RSA-challenge question: a 2048-bit key means each prime is 1024 bits, which is 992 more doublings past the 38-minute crack of a 32-bit prime. 2^992 is far more than the number of atoms in the universe, so no amount of hardware or patience gets there by brute force. A madlabs computer would not change that: the search is embarrassingly parallel, so k times the cores buys about log2(k) more bits in the same wall time (64 cores against this machine's 12 threads is about 2.4 bits), which is nothing against 992. A "lottery" of random guesses does no better: there are about 2^1013.5 primes with 1024 bits (2^1023 / ln 2^1024), so one random 1024-bit prime hits a particular factor one time in about 2^1013.5, and either of the two factors one time in about 2^1012.5. FILES Rsa.java the modified program make_plot.py the plot script (matplotlib + standard library) results\environment.txt CPU, RAM, OS, Java version results\results-16-28-single.txt "Results:" output, one run per bit length results\average-results-16-28.txt "Average results:" output, three runs per bit length results\run-16-28.log the console log of both runs with timestamps results\extra-credit-29-32.txt extra credit output, one run per bit length results\run-extra-29-32.log the console log of the extra credit run with timestamps results\HW5-plot.png bit length vs seconds, 16..28 (the required plot) results\HW5-plot-log.png 16..32 on a log y axis with a "doubles every bit" guide line results\HW5-plot-extra.png 16..32 on linear axes (the 16..28 points go flat next to 32) (the instructor's original is not in this folder; the changes against it are listed under MY CHANGES) SOURCES Rsa.java, CSC 482 course page (J. Hastings), johnhastings.herokuapp.com/classes/csc482/homework/Rsa.java CSC 482 notes: Euclidian Algorithm, Modular Arithmetic (unit 5) 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 AI: the loop, averaging, verification check, plot script and this write-up were done with Claude (Anthropic), per the course AI policy.