Smooth As Silk (200 pts)

Question:

11461532818525251775869994369956628325437478510485272730419843320517940601808597552925629451795611990372651568770181872282590309894187815091191649914833274805419432525386234876477307472337026966745408507004000948112191973777090407558162018558945596691322909404307420094584606103206490426551745910268138393804043641876816598599064856358266650339178617149833032309379858059729179857419751093138295863034844253827963.

Write-Up:

The name smooth as silk alludes to smooth numbers, which are integers with very small prime factors.

In this question, is smooth (as we shall see, its only prime factors are 2, 3, 5, and 7).

To factor an integer where is smooth, one can use the Pollard's algorithm. Here, we use the pseudocode due to Katz & Lindell, 2nd Edition (see Section 9.1.1), and turn it into a Sage code.

Prior to running the algorithm, we have to guess the value of the smoothness bound (). Since is very smooth (as smooth as silk!), cannot have too many prime factors, or prime factors which are too large. Hence, we may try the product of primes under 10 or 20. The following code uses the former bound (primes under 10), and succeeds. In other words, we let , where , , , and are computed as the largest possible exponent (i.e., ).

Here's a simple Sage implementation:

#!/usr/bin/env sage

n = 11461532818525251775869994369956628325437478510485272730419843320517940601808597552925629451795611990372651568770181872282590309894187815091191649914833274805419432525386234876477307472337026966745408507004000948112191973777090407558162018558945596691322909404307420094584606103206490426551745910268138393804043641876816598599064856358266650339178617149833032309379858059729179857419751093138295863034844253827963

p2 = floor(log(n,2))
p3 = floor(log(n,3))
p5 = floor(log(n,5))
p7 = floor(log(n,7))

B = 2^p2 * 3^p3 * 5^p5 * 7^p7
R = Integers(n)

while True:
    x = randint(1,n)
    y = (R(x)^B -1)%n
    z = gcd(y,n)
    if z > 1:
        break

p = max(int(z), n/int(z))

import hashlib
m = hashlib.md5()
m.update(str(p))
print(m.hexdigest())

The output is the flag:

c78504a558bdb6213b9019f6925fa4ae

Source Code

Smooth_As_Silk_Pollard.sage.