Msieve 1.49 + GUI 1.1
因式分解是研究（半数学、半工程、半艺术形式）取大数并将它们作为较小数的乘积来表达的研究。如果我发现 15 = 3 * 5，我就对数字 15 进行了整数因式分解。随着要因式分解的数变大，完成因式分解的难度会爆炸式增长，以至于您可以发明密码取决于保理的难度，并合理地期望您的加密数据保持安全。有很多算法可用于执行整数分解。所有这些都有一个他们最擅长因式分解的首选数字大小，并且所有这些都有大量可用的实现。 Msieve 也不例外：它很有可能找到最大约 125 位数字的任何输入数字的完整因式分解。支持的实际位数要高得多（最多 164 位数），但大于 125 位数的问题很可能会失败。
试除法用于所有输入；如果结果的大小小于 25 位，则微小的自定义例程会进行分解。对于更大的数字，代码会切换到更强大的方法。在 1.04 版之前，这些方法仅限于二次筛。然而，从那时起，数字字段筛的实现也可用。 Readme.qs 中包含特定于二次筛实现的信息，而数字字段筛变体在 Readme.nfs 中描述
编写 Msieve 时考虑了几个目标：
- 尽可能快。我声称（没有证据）对于完全分解 40 到 100 位数字之间的一般输入，Msieve 比实现任何其他算法的任何其他代码都快。我意识到这是一项艰巨的任务，我可能不得不吃掉这些话，但是为了让 Msieve 快速运行已经付出了*很多*的努力。
- 尽可能便携。代码是用 C 编写的，并且是完全自包含的。它有自己的基本多精度库（可用于其他应用程序），并以尽可能独立于机器的方式编写。我已经验证了源代码在 32 位或 64 位 Intel x86、32 位和 64 位 PowerPC 以及 64 位 Alpha 平台上可以正确编译和运行。据报道，它可以在 RS6000 上以 32 位模式工作。它适用于 Windows、Linux（多种版本）、Mac OS X 和 AIX。几乎构建代码的唯一要求是您的编译器具有本机 64 位数据类型。
- 使用简单。唯一的输入是要因式分解的整数。其他一切都会自动发生。
- 自由（如啤酒）。整个代码库被发布到公共领域。这对我来说是爱好，用得越多越好。
如果您选择使用 Msieve，请告诉我它是如何进行的。我欢迎错误报告、建议、优化、新平台的移植、投诉、吹嘘等等。
(Factoring is the study (half math, half engineering, half art form) of taking big numbers and expessing them as the product of smaller numbers. If I find out 15 = 3 * 5, I've performed an integer factorization on the number 15. As the number to be factored becomes larger, the difficulty involved in completing its factorization explodes, to the point where you can invent secret codes that depend on the difficulty of factoring and reasonably expect your encrypted data to stay safe.
There are plenty of algorithms for performing integer factorization. Allhave a preferred size of number they are best at factoring, and all of themhave plenty of implementations available. Msieve is no exception: it can with high probability find the complete factorization of any input number up to about 125 digits in size. The actual number of digits supported is much higher (up to 164 digits), but problems larger than 125 digits are likely to fail.
Trial division is used on all inputs; if the result is less than 25 digits in size, tiny custom routines do the factoring. For larger numbers, the code switches to more powerful methods. Prior to version 1.04, those methods were limited to the quadratic sieve. From that point on, however, an implementation of the number field sieve is also available. Information specific to the quadratic sieve implementation is contained in Readme.qs, while the number field sieve variant is described in Readme.nfs
Msieve was written with several goals in mind:
- To be as fast as possible. I claim (without proof) that for completely factoring general inputs between 40 and 100 digits in size, Msieve is faster than any other code implementing any other algorithm. I realize that's a tall order, and that I'll probably have to eat those words, but a *lot* of effort has gone into making Msieve fast.
- To be as portable as possible. The code is written in C and is completely self contained. It has its own basic multiple precision library (which can be used in other applications) and is written in as machine-independent a manner as possible. I've verified that the source code compiles and runs correctly on 32- or 64-bit Intel x86, 32- and 64-bit PowerPC, and 64-bit Alpha platforms. It's reported to work in 32-bit mode on the RS6000. It works in Windows, Linux (several flavors), Mac OS X, and AIX. Pretty much the only requirement for building the code is that your compiler have a native 64-bit data type.
- To be simple to use. The only input is the integer to be factored. Everything else happens automatically.
- To be free (as in beer). The entire code base is released into the public domain. This is hobby stuff for me, and the more it's used the better.
If you choose to use Msieve, please let me know how it goes. I welcome bug reports, suggestions, optimizations, ports to new platforms, complaints, boasts, whatever.)
页:
[1]