Prime factorization (102 digits) I have a number that consists of 102 digits and I need to factor it. I ran it in alpertrom.com.ar, but it'll take up to 40 hours if I counted all right. Is there any way to make it by hand (stupid question), I mean to simplify computation for the program? Or maybe anyone can factor it out. The professor is probably just testing our processor's computability.
Here's the number: 166045890368446099470756111654736772731460671003059151938763854196360081247044441029824134260263654537
Your 102-digit nuber is two digits more than the first RSA challenge RSA-100 that has 330-bit.
This can be easily achieved with existing libraries like;

CADO-NFS ; http://cado-nfs.gforge.inria.fr/

NFS factoring: http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html

Factoring as a service https://seclab.upenn.edu/projects/faas/

The Factoring as a Service project is designed to allow anyone to factor 512-bit integers in as little as four hours using the Amazon EC2 platform for less than $100, with minimal setup.




The experiment
Factor of a 99 digit number
$n =$ 112887987371630998240814603336195913423482111436696007401429072377238341647882152698281999652360869.

I have tried with Pollard's $p$ -1 algorithm, still running for one and a half-day and did not produce a result, yet. This is what expected due to the B bound must be around $2^{55}$ with success probability $\dfrac{1}{27}$. I've stopped the experiment after the CADO-NFS succeeds. This is self-implemented Pollard's $p$ -1, one can find an optimized in GMP-ECM

Tried the CADO-NFS. The stable version may not be easily compiled for new machines, so prefer the active one from the GitLab.
After ~6 hours with 4 cores, CADO-NFS produced the result. This was an RSA CTF/Challange and I don't want to spoil the fun; here the hash commitments with SHA-512, it is executed with OpenSSL;
echo -n &quot;prime x&quot; | openssl sha512


27c64b5b944146aa1e40b35bd09307d04afa8d5fa2a93df9c5e13dc19ab032980ad6d564ab23bfe9484f64c4c43a993c09360f62f6d70a5759dfeabf59f18386

faebc6b3645d45f76c1944c6bd0c51f4e0d276ca750b6b5bc82c162e1e9364e01aab42a85245658d0053af526ba718ec006774b7084235d166e93015fac7733d


Experiments on RSA challenges with 6 cores using CADO-NFS




RSA Challange
Bit size
Time in minutes




RSA-100
330
270


RSA-110
364
280


RSA-120
397
1049


RSA-129
426
3279


RSA-140
430
Not tested





The core count is very important to reduce the time as 512-bit can be broken as 4 hours in the EC2 platform.

Details of the experiment

CPU : Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz

RAM : 32GB - doesn't require much ram, at least during polynomial selection and Sieveing.

Dedicated cores : 4

Test machine Ubuntu 20.04.1 LTS

CUDA - NO

gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)

cmake version 3.16.3

external libraries: Nothing out of Ubuntu's canonicals

CODA-NFS version : GitLab develepment version cloned at 23-01-2021

The bit sizes;

$n$ has 326 bits
$p$ has 165 bits
$q$ has 162 bits



The cado-nfs-2.3.0 did not compile and giving errors about HWLOC-  HWLOC_TOPOLOGY_FLAG_IO_DEVICES. Asked a friend to test the compile and it worked for them. It was an older Linux version. So I decided to use the GitLab version.


Note: this question did not factor the OPs original number.

Historical note: RSA-100 challenge has 330 bits and broken by Lenstra in 1991.