- Any computer with Python 3.

As shown below, Python calculates the square of

python3 a = 1001 a*a

As shown below, Python calculates the square of that 100-digit number correctly also.

a = 10**100 + 1 a*a

As shown below, math.sqrt() gets the wrong answer. Evidently it's rounding the numbers off.

a = 10**100 + 1 b = a * a import math math.sqrt(b)

To see that, execute these commands at the Python prompt:

Now we get the right answer, as shown below.

a = 10**100 + 1 b = a * a from decimal import * getcontext().prec = 200 Decimal(b).sqrt()

What are the factors of this number? Hint: there are two prime factors, and they are close to one another.

**
10000000000000000016800000000000000005031
**

To find the square root, execute these commands at the Python prompt:

The square root is 100000000000000000083 plus a fraction, as shown below.

n = 10000000000000000016800000000000000005031 from decimal import * getcontext().prec = 50 Decimal(n).sqrt()

So one way to find a factor is to test all odd numbers below the square root.

To do that, execute these commands at the Python prompt. Press Enter twice after the last command.

As shown below, the modulus is zero when p is 100000000000000000039, so that's a factor.

n = 10000000000000000016800000000000000005031 p0 = 100000000000000000083 for p in range(p0, p0-50, -2): print(p, n%p)

Notice the "//" operator in the third line: that performs "floor" division, returning an integer value. The "/" operator returns a floating point value, which is not what we want here.

As shown below, q is easily found and verified.

n = 10000000000000000016800000000000000005031 p = 100000000000000000039 q = n//p print(q) print(p * q) print(n - p * q)

The factors are:

p = 100000000000000000039

q = 100000000000000000129

As shown above, the square root of **n**
is 100000000000000000083 (plus a fraction).

As expected, one factor is above the square root and the other is below it.

## C 504.1: Factor this number (10 pts)

123459259296296790129629703704567911111222220989329646370537655992609296463211544461111289984805767The flag is the smaller prime factor, as one long integer, like

11111111111111111111111111111111

## C 504.2: Factor this number (10 pts extra)

2457319490775870034107936327697724401721210936487723795115696610653082228345978452724879092419462602801287921034412592451829320597304383170626854710604026609207557310932504074259543909051122202199219The flag is the smaller prime factor, as one long integer, like

11111111111111111111111111111111

Posted 11-9-17 by Sam Bowne

Added to Crypto Hero 4-16-18 6:43 am

Ported to new scoring engine 7-8-19

Extra credit points specified 9-10-20

Updated for Python 3 11-10-21