0

从标题可以看出，我正在努力尝试对因数为 2 个素数的大整数进行因式分解。我想知道是否有一种方法可以为此在 for 循环中使用 for 循环。我知道这是一种可怕的方法，但我还是想这样做。（我打算使用 fermats 因式分解定理，但如果没有一些额外的方法/库，你就不能 sqrt BigIntegers，我不能这样做）所以试着看看你是否能帮助我做我正在做的事情。大致上是这样的：

BigInteger n = new BigInteger("270653957405596110781");  // this is what i need the factors of
BigInteger TWO = new BigInteger("2");
for( BigInteger i = new BigInteger("1"); i < n.divide(TWO); i.nextProbablePrime() ){
    for( BigInteger k = new BigInteger("1"); k < n.divide(TWO); k.nextPossiblePrime){
        if(i.Multiply(k) = n){
            //i and k are the factors, and return them
        }
     }
 }

显然那太糟糕了，我知道你不能通过说 i.nextPossiblePrime() 来增加下一个素数，你需要它说 i = i.nextpossible prime，我只是向你展示了我希望它如何工作; 但这就是我问的原因，因为我想知道这样的事情是否可能！

请让我知道这条路线是否可行，以及我如何修复这个糟糕的代码以像我想象的那样运行！

谢谢！

4

2 回答 2

4

我拒绝“只是帮助你做你正在做的事情”。它行不通。

我谦虚地在我的博客上推荐了一篇关于素数编程的文章。那里讨论的 pollard-rho 算法将毫无困难地考虑您的数字。包括使用 BigInteger 的 java 实现。

顺便说一句，270653957405596110781 = 7588940707 * 35664260383。

于 2013-04-15T01:59:26.160 回答
1

我对计算机科学还很陌生（8 个月），这是我第一次回答问题，如果我没有太多帮助，很抱歉。如果我错了，请纠正我（说真的，我正在努力学习），但我认为你正在寻找的是二次筛。http://en.wikipedia.org/wiki/Quadratic_sieve您似乎比我更先进，但我能够通过一天的工作来实现它。它在分解大量数字方面非常有效。

我对 Fermat 的因式分解方法一无所知，但是您不能将 BigInteger 继承到一个新类中并自己实现它，并使用平方根函数完成吗？我不知道您需要什么样的准确性，但您始终可以将其基于 BigDecimal。

希望这会有所帮助

编辑：我猜你没有测试你的代码。您不能将 < 之类的运算符与 BigInteger 一起使用。您需要使用 BigInteger.compareTo(BigInteger)

于 2013-04-16T07:23:06.950 回答