蛮力大整数分解

Question

正如你从标题中所看到的，我正在努力对因子为2个素数的大整数进行强制因子分解。我想知道是否有一种方法可以在forhtml" target="_blank">循环中使用for循环。我知道这是一种很糟糕的方式，但无论如何我都愿意这样做。（我本来打算使用费马分解定理，但如果没有一些额外的方法/库，你就不能求大整数，我无法做到这一点），所以请尝试一下，看看你是否可以帮助我。大致如下：

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.nextPossiblePrime，我只是想告诉你我希望它如何工作；但这就是为什么我要问，因为idk这样的事情是否有可能！

请让我知道这条路线是否可行，以及我如何修复这个错误代码，使其像我正在可视化一样运行！

谢谢

Answer 1

我对计算机科学还是相当陌生（8个月），这是我第一次回答问题，如果我帮不上什么忙，那么很抱歉。如果我错了，请纠正我（说真的，我正在努力学习），但我认为你要找的是二次筛。http://en.wikipedia.org/wiki/Quadratic_sieve你似乎比我更先进，但我用了一天的时间就实现了。它在分解大数方面非常有效。

我对Fermat的因式分解方法一无所知，但你能不能把BigInteger继承到一个新的类中，并用一个平方根函数来实现它？我不知道你需要什么样的精确度，但你可以用BigDecimal来代替。

希望这有帮助

编辑：我猜你没有测试你的代码。不能使用这样的运算符

Answer 2

我拒绝“只是帮你做你正在做的事情”没用的。

我谦虚地在我的博客上推荐使用质数的短文编程。这里讨论的pollard rho算法将毫不费力地计算出您的数字。包括使用BigInteger的java实现。

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