2

だから私は今Javaコードに取り組んでいます。私はそれを完全にうまく機能させましたが、割り当てのポイントは、大きな数 (30 桁以上) を因数分解することです。それを行いますが、それを行うのに 15 分以上かかる場合があり、これは良くありません。私の教授は、私が使用しているアルゴリズムは 2^70 までの数値に対して機能し、約 5 分で処理できるはずだと保証してくれました。私はそれを行う方法を考え出そうとしています（1ではなく2ずつ増やすなど）が、いくつかの要因をスキップせずにそれをより速く動かす方法を実際に理解できないようです. 何か案は？私も楕円曲線法の方がいいと思っていたのですが、今は取り扱わないようにとのことでした。

これが私のコードです（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;
}

このコードは、私のブログのエッセイで説明されています。大きな整数の素因数分解により適している可能性があるポラードのロー アルゴリズムの説明もあります。

ところで、30 桁は、最近では特に大きな因数分解の問題ではありません。数秒以上は長すぎます。

于 2013-05-29T02:29:39.233 に答える