8
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ What was the purpose of the professor's example? If they wanted to make everybody understand that factoring is hard, maybe they have succeeded, because you have not factored it yet, have you? From the context, I suppose the intention was not to test factoring software written by yourself? So, factoring such a number is possible, but it requires software that uses smart enough techniques, and it requires computational power. You can download Yafu for example; say factor(1660...37) to it, and wait. Then you will see the result eventually. Deadline? $\endgroup$
    – Jeppe Stig Nielsen
    Commented Apr 23, 2021 at 15:25
  • $\begingroup$ Transforming crypto.SE into factor-a-CTF-modulus-as-a-free-service is a dangerous slope. If there's another question like this consisting mostly of an RSA modulus to factor, I'm thinking of closing it under the rule "Requests for analyzing ciphertext (..) are off-topic", or similar. $\endgroup$
    – fgrieu ♦
    Commented Apr 24, 2021 at 6:38
  • $\begingroup$ @fgrieu In that case, you'd probably also want to remove this from the HNQs, so it doesn't set an example for other people. $\endgroup$
    – user80567
    Commented Apr 24, 2021 at 8:24
  • 1
    $\begingroup$ Well, I did not provide the answer, rather provide the ways to solve it and provide some personal experiences. I considered this as a canonical answer for our site so that any other similar question can be duped on this. $\endgroup$
    – kelalaka
    Commented Apr 24, 2021 at 8:26

2 Answers 2

Reset to default
15
$\begingroup$

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;

The experiment

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

  1. 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

  2. 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 "prime x" | 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

enter image description here 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.

Improve this answer
$\endgroup$
12
  • $\begingroup$ how are the minutes/seconds calculated? doesn't seem like a factor of 60 $\endgroup$
    – qwr
    Commented Apr 23, 2021 at 5:43
  • $\begingroup$ did you try with ggnfs or msieve? it's been years since I messed around with those programs so idk if they are still used. $\endgroup$
    – qwr
    Commented Apr 23, 2021 at 5:45
  • $\begingroup$ @qwr CADO-NFS output 93645.9/16232.1. I've used my system real-time measured with time command. No, I did not try ggnfs or msieve. $\endgroup$
    – kelalaka
    Commented Apr 23, 2021 at 10:54
  • 2
    $\begingroup$ 270 minutes is not 32720 seconds, and 3279 minutes is definitely not 7838 seconds. Only after puzzling about this for a long time and starting this comment did it occur to me that you might be using the comma as a decimal separator. In which case you should probably remove the milliseconds, which have no imaginable importance on day-long timescales, rather than baffling many readers. $\endgroup$
    – Nick Matteo
    Commented Apr 23, 2021 at 14:27
  • $\begingroup$ @NickMatteo One should read it like 270m32720s. Removed the seconds. $\endgroup$
    – kelalaka
    Commented Apr 23, 2021 at 14:42
3
$\begingroup$

Using for example cado-nfs, you can find the factorization (~5min using 32 cores) as 51700365364366863879483895851106199085813538441759 * 3211696652397139991266469757475273013994441374637143

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Welcome to Cryptography and here we are not HW solvers, and this is not out community's way. My answer doesn't provide the solution, rather concentrate on the problem and how to solve it. $\endgroup$
    – kelalaka
    Commented Apr 23, 2021 at 18:08
  • $\begingroup$ @FelixZimmermann how much ram did it used? $\endgroup$
    – user2284570
    Commented Feb 20 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.