Java中大整数的快速素因子分解

Question

所以我现在正在编写一个java代码。我已经让它工作得很好了，不过任务的重点是让它分解大数字（超过30位）。它可以做到这一点，但它可能需要超过15分钟，这是没有好处的。我的教授向我保证，我正在使用的算法将适用于2^70以下的数字，大约需要五分钟。我一直在试图想出一种方法（增加2而不是1，等等），但我似乎真的不知道如何在不跳过某些因素的情况下让它移动得更快。有什么想法吗？我还认为椭圆曲线法会更好，但他告诉我现在不要处理这个问题

以下是我的代码（ps，sqrt是我自己的功能，但我确信它正在工作）：

public String factorizer(BigInteger monster){
    System.out.println("monster =" + monster); 
    String factors = "";  
    BigInteger top = maths.monsterSqrt(monster);   
    if(monster.mod(two).equals(0));
        BigInteger jump = two;
    for(BigInteger bi = two; bi.compareTo(top) <= 0; bi = bi.add(jump)){
        while(monster.mod(bi).equals(zero)){
            factors +=  "+" + bi + ""; 
            monster = monster.divide(bi); 
            jump = one; 
        }
    }
    if(monster.compareTo(BigInteger.ONE) == 1){
        factors  += "+" + monster; 
    } 
    return factors; 
} 

Answer 1

当你把monster除以素数因子时，你也应该相应地调整top。实际上，外循环总是以1或2的增量运行到原始数字的平方根，对于一个30位数的数字，这将以10^15步的顺序进行。。。你只用了15分钟就完成了，这真是令人惊讶

如果你的怪物数有非常大的素数因子（比如说它本身就是素数），那么在任何情况下你都可以忘记良好的性能

请注意，您的示例代码的增量错误：如果原始数字不是偶数，那么jump将始终保持two，这意味着您只调查偶数因子，因此不会找到任何