用gmp有效率地计算大数 [英] Factor a large number efficiently with gmp

问题描述

我需要得到所有的大数字的素因子，可以很容易得到1k位。
数字几乎是随机的，所以它不应该是硬的。
我如何有效地做？我使用C ++与GMP库。

I need to get all the prime factors of large numbers that can easily get to 1k bits. The numbers are practically random so it shouldn't be hard. How do I do it efficiently? I use C++ with GMP library.

编辑：
我想你都误解了我。

我的意思是一个数字

对我的英语很抱歉，在我的语言中，prime和factor是相同的：）

I guess you all misunderstood me.
What I mean by prime a number is to get all prime factors of the number.
Sorry for my english, in my language prime and factor are the same :)

澄清（从OP的其他职位）：

clarification (from OP's other post):

我需要的是一种有效率的因素（可以达到2048位），使用C ++和GMP（Gnu多重处理lib）或更少优选任何其他方式。
这些数字几乎是随机的，所以很少有机会很难考虑，即使这个数字很难考虑，我可以重新输入数字（不能选择）。

What I need is a way to efficiently factor(find prime factors of a number) large numbers(may get to 2048 bits) using C++ and GMP(Gnu Multiple Precession lib) or less preferably any other way. The numbers are practically random so there is little chance it will be hard to factor, and even if the number is hard to factor, I can re-roll the number(can't choose though).

推荐答案

一个好的开始是用小素数进行一些预过滤，比如说低于100 000左右的所有素数。只需尝试划分其中每一个（创建一个表，然后在运行时加载或将其作为静态数据在代码中）。它可能看起来很慢和愚蠢，但如果数字是完全随机的，这将给你一些因素非常快，具有巨大的概率。然后看看剩余的数字，并决定下一步做什么。如果它是相当小（什么小的意思是由你），你可以尝试一个原始性测试（在GMP中有一些东西我认为），如果它给它是一个素数，你可以在大多数情况下信任它。否则你必须进一步考虑。

A good start would be some pre-filtering with small primes, say about all primes lower than 100 000 or so. Simply try to divide by every single one of them (create a table which you then load at runtime or have it as static data in your code). It might seem slow and stupid, but if the number is totally random, this will give you some factors very fast with a huge probability. Then look at the remaining number and decide what to do next. If it is quite small (what "small" means is up to you) you could try a primality test (there is something in GMP i think) and if it gives it is a prime, you can in most of the cases trust it. Otherwise you have to factor it further.

如果你的数字真的很大，而且你关心性能，那么你肯定需要实现比一个愚蠢的部门更复杂的东西。看看二次筛（try wikipedia）。这是相当简单，但非常强大。如果你是最大的挑战，尝试MPQS，二次筛选算法的一个变体。 此论坛是一个很好的信息来源。您甚至还需要一个工具的现有实施 - 查看示例。

If your numbers are really huge and you care about performance, then you definitely need to implement something more sophisticated than just a stupid division. Look at Quadratic Sieve (try wikipedia). It is quite simple but very powerful. If you are up to the chalenge, try MPQS, a variant of the quadratic sieve algorithm. This forum is a good source of information. There are even existing implementations of a tool you need - see for example this.

请注意，尽管1k位的数字是巨大的。考虑这样的数字（即使使用MPQS或其他）可能需要多年，如果你是幸运和永远，如果不是。我认为MPQS执行良好的数字约100-400位（如果他们是由两个素数几乎同样大，这是最难的情况下当然）。

Note though that numbers with 1k bits are huge by all means. Factoring such a number (even with MPQS or others) might take years if you are lucky and forever if not. I think that MPQS performs well with numbers of about 100-400 bits (if they are composed of two primes almost equally large, which is the hardest case of course).

这篇关于用gmp有效率地计算大数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！