Proj X5: Factoring Large Numbers (20 pts. extra credit)

What you need:

Purpose

To factor large numbers which are the product of two primes that are close together.

Background

In general, factoring a large number is difficult or impossible, if the number is the product of two random large primes. However, if you have some information about the primes, it can be easy. In this case the weakess is that the two primes are close to one another.

1: Accurate Square Roots in Python

Multiplication in Python

Execute these commands at a Terminal or Command Prompt: 
python
a = 1001
a*a
As shown below, Python calculates the square of a correctly.

Large Integers in Python

For simple operations like multiplication and division, Python handles large integers accurately by default. To see that, execute these commands at the Python prompt: 
a = 10**100 + 1
a*a
As shown below, Python calculates the square of that 100-digit number correctly also.

Testing math.sqrt()

However, the math.sqrt() function is not so precise. To see that, execute these commands at the Python prompt: 
a = 10**100 + 1
b = a * a
import math
math.sqrt(b)
As shown below, math.sqrt() gets the wrong answer. Evidently it's rounding the numbers off.

Using the Decimal Library

The Decimal library can be adjusted to be as precise as you like, solving this problem.

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

a = 10**100 + 1
b = a * a
from decimal import *
getcontext().prec = 200
Decimal(b).sqrt()
Now we get the right answer, as shown below.

2. Example: Factoring a Large Number

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

10000000000000000016800000000000000005031

Finding the Square Root

Since the two factors are close together, they must both be close to the square root of that number.

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

n = 10000000000000000016800000000000000005031
from decimal import *
getcontext().prec = 50
Decimal(n).sqrt()
The square root is 100000000000000000083 plus a fraction, as shown below.

Testing Candidate Factors

One factor must be below the square root, and one above it. Also, since both factors are prime, they must both be odd.

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. 

n = 10000000000000000016800000000000000005031
p0 = 100000000000000000083
for p in range(p0, p0-80, -2):
  print p, n%p
As shown below, the modulus is zero when p is 100000000000000000039, so that's a factor.

Finding q

To find the other factor, just divide n by p. To do that, and test the result, execute these commands at the Python prompt. 
n = 10000000000000000016800000000000000005031
p = 100000000000000000039
q = n/p
print q
print p * q
print n - p * q
As shown below, q is easily found and verified.

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.

Challenge 1: Factor this number (10 pts. extra credit)

123459259296296790129629703704567911111222220989329646370537655992609296463211544461111289984805767

Use the form below to put your name on the WINNERS PAGE.

Your Name (without spaces):
The smaller prime factor, as one long integer, like 11111111111111111111111111111111 :
Save a whole-screen image of the winners page showing your name, as shown below, with the filename "YOUR NAME Proj 5x1".

Challenge 2: Factor this number (10 pts. extra credit)

2457319490775870034107936327697724401721210936487723795115696610653082228345978452724879092419462602801287921034412592451829320597304383170626854710604026609207557310932504074259543909051122202199219

Use the form below to put your name on the WINNERS PAGE.

Your Name (without spaces):
The smaller prime factor, as one long integer, like 11111111111111111111111111111111 :
Save a whole-screen image of the winners page showing your name, as shown below, with the filename "YOUR NAME Proj 5x2".

Turning in your Project

Email the images to cnit.141@gmail.com with the subject line: Proj X5 from YOUR NAME.
Posted 11-9-17 by Sam Bowne