2

所以我现在正在研究一个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; 
}
4

3 回答 3

6

这是我通过试除法进行的整数分解：

public static LinkedList tdFactors(BigInteger n)
{
    BigInteger two = BigInteger.valueOf(2);
    LinkedList fs = new LinkedList();

    if (n.compareTo(two) < 0)
    {
        throw new IllegalArgumentException("must be greater than one");
    }

    while (n.mod(two).equals(BigInteger.ZERO))
    {
        fs.add(two);
        n = n.divide(two);
    }

    if (n.compareTo(BigInteger.ONE) > 0)
    {
        BigInteger f = BigInteger.valueOf(3);
        while (f.multiply(f).compareTo(n) <= 0)
        {
            if (n.mod(f).equals(BigInteger.ZERO))
            {
                fs.add(f);
                n = n.divide(f);
            }
            else
            {
                f = f.add(two);
            }
        }
        fs.add(n);
    }

    return fs;
}

这段代码在我博客的一篇文章中有解释，里面也有对 Pollard 的 rho 算法的解释，可能更适合分解大整数。

顺便说一句，如今 30 位数并不是一个特别大的因式分解问题。任何超过几秒钟的时间都太长了。

于 2013-05-29T02:29:39.233 回答
2

当你除以monster一个主要因素时，你也应该top相应地调整。实际上，外部循环将始终运行到原始数字的平方根，增量为 1 或 2，对于 30 位数字，它需要 10 ^ 15 步的顺序......这很奇怪您只需 15 分钟即可完成！

如果你的怪物数有非常大的素因数（比如说它本身就是一个素数），那么无论如何你都可以忘记良好的性能。

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

于 2013-05-28T22:24:33.503 回答
0

不知道你为什么要返回一个字符串！

这对我有用。请注意，它每次都i与n / i和进行比较：n = n / i

// Memoization of factors.
static Map<BigInteger, List<BigInteger>> factors = new HashMap<>();
private static final BigInteger TWO = BigInteger.ONE.add(BigInteger.ONE);

public static List<BigInteger> factors(BigInteger n, boolean duplicates) {
  // Have we done this one before?
  List<BigInteger> f = factors.get(n);
  if (f == null) {
    // Start empty.
    f = new ArrayList<>();
    // Check for duplicates.
    BigInteger last = BigInteger.ZERO;
    // Limit the range as far as possible.
    for (BigInteger i = TWO; i.compareTo(n.divide(i)) <= 0; i = i.add(BigInteger.ONE)) {
      // Can have multiple copies of the same factor.
      while (n.mod(i).equals(BigInteger.ZERO)) {
        if (duplicates || !i.equals(last)) {
          f.add(i);
          last = i;
        }
        // Remove that factor.
        n = n.divide(i);
      }
    }
    if (n.compareTo(BigInteger.ONE) > 0) {
      // Could be a residue.
      if (duplicates || n != last) {
        f.add(n);
      }
    }
    // Memoize.
    factors.put(n, f);
  }
  return f;
}
于 2013-05-28T22:51:56.650 回答