Cracking 1980s Encryption

Computer Science Level 4

Your uncle Omar has asked for your help. Back in the 1980s, he encrypted some personal documents using RSA encryption, but he lost his private key. He waited years for computers to become powerful enough to unlock his key, but then forgot about the documents until last week.

Can you help him recover the documents by factoring this large number for him?

26390 85015 23339 22027 40949 38630 97432 59521 51779 38861 43240 989

Please submit your answer by entering the digit sum of the smallest prime factor.

The answer is 115.

5 solutions

Discussions for this problem are now closed

Ricky Escobar
Jan 28, 2014

In Mathematica, we use

FactorInteger[2639085015233392202740949386309743259521517793886143240989]

which returns

{{3167364220484410988722665601, 1}, {833211727961546299775962002589, 1}}

in about two minutes on my machine. The smallest prime factor of our number is the first element of the above list: $3\ 167\ 364\ 220\ 484\ 410\ 988\ 722\ 665\ 601,$ the digit sum of which is $\fbox{115.}$

Exactly what I did

Sam Thompson - 7 years, 4 months ago

Can anyone check and tell me what's wrong with my code? I don't see anything wrong and it works for small numbers. I got the answer as 29 (which on summing is 11) -

public static void main(String a[]){
    final double num = 2639085015233392202740949386309743259521517793886143240989d;

    for(double i = 3d;;i++)
        if(num % i == 0)
            if(prime(i)){
                System.out.println(i);
                break;
            }
}

static boolean prime(double n) {
    if (n%2==0) return false;
    for(double i=3;i*i<=n;i+=2)
    if(n%i==0)
        return false;
    return true;
}

I just loop through numbers, check if they can divide the large number without any remainder and if a number does that, then check if it is prime. If it is, then print out the answer

Aryan Gaikwad - 6 years, 2 months ago

Thaddeus Abiy
Jan 25, 2014

I see no way of solving this except using a number field,quadratic sieve or GMP-ECM.

> The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.[1]

More Here

The Lenstra elliptic curve factorization or the elliptic curve factorization method (ECM) is a fast, sub-exponential running time algorithm for integer factorization which employs elliptic curves. For general purpose factoring, ECM is the third-fastest known factoring method. The second fastest is the multiple polynomial quadratic sieve and the fastest is the general number field sieve. The Lenstra elliptic curve factorization is named after Hendrik Lenstra. Practically speaking, ECM is considered a special purpose factoring algorithm as it is most suitable for finding small factors. Currently, it is still the best algorithm for divisors not greatly exceeding 20 to 25 digits (64 to 83 bits or so), as its running time is dominated by the size of the smallest factor p rather than by the size of the number n to be factored. Frequently, ECM is used to remove small factors from a very large integer with many factors; if the remaining integer is still composite, then it has only large factors and is factored using general purpose techniques. The largest factor found using ECM so far has 83 digits and was discovered on 7 September 2013 by R. Propper.[1] Increasing the number of curves tested improves the chances of finding a factor, but they are not linear with the increase in the number of digits.

At first I tried brute forcing with the first fifty million primes but that didn't work,Either because none of them really factorized the number or because python was unable to handle the large size of the problem. It felt like cheating but after days of fruitless labour,I just used GMP-ECM( pyecm ) to factorize the monster of a number.

Eric Zhang
Feb 23, 2014

Use http://www.numberempire.com/numberfactorizer.php?number=2639085015233392202740949386309743259521517793886143240989

Takes less than 0.5 seconds, wow.

Louie Tan Yi Jie
Jan 25, 2014

Mathematica: $2639085015233392202740949386309743259521517793886143240989\\ = 3167364220484410988722665601 \times 833211727961546299775962002589$

What happens if we express the number in terms of a large prime (say 99991 which is the largest 5 digit prime) and then reduce the factorization of the number to polynomial factorization and / or factorization of the individual digits ?

Sundar R - 7 years, 4 months ago

Haroun Meghaichi
Jan 24, 2014

Mathematica enhanced :

g = 2639085015233392202740949386309743259521517793886143240989;
k = 2;
While[a, If[Mod[g, Prime[k]] == 0, a = False]; k = k + 1];
Print[Prime[k-1]];

Sage:

n = 2639085015233392202740949386309743259521517793886143240989
k = factor(n)
print( sum(k[0][0].digits()) )

Runs in 8.11 seconds on my machine. I believe Sage uses an underlying quadratic sieve algorithm by default, though one can access GMP-ECM by using "ecm.factor()". For some reason, although theoretically faster for semiprime numbers around 50 digits or so, ECM took a significantly greater time on my machine but the breakdown attributed most of the time as wall time, and ECM took less CPU time (than quadratic sieve).

Shreyas Balaji - 7 years, 4 months ago

The rest is easy, just :

Total[IntegerDigits[Prime[%]];

Haroun Meghaichi - 7 years, 4 months ago

About how long does that program take to run?

Peter Byers - 7 years, 4 months ago

$\approx$ 25 seconds

Shreyas Balaji - 7 years, 4 months ago

Cracking 1980s Encryption

The answer is 115.

5 solutions

Discussions for this problem are now closed

0 pending reports