search

AdamWhiteHat / GNFS

A complete, proof-of-concept, C# implementation of the General Number Field Sieve algorithm for factoring very large semi-prime numbers. The focus was on readability and understandability of the code, not performance.
GNU General Public License v3.0
56 stars 13 forks source link

Question: I need just function Factorization(n) for get prime numbers. Is it possible? #11

Closed potaninmt closed 2 years ago

potaninmt commented 2 years ago

I need just function Factorization(n) for get prime numbers. Is it possible?

AdamWhiteHat commented 2 years ago

Is it possible?

Probably.

What factorization algorithm you will want to use depends on the size of the number you are trying to factor.

For 'smallish' numbers, say, 17 digits or less, you can use this factorization class: Factorization.cs

The General Number Field Sieve algorithm is only for factoring numbers that are the product of exactly two prime numbers (a semiprime number). The complexity and runtime of that algorithm is such that it only really makes sense to run it on numbers that are greater than 100 digits in size.

If your number is less than that, and you know it has many factors, then the elliptic curve factorization algorithm is ideal for that scenario.

If your number is a semiprime number, and you know that your two prime factors are very close to each other, that is, the two prime factors are within ±1,000,000 of the square root of your number to be factored, then Fermat's factorization method will make short work of that.

For those last two scenarios, and probably just about any other factoring scenario really, especially you are not looking for code, but rather an application you can just tell it to factor your number and have it figure out what the best approach is, then you will want a tool, not written by, me called YAFU. It stands for Yet Another Factoring Utility--a rather modest name for what it does, really. Its my go-to whenever I need to get something factored that isn't trivially small. YAFU can also do the GNFS too (actually, it doesn't do gnfs itself, it calls ggnfs, an external gnfs library) and its going to perform GNFS a lot faster than my GNFS library.

The purpose of my GNFS library isn't so much to do GNFS and be fast at it, it's to do the GNFS algorithm and have code that is readable and understandable with the hope being that it will help people better understand how the GNFS algorithm works--something I wish I had when I was learning it. The program GGNFS and MSIEVE are open source as well, but they are written in C/C++ and designed for speed, not readability and understandably, and as such, reading their source code is not particularly insightful for understanding the algorithm.

You should be able to download an already compiled version of YAFU for your system (mac, windows or Linux), and to factor a number with you, you run it on the command line, it will give you a prompt and you just type: factor(61965745159819079) or whatever your number is and hit enter.

If you want YAFU to be able to use elliptic curve against your number (I suppose you ought to--it might be kind of limited without it), you'll need to download the binaries of an application called GMP-ECM, extract them to a folder somewhere, and tell YAFU the path to the ecm.exe in that folder by setting the ecm_path setting in the yafu.ini file.

Similarly, if you want YAFU to be able to run your number through GNFS if that's what it determines is required to factor it, you will need to download a compiled version of the application called GGNFS, extract them somewhere, and provide the DIRECTORY (not exe file this time) path to YAFU by setting the ggnfs_dir setting in the yafu.ini file.

Actually, that all sounds rather complicated, doesn't it? Since I already have all these installed and set it up, I went ahead and just zipped up my YAFU folder and the ECM, GGNFS and MSIEVE utils and their folders relative to YAFU for you and attached it to this comment right here:

YAFU_Portable.zip

So if you are running 64 bit Windows, you can just download Yafu_Portable.zip, extract it somewhere, and run yafu.exe or yafu-Win32.exe on the command line, then type: factor(61965745159819079) or whatever your number you want to factor is, and hit enter, and you should be factoring. (Unless you are not running 64bit windows, well then refer to the paragraphs above that is struckthrough.)

Note, when I say on the command line, I mean: run cmd.exe, browse to the YAFU folder and run yafu.exe from the cmd window. This isn't strictly necessary, but if you don't do this, as soon as the application is done factoring, the window disappears and you have to go digging through the factor.log to retrieve the results of your factorization. If you run cmd.exe first, then run yafu, it wont disappear after its done running and you read its output.

If your intent was to understand the GNFS algorithm more (I think your question makes it clear that is not the case), and you want some help selecting the parameters to get my application to factor your number with some degree of success, let me know what number you wanted to use and we can discuss parameters.

Let me know if I have answered your question for you, or if you have any remaining questions, feel free to ask them.