I am fairly new to Julia. I am a retired Engineer/Computer Scientist that continues to be a hobby programmer. I particularly enjoy arbitrary precision math (computation of constants, Bernoulli numbers, prime factoring…). I maintain a set of such code using C/C++, Python, Go, Rust, Ruby, Swift and Julia. One of the key pieces of code missing from my code set is a decent Quadratic Sieve program native to Julia. I found one on Github but could not get it to run. Even if I did it is pretty basic. There is one post on this forum from 2018 on the subject that basically ended with if you want one write one. I recently have had some success in converting snippets between languages using AI language converters so I though why not try to convert a whole app. So I went looking for a candidate Quadratic Sieve application. I wanted one that was complete (many on Github end with an initial commit and never result in working code. I also wanted one fairly small and well organized. I also wanted to convert an application that uses gmplib mpz’s so that they can be mapped to Julia BigInt’s.
I found one such application. I set out to convert using AI. The first attempt ended with the AI in a forever “thinking” timeout. The second and third attempt resulted in code to slow to be used. The fourth attempt resulted in working code that is reasonably performant and surprisingly error free. After much testing and adding some features including automatic parameter generation, I have uploaded the code to Github.
The code runs, and produces factors for up to 100 digit numbers. Has been tested with RSA-100. The original code is written in Rust. The Julia code is about 2.5 times slower.
The main issue now is memory usage. I have 128G of memory on my laptop and the code will use it all plus some. During the RSA-100 factoring Julia consumed 155Gbytes!!! Running the Rust version with the same parameters it never used more than 1.2G. I have tried using the heap-size-hint and it helps some. Adding GC.gc() calls at a couple of locations in the sieving code dramatically lowers memory usage but in turns kills performance (up to 100x slower run performance). So the tradeoff is reasonable performance and let Julia consume all memory or try to limit memory usage and kill performance.
So at this point I am happy to donate some code to the Julia community but somewhat disappointed with the outcome.
Please note that I have gone line by line and compared the converted code to the original and it is very close to identical. I also ensured that mutating functions and variables were used when possible.
I hope that over time, users and developers will provide recommendations and insights for improvement.
bainv is a dense matrix indexed by factor-base position.
fdiv_ui is used for allocation-free modular reduction.
RSA-100 (100 digits):
The run was at about 594 MiB RSS and flat over its first ~7 min.
The projected total was about 15.7 h, so I killed it before it finished.
There is no final peak RSS, factorisation or time -l output for it.
Scale limit:
Yield falls steeply with size. It was 0.074 relations per polynomial at 60 digits and about 0.001 at 90.
The 90-digit projection is about 2 to 3 h.
Seven parameter variants (factor base, interval, eps, large-prime multiplier) all landed within a few percent of the existing tiers or were worse. This is a flat optimum, not a tuning gap.
The limiting factor is the sieve and trial-division implementation, not the parameters. I haven’t profiled it.
The 90-digit comparisons were run four at a time on one machine, so absolute ETAs include contention.
I haven’t compared 90- or 100-digit behaviour against main.
Memory was only measured to completion at 60 digits.
I’d be glad to make a pull request if that will be helpful.
The algorithm seems right, parameter tuning didn’t help, so that leaves data structure and implementation. Sonnet suggested
This branch’s data-structure changes cut the null-space step from 1.97 s to 0.05 s at 60 digits, about 40×. That’s how much headroom this code had when its representation was fixed.
The hot loop does BigInt arithmetic per sieve candidate (factorise_fast and the bmod calls). Production SIQS implementations avoid that by working in machine words and by recording which primes hit each sieve location.
Some of the likely gaps are algorithmic variations inside SIQS rather than pure tuning:
It uses single large-prime handling only, with no double large primes.
The 589,824-byte sieve interval is far larger than L1 cache, so it isn’t segmented into cache-sized blocks.
Candidate verification re-divides by the whole factor base instead of only the primes known to have hit.
Thanks for the Sonnet AI improvement suggestions. I would welcome a pull request. I am not that literate on how pull requests work and how to use them to create revisions but will learn.
I tried using Muse AI to request improvements. It suggested similar types of things that replaced BigInt usage in functions. But the code it developed made performance much worse or simply did not function.
The null space extraction function is for sure where dramatic improvement is likely to come. Look forward to seeing your code improvements. Thanks for taking your time to do this.
Just curious, do you have a paid plan to access AI code conversion/generation? I really wanted to convert FlintQS to Julia rather than the code base that I used. But I did it with a free account and did not have the token limit high enough to convert FlintQS. FlintQS on Github at:
It uses a Lanczos algorithm and is very fast. A later version is evidently used in Flint and Sagemath. I entertained a manual conversion from the C++ code to other languages like Julia but the code is pointer hell! A good AI conversion might work. I did not expect the Rust conversion I did to work as well as it did. I have not found a single bug in the conversion, including all the 0-based to 1-base conversion for array indexing. I was just amazed.
btw, I contacted the author of FlintQs (William Hart) and asked permission to convert to Julia and he replied with a yes. The converted code would probably need to be GPL licensed the same as FlintQs.
Yeah I read about Nemo.jl and it looks like a good package. Right now I am on a pure Julia kick. I am able to compile and run FlintQS using Xcode on a MacBook and MacOS but would like to have the FlintQS codebase running pure Julia code (and other languages like Rust). I enjoy the conversion process.
I had to take jobs as an AI trainer to support my token habit. Between my own subscriptions and client-provided accounts, I’m somewhere north of a billion, YTD.
The pull request is live. Rather than doing a merge, I’d just work from that fork separately.
RSA-896 was factorized last month: https://saweis.net/posts/rsa-896.html
The author used Claude to port existing factorization software to GPUs. Maybe it would be fun to try this with CUDA.jl.
I went and merged it. The results are very good. I just finished checking the 90 bit number. It factored in 46 min 44 seconds. The null space extraction was less than 10 seconds which is very, very good. Memory peaked at about 700Mbytes, also very good.
I wouldn’t know where to begin and certainly don’t have access to the resources needed. Quite impressive though. The pace in which AI is evolving and making it’s mark is like nothing I have experienced in my almost 50 years experience in the computer world.
I compared elapsed times with a 60 digit test number that I use. What I got was 16.5 seconds for the Primes mpqs and 2.5 seconds for this code.
From an initial browsing of the functions there is a lot of similarity between the two code bases. Since mine is a conversion from a Rust program you will see a lot of u32 variables. Both code bases look to use BigInts. I suspect a more performant path would be to use a fixed width type from another package, something like a u512. I know of one Rust program that is designed that way. It is also multi-threaded and blistering fast. I have factored RSA-120 with it. Link below:
Anyway, I am just getting started with this code and am no way confident with it. I am at the point where I believe I have eliminated hangs and crashes but suspect there is some dead code paths and inefficiencies left to be resolved. The most troublesome function is the generate_a function. I was getting hangs with smaller input which I have hopefully resolved. I am still not confident in the logic within this function.
In any case, I just do this as a hobby and have no intent of supporting the masses like you guys are doing with Primes. If you find anything valuable in my code base please don’t hesitate to use it.
Looks like I need to delete the GitHub repository. I misunderstood how licensing worked. The repository that I converted from has no licensing attached. I assumed that there was no restrictions. But after searching on the web that is not the case. If there is no license then you have to rights to access. Very confusing. I have found no way to contact the author except to post an issue. I posted an issue and requested that a license be applied. It has been a week with no response. For now, I think I need to remove the repository until I can hear from the author. Sorry if I have caused anyone trouble doing this.
By making a repository public, you grant other Users a nonexclusive, worldwide license to use, display, perform and reproduce (by forking) Your Content through the Service as permitted by GitHub’s functionality. You may grant additional rights by adopting a license.
I’ll give you the lawyer answer: it depends. In this case it depends on the construction of the verb “to use.” On the first of many hands, it might be construed in connection with the activities mentioned in the TOS, such as forking a repository. It doesn’t likely include running the code if “perform” is understood in that sense, which would already cover that. On another hand, California law favors a broad interpretation of the term if not expressly agreed. Zooming out, copyright law protects expression, not ideas. The algorithms can be studied and implemented in the same or another language independently. If you take only the algorithm and features necessary to implement it the copyright argument is that no permission is needed for those features. You would therefore not have to win the argument that GitHub’s word use authorizes derivative works. For an actual pair of implementations, the decisive question would be whether the claimed similarities are functionally dictated or include discretionary, protected expression.
All of which is to say it’s messy. If a particular implementation of an algorithm must necessarily reduce to identical pcode, the pcode is not protectable expression. Copyright does not protect the idea. It’s the path from the algorithm to a particular programming realization is where the line mines lie buried.
All of which is to say that safety lies in avoidance. Grace Hopper would have something to say about that.
What might be worth doing to avoid tripping over the theoretical legal risk is closely to study the code and identify the algortihms, then search out the formal definitions and start from scratch.
