Search code examples
mathencryptioncryptographyrsaprime-factoring

Issues factoring large number that is 99 digits long

The number is

112887987371630998240814603336195913423482111436696007401429072377238341647882152698281999652360869

My code is below

def getfactors(number):
    factors = []
    for potentialFactor in range(1 , int(math.sqrt(number)) + 1):
        if number % potentialFactor == 0:
            factors.append(potentialFactor)
    return factors

and the input is

getfactors(112887987371630998240814603336195913423482111436696007401429072377238341647882152698281999652360869)

The program has been running for at least 3 hours and I still have no results from it yet. The code works with other numbers too. Is there any algorithm or method that I could use to speed this up?

Solution

  • Your method will take a lot of time to factor in the given number since the RSA primes are close to each other. Even sieving with Sieve of Eratosthenes won't help, since you have a 326-bit number. Can you sieving to 163-bit, there is no way. This is slightly larger than the first RSA challenge RSA-100 that has 300-bit.

    Use existing libraries like the

    The experiments

    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 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. As expected this is an RSA CTF/Challange. Since 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

    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 ( RSA-100 challenge has 330 and broken by Lenstra in 1991)
      • 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.