大整数因数分解问题

kaiser

I(i)给定两个素数p,q，计算乘积p*q=n很容易；
(ii)给定整数n,求n的素因数p,q使得n=p*q非常困难。
试分解n=p*q＝16000000000000002295000000000000003170601

碧城仙

factor 16000000000000002295000000000000003170601
first trying brute force division by small primes
PRIME FACTOR     1249
now trying 1000 iterations of brent's method
PRIME FACTOR     19861
PRIME FACTOR     375563
now trying william's (p+1) method
phase 1 - trying all primes less than 10000
phase 2 - trying last prime less than 1000000
PRIME FACTOR     82798699
PRIME FACTOR     20741975668392230957

请勿用于任何非法活动中，请勿用于商业活动中，仅供参考，风险自担，后果自负！本站不欢迎任何具体的询问大合数分解和密码破解的问题！包括本帖所提问题！本论坛仅仅只欢迎讨论算法或者软件使用方面的问题！基于一些安全性的考虑，我们记录了您的 IP：219.245.96.128(来源：陕西省 西安市 西安电子科技大学 24号楼)，请谅解！

碧城仙

16000 000000 000002 295000 000000 000003 170601 = 1249 x 19861 x 375563 x 82 798699 x 20 741975 668392 230957

Number of divisors:  32

Sum of divisors:  16013 659324 472865 184956 038287 751466 000000

Euler's Totient:  15986 342038 356302 037157 708165 581905 479680

Moebius: -1

Sum of squares: a^2 + b^2 + c^2
a = 124 526545 308432 883791
b = 22 206744 776009 257186
c = 18

Factorization complete in 0d 0h 0m 0s
ECM: 108075 modular multiplications
Prime checking: 6893 modular multiplications

16000000000000002295000000000000003170601 = 1249 * 19861 * 375563 * 82798699 * 20741975668392230957