Issues factoring large prime that is 99 digits long

user_15049713 0
Viewed 354

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?

prime-factoring rsa cryptography math encryption
3 Answers

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.

user_18205530

What do you know about this number? If it is an RSA public key then it only has two large prime factors. If it is a random number then it will very probably have small prime factors. The type of number will determine how you want to approach factorising it.

Two ancillary functions will also be useful. First a Sieve of Eratosthenes to build a list of primes up to, say 50,000 or some convenient limit. Second a large number prime test, such as Miller-Rabin, to check if the residue is prime or not.

Use the sieve of Eratosthenes to give you all the small primes up to a convenient limit. Test for each prime in turn up to the square root of the target number. When you find a prime that divides the test number, divide the test number to make it smaller. A prime may divide in more than once. Reset the prime limit to the square root of the smaller number once all the divisions are finished.

if (numToTest MOD trialFactor = 0)
  repeat
    listOfFactors.add(trialFactor)
    numToTest <- numToTest/trialFactor
  until (numToTest MOD trialFactor != 0)
  primeLimit <- sqrt(numTotest)
endif

Once the number you are testing has been reduced to 1, you have completely factored it.

If you run out of primes before completely factoring the target, it is worth running the Miller-Rabin test 64 times to see if the remainder is itself prime; potentially that can save you a lot of work trying to find non-existent factors of a large prime. If the remainder is composite then you can either try again with a larger sieve or use one of the heavy duty factoring methods: Quadratic Sieve, Elliptic Curve etc.

user_8201270

I have authored a library for the R programming language called RcppBigIntAlgos that can factor these types of numbers in a reasonable amount of time (not as fast as using the excellent CADO-NFS library as used in @kelalaka's answer).

As others have pointed out, your number is going to be very difficult to factor by any program you roll yourself unless you invest a considerable amount of time into it. For me personally, I have invested thousands of hours. Your mileage may vary.

Here is my test run in a vanilla R console (no special IDE):

numDig99 <- "112887987371630998240814603336195913423482111436696007401429072377238341647882152698281999652360869"
## install.packages("RcppBigIntAlgos") if necessary
library(RcppBigIntAlgos)

prime_fac <- quadraticSieve(numDig99, showStats=TRUE, nThreads=8)

Summary Statistics for Factoring:
    112887987371630998240814603336195913423482111436696007401429072377238341647882152698281999652360869

|      MPQS Time     | Complete | Polynomials |   Smooths  |  Partials  |
|--------------------|----------|-------------|------------|------------|
|  11h 13m 25s 121ms |   100%   |   11591331  |    8768    |    15707   |

|  Mat Algebra Time  |    Mat Dimension   |
|--------------------|--------------------|
|    1m 39s 519ms    |    24393 x 24475   |

|     Total Time     |
|--------------------|
|  11h 15m 12s 573ms |

And just as @kelalaka, we obtain the same hashed values (Again, ran right in the R console):

system(sprintf("printf %s | openssl sha512", prime_fac[1]))
faebc6b3645d45f76c1944c6bd0c51f4e0d276ca750b6b5bc82c162e1e9364e01aab42a85245658d0053af526ba718ec006774b7084235d166e93015fac7733d

system(sprintf("printf %s | openssl sha512", prime_fac[2]))
27c64b5b944146aa1e40b35bd09307d04afa8d5fa2a93df9c5e13dc19ab032980ad6d564ab23bfe9484f64c4c43a993c09360f62f6d70a5759dfeabf59f18386

The algorithm implemented in RcppBigIntAlgos::quadraticSieve is the Multiple Polynomial Quadratic Sieve. There is a more efficient version of the quadratic sieve known as the Self Initializing Quadratic Sieve, however, there isn't as much literature in the wild available.

Here are my machine specs:

MacBook Pro (15-inch, 2017)
Processor: 2.8 GHz Quad-Core Intel Core i7
Memory; 16 GB 2133 MHz LPDDR3

And here is my R info:

sessionInfo()
R version 4.0.3 (2020-10-10)
Platform: x86_64-apple-darwin17.0 (64-bit)
Running under: macOS Catalina 10.15.7

Matrix products: default
BLAS:   /System/Library/Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/Versions/A/libBLAS.dylib
LAPACK: /Library/Frameworks/R.framework/Versions/4.0/Resources/lib/libRlapack.dylib

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] RcppBigIntAlgos_1.0.1 gmp_0.6-0            

loaded via a namespace (and not attached):
[1] compiler_4.0.3 tools_4.0.3    Rcpp_1.0.5
user_44085380
Related