簡単に 1k ビットに達する大きな数のすべての素因数を取得する必要があります。数字は実質的にランダムなので、難しいことではありません。効率的に行うにはどうすればよいですか？私はGMPライブラリでC++を使用しています。
編集：皆さんは私を誤解していると思います。
素数とは、その数のすべての素因数を取得することです。
私の英語で申し訳ありませんが、私の言語では素数と因数は同じです:)
明確化（OPの他の投稿から）：
私が必要としているのは、C ++とGMP（Gnu Multiple Precession lib）を使用して、またはあまり好ましくない他の方法を使用して、大きな数（2048ビットになる可能性がある）を効率的に因数分解する（数の素因数を見つける）方法です。数字は実質的にランダムなので、因数分解が困難になる可能性はほとんどなく、因数分解が困難な場合でも、数字を再ロールできます（選択できません）。
良いスタートは、100 000 程度以下のすべての素数について、小さな素数で事前にフィルタリングすることです。それらのすべてで除算するだけです（実行時にロードするテーブルを作成するか、コード内の静的データとして使用します）。遅くてばかげているように見えるかもしれませんが、数が完全にランダムである場合、これは非常に高速で大きな確率でいくつかの要因を提供します. 次に、残りの数を見て、次に何をすべきかを決定します。それが非常に小さい場合（「小さい」という意味はあなた次第です）、素数性テストを試すことができます（GMPには何かがあると思います）。それ以外の場合は、さらに因数分解する必要があります。
数が非常に多く、パフォーマンスが重要な場合は、単なるばかげた除算よりも洗練されたものを実装する必要があります。Quadratic Sieve を見てください (wikipedia を試してください)。非常にシンプルですが、非常に強力です。挑戦するつもりなら、二次ふるいアルゴリズムの変形である MPQS を試してみてください。このフォーラムは良い情報源です。必要なツールの既存の実装もあります。たとえば、 this を参照してください。
ただし、1k ビットの数値はどうしても巨大であることに注意してください。そのような数を (MPQS などを使用しても) 因数分解すると、運が良ければ何年もかかるかもしれません。MPQS は、約 100 ～ 400 ビットの数でうまく機能すると思います (もちろん、最も難しいケースである、ほぼ同じ大きさの 2 つの素数で構成されている場合)。
以下は、Java のサンプル アルゴリズムです (GMP を使用した C++ ではありませんが、変換は非常に簡単なはずです)。
xビット長の乱数を生成しますNbitsisProbablePrimeJavaのメソッドを使用して、残りの因数が素数かどうかをテストしますこのアルゴリズムのすべてのパラメーターは、プログラム リストの先頭付近にあります。250 ミリ秒のタイムアウトで 1024 ビットの乱数を探し、少なくとも 4 つの素因数を持つ数値 x を取得するまでプログラムを実行し続けます (プログラムは 1、2、または 3 つの素因数を持つ数値を見つけることがあります)。最初）。このパラメータを設定すると、通常、私の 2.66Ghz iMac で約 15 ～ 20 秒かかります。
Pollard の rho アルゴリズムは実際にはそれほど効率的ではありませんが、二次ふるい(QS) や一般数体ふるい(GNFS) と比較すると単純です。単純なアルゴリズムがどのように機能するかを確認したかっただけです。
なぜこれが機能するのか: (これは難しい問題だと多くの人が主張しているにもかかわらず)
明白な事実は、素数はそれほどまれではないということです. 1024 ビット数の場合、素数定理によれば、1024 ln 2 (= 約 710) 個の数に約 1 個が素数です。
したがって、素数である乱数 x を生成し、確率論的素数検出を受け入れると、x の因数分解に成功します。
素数ではないが、いくつかの小さな因数をすばやく因数分解し、残りの因数が (確率的に) 素数である場合、x の素因数分解は成功です。
それ以外の場合は、あきらめて新しい乱数を生成します。（OPが言うことは受け入れられます）
因数分解に成功したほとんどの数には、1 つの大きな素因数といくつかの小さな素因数があります。
素因数分解が困難な数は、小さな素因数がなく、少なくとも 2 つの大きな素因数 (これらには、2 つの大きな数の積である暗号化キーが含まれます。OP は暗号化について何も述べていません) です。時間がなくなったらスキップします。
package com.example;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class FindLargeRandomComposite {
final static private int[] smallPrimes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97};
final static private int maxTime = 250;
final static private int Nbits = 1024;
final static private int minFactors = 4;
final static private int NCERTAINTY = 4096;
private interface Predicate { public boolean isTrue(); }
static public void main(String[] args)
{
Random r = new Random();
boolean found = false;
BigInteger x=null;
List<BigInteger> factors=null;
long startTime = System.currentTimeMillis();
while (!found)
{
x = new BigInteger(Nbits, r);
factors = new ArrayList<BigInteger>();
Predicate keepRunning = new Predicate() {
final private long stopTime = System.currentTimeMillis() + maxTime;
public boolean isTrue() {
return System.currentTimeMillis() < stopTime;
}
};
found = factor(x, factors, keepRunning);
System.out.println((found?(factors.size()+" factors "):"not factored ")+x+"= product: "+factors);
if (factors.size() < minFactors)
found = false;
}
long stopTime = System.currentTimeMillis();
System.out.println("Product verification: "+(x.equals(product(factors))?"passed":"failed"));
System.out.println("elapsed time: "+(stopTime-startTime)+" msec");
}
private static BigInteger product(List<BigInteger> factors) {
BigInteger result = BigInteger.ONE;
for (BigInteger f : factors)
result = result.multiply(f);
return result;
}
private static BigInteger findFactor(BigInteger x, List<BigInteger> factors,
BigInteger divisor)
{
BigInteger[] qr = x.divideAndRemainder(divisor);
if (qr[1].equals(BigInteger.ZERO))
{
factors.add(divisor);
return qr[0];
}
else
return x;
}
private static BigInteger findRepeatedFactor(BigInteger x,
List<BigInteger> factors, BigInteger p) {
BigInteger xprev = null;
while (xprev != x)
{
xprev = x;
x = findFactor(x, factors, p);
}
return x;
}
private static BigInteger f(BigInteger x, BigInteger n)
{
return x.multiply(x).add(BigInteger.ONE).mod(n);
}
private static BigInteger gcd(BigInteger a, BigInteger b) {
while (!b.equals(BigInteger.ZERO))
{
BigInteger nextb = a.mod(b);
a = b;
b = nextb;
}
return a;
}
private static BigInteger tryPollardRho(BigInteger n,
List<BigInteger> factors, Predicate keepRunning) {
BigInteger x = new BigInteger("2");
BigInteger y = x;
BigInteger d = BigInteger.ONE;
while (d.equals(BigInteger.ONE) && keepRunning.isTrue())
{
x = f(x,n);
y = f(f(y,n),n);
d = gcd(x.subtract(y).abs(), n);
}
if (d.equals(n))
return x;
BigInteger[] qr = n.divideAndRemainder(d);
if (!qr[1].equals(BigInteger.ZERO))
throw new IllegalStateException("Huh?");
// d is a factor of x. But it may not be prime, so run it through the factoring algorithm.
factor(d, factors, keepRunning);
return qr[0];
}
private static boolean factor(BigInteger x0, List<BigInteger> factors,
Predicate keepRunning) {
BigInteger x = x0;
for (int p0 : smallPrimes)
{
BigInteger p = new BigInteger(Integer.toString(p0));
x = findRepeatedFactor(x, factors, p);
}
boolean done = false;
while (!done && keepRunning.isTrue())
{
done = x.equals(BigInteger.ONE) || x.isProbablePrime(NCERTAINTY);
if (!done)
{
x = tryPollardRho(x, factors, keepRunning);
}
}
if (!x.equals(BigInteger.ONE))
factors.add(x);
return done;
}
}
現時点では、GMP で bigint を因数分解することはできません。bigint を他のライブラリに変換し、それらのファクタリング アルゴリズムを使用できます。>>20 桁の整数の素因数分解には特殊なアルゴリズムが必要であり、ほぼ指数関数的に遅いことに注意してください。
チェックアウト：