Nbits的随机数xx的质因数列表。isProbablePrime方法测试剩余的因子是否为质数x分解。（停止）x的质因数列表中，并转到步骤4。为什么这个方法可行：（尽管你们中的许多人认为这是一个难题）
事实是，质数并不是那么稀有。对于1024位数，素数定理表明大约每1024 ln 2（约710）个数字中就有一个是素数。
因此，如果我生成一个随机数x，它是素数，并且我接受概率素数检测，那么我就成功地分解了x。
如果它不是素数，但我快速地分解出一些小因子，并且剩余因子是（概率上）素数，那么我就成功地分解了x。
否则，我会放弃并生成一个新的随机数。（这是OP认为可接受的）
大多数成功分解的数字将具有1个大素数因子和几个小素数因子。
难以分解的数字是那些没有小素数因子且至少有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;
}
}
如果你要分解的数字具有小质因子，可以使用Pollard p-1分解算法。它已经将数字2 ^ 740 + 1的30位质因子分解出来。ECM是一种类似但次指数的算法，但实现更加困难。算法所需时间取决于设定的边界b。它将分解任何具有因子p且p - 1为b平滑的数字。
//Pollard p - 1 factorization algorithm
void factor(mpz_t g, mpz_t n, long b)
{
//sieve for primes
std::vector<bool> r;
for(int i = 0; i < b; i++)
r.push_back(true);
for(int i = 2; i < ceil(sqrt(b - 1)); i++)
if(r.at(i) == true)
for(int j = i * i; j < b; j += i)
r.at(j) = false;
std::vector<long> p;
std::vector<long> a;
for(int i = 2; i < b; i++)
if(r[i] == true)
{
p.push_back(i);//Append the prime on to the vector
int temp = floor(log(b) / log(i)); //temp = logb(i)
// put primes in to sieve
// a = the maximum power for p ^ a < bound b
if(temp == 0)
a.push_back(1);
else
a.push_back(temp);
}
int m = p.size();//m = number of primes under bound b
mpz_t c;// c is the number Which will be exponated
mpz_init(c);
long two = 2;
mpz_set_ui(c, two);// set c to 2
int z = 0;
long x = 2;
// loop c until a factor is found
for(;;)
{
mpz_set_si( c, x);
//powering ladder
for(long i = 0; i < m; i++)
for(long j = 0; j < a[i]; j++)
mpz_powm_ui(c , c, (p[i]), n);
//check if a factor has been found;
mpz_sub_ui(c ,c,1);
mpz_gcd(g ,c, n);
mpz_add_ui(c , c, 1);
//if g is a factor return else increment c
if((mpz_cmp_si(g,1)) > 0 && (mpz_cmp(g,n)) < 0)
return;
else if (x > b)
break;
else
x++;
}
}
int main()
{
mpz_t x;
mpz_t g;
//intialize g and x
mpz_init(g);
mpz_init_set_str(x,"167698757698757868925234234253423534235342655234234235342353423546435347",10);
//p-1 will factor x as long as it has a factor p where p - 1 is b-smooth(has all prime factors less than bound b)
factor(g , x, 1000);
//output the factor, it will output 1 if algorithm fails
mpz_out_str(NULL, 10, g);
return 0;
}
输出 - 7465647 执行时间 - 0.003 秒
J.Pollard 创造的另一个分解算法是 Pollards Rho 算法，它不是很快但需要非常少的空间。还有并行化的方法。它的复杂度为 O(n^1/4)。
//Pollard rho factoring algorithm
void rho(mpz_t g, mpz_t n)
{
mpz_t x;
mpz_t y;
mpz_init_set_ui(x ,2);
mpz_init_set_ui(y ,2);//initialize x and y as 2
mpz_set_ui(g , 1);
mpz_t temp;
mpz_init(temp);
if(mpz_probab_prime_p(n,25) != 0)
return;//test if n is prime with miller rabin test
int count;
int t1 = 0;
int t2 = 1;
int nextTerm = t1 + t2;
while(mpz_cmp_ui(g,1) < 1)
{
f(x,n);//x is changed
f(y,n);//y is going through the sequence twice as fast
f(y,n);
if(count == nextTerm)//calculate gcd every fibonacci number
{
mpz_sub(temp,x,y);
mpz_gcd(g , temp, n);
t1 = t2;
t2 = nextTerm;
nextTerm = t1 + t2;//calculate next fibonacci number
}
count ++;
}
return;
}
int main()
{
mpz_t x;
mpz_t g;
//intialize g and x
mpz_init(g);
mpz_init_set_str(x,"167698757698757868925234234253423",10);
rho(g , x);
//output the factor, it will output 1 if algorithm fails
mpz_out_str(NULL, 10, g);
return 0;
}
输出 - 353 执行时间 - 0.003秒
f() 在哪里？ - raspiduino目前您无法使用GMP对bigint进行因式分解。 您可以将bigint转换为其他库，并使用它们的因式分解算法。 请注意，具有>> 20位数字的整数的因式分解需要专门的算法，并且接近指数级缓慢。
请查看：
你提供的任务很有趣！谢谢！
对我来说，用了两天时间编写高级解决方案是一件非常愉快的事情。我从头开始实现了三个分解算法：试除法、Pollard Rho 和Lenstra椭圆曲线方法(ECM)。
众所周知，ECM 方法(基于椭圆曲线)是中等范围因素分解的最快方法之一。虽然试除法适合处理非常小的因子(每秒可达到2^20个因子)，而Pollard Rho则适合更大但仍然比较小的因子(每秒可达到2^40个因子)，而 ECM 则适合于中等范围因子(每10秒可达到2^60个因子)。
还有一些非常先进的方法，如通用数域筛(GNFS)(每月可实现2^700的因子分解)，但它们很难实现。还有二次筛法方法也很先进(可能每月可实现2^400的因子分解)，我也从头开始实现了这个算法，但代码太长了，虽然可以理解，但由于其体积，我没有在此附上。ECM 方法是高级方法中唯一相对容易实现的方法。
除了我实现的上述3种分解方法之外，我还在代码中使用了以下算法：模指数运算、费马素性测试、Barrett减少算法、欧几里得算法、扩展欧几里得算法、模乘逆算法、椭圆曲线点加法和乘法。
实际上，您的任务非常容易快速解决：对于2048位大小的比特，在大约每个ln(2048) = 1420次数中会出现一个质数，因此您只需快速生成大约1500个数字，同时检查它们是否为素数，例如使用非常快的费马素性测试。如果一个数字是素数，那么根据定义它已经被分解了。#include <boost/multiprecision/cpp_int.hpp>和#include <gmpxx.h>），因此您应该安装并链接两者。在Linux下，通过sudo apt install libboost-all-dev libgmp-dev非常容易安装两者。但是在Windows上有点棘手，请先安装Chocolatey Packet Manager，然后执行命令choco install boost-msvc-14.3。对于GMP，请按这里描述的方式安装VCPKG，然后vcpkg install gmp。如果您想要的话，也可以通过VCPKG安装Boost：vcpkg install boost。Y^2 = X^3 + A * x + B (mod N)。lambda = (y_q - y_p) / (x_q - x_p)。该分母是模N的模乘法逆元计算得出的。对于无限点，它变成不可逆，而根据逆数不可逆的属性，只有当GCD(N，x_q-x_p)!=1时才可能不可逆，此时GCD会给出一些非平凡因子（有时也是N），因此我们成功地通过给出第一个因子来分解了N。源代码在此处。由于StackOverflow每篇文章的符号限制为30K，而我的代码本身约为44K字节，因此我无法将其内联在此处，而是通过Github Gist共享它（下面链接）。同样的代码也可以通过Godbolt服务器上的在线尝试！链接获得。
示例控制台输出：
TrialDiv time 8.230 sec
Num: 4343663370925180057127849780941698665126534031938076094687921681578209757551374613160773985436765755919464255163981465381983273353052491 (2^453.90)
Factored: 13 (2^3.70, prime), 167 (2^7.38, prime), 3853 (2^11.91, prime), 53831 (2^15.72, prime), 916471 (2^19.81, prime), 9255383 (2^23.14, prime),
UnFactored: 11372390351822722497588418782148940973499109818654526670537593527638523385195910987808859992169924704037636069779 (2^372.24, composite),
PollardRho time 8.51 sec
Num: 11372390351822722497588418782148940973499109818654526670537593527638523385195910987808859992169924704037636069779 (2^372.24)
Factored: 189379811 (2^27.50, prime), 2315962907 (2^31.11, prime), 50213994043 (2^35.55, prime),
UnFactored: 5163708449171395447719565208770850251589387410889704005960043195676697732937073689 (2^278.09, composite),
Curves 1, Ops 12.965 Ki, ExtraPrimes 512, Primes 0.500 Ki, IterTime 0.410 sec
Curves 2, Ops 50.912 Ki, ExtraPrimes 512, Primes 1.000 Ki, IterTime 8.062 sec
Curves 3, Ops 112.586 Ki, ExtraPrimes 464, Primes 1.453 Ki, IterTime 15.093 sec
Curves 4, Ops 162.931 Ki, ExtraPrimes 120, Primes 1.570 Ki, IterTime 4.853 sec
Curves 5, Ops 193.699 Ki, ExtraPrimes 80, Primes 1.648 Ki, IterTime 4.201 sec
ECM time 32.624 sec
Num: 5163708449171395447719565208770850251589387410889704005960043195676697732937073689 (2^278.09)
Factored: 955928964443 (2^39.80, prime),
UnFactored: 540177004907359979630305557131905764121354872876442621652476639261690523 (2^238.29, composite),
Final time 49.385 sec
Num: 4343663370925180057127849780941698665126534031938076094687921681578209757551374613160773985436765755919464255163981465381983273353052491 (2^453.90)
Factored: 13 (2^3.70, prime), 167 (2^7.38, prime), 3853 (2^11.91, prime), 53831 (2^15.72, prime), 916471 (2^19.81, prime), 9255383 (2^23.14, prime), 189379811 (2^27.50, prime), 2315962907 (2^31.11, prime), 50213994043 (2^35.55, prime), 955928964443 (2^39.80, prime),
UnFactored: 540177004907359979630305557131905764121354872876442621652476639261690523 (2^238.29, composite),