Computational Number Theory (Prime Adventure part 1)

Prime Adventure: Learn how to build algorithms (and write code!) which solve number theoretic challenges such as prime factorization. Follow the rest of this adventure on Khan Academy: http://www.khanacademy.org/cs/prime-adventure-level-1/1018672065

We'll return back to 1770, and look at what

Leonard Euler said at the time.

"Mathematicians have tried in vain

to discover some order

in the sequence of prime numbers.

But we have every reason to believe

that there are some mysteries

which the human mind will never penetrate."

Okay?

And thirty years later, here's a quote from Gauss.

"The problem of distinguishing

prime numbers from composite numbers,

and resolving composite numbers into their

prime factors, is known as one of the most

important and useful [problems] in the arithmetic.

All methods that have been proposed thus far

are either restricted to very special cases,

or are so difficult that they try the patience

of even the practiced calculator.

The dignity of science itself seems to require

that every possible means be explored

for the solution of a problem

so elegant and so celebrated."

Wow!

So these two great thinkers have really

set the stage for the challenge ahead of us.

And now, I'm going to fast-forward to 2010,

and show you a paper

that came out of the 'RSA competition' --

which is a competition that no longer runs.

But the purpose of the competition was

to put out a large number and say,

"Can anyone factor it?"

So in 2010, this winning team

factored a 768-bit number.

(And that means it was a 232-digit number,

if you're thinking in base ten.)

So this team -- in 2010 -- they won the competition

by factoring a 232-digit number.

So that's how far we have come from Euler to --

(Or we can go back to Euclid.)

But from Euler to 2010,

we're at 232-digit numbers.

And here was the answer in their paper.

So this was the first prime.

This was p1.

And this was p2.

So this is the state of the art right now.

Okay. How did they factor this number?

And what are the state-of-the-art techniques?

Well, we're going to go back

and build from the beginning.

And this kind of defines 'computational number theory.'

That is the topic of this adventure.

So what does computational number theory mean?

Well, 'computation' comes from the Greek word for 'gravel.'

Stones were used for counting.

Computation is any type of calculation --

whether you're using stones, or a ruler,

or a slide rule, or a calculator,

or this cool looking machine --

which is Babbage's 'Difference Engine' --

which was a hand-powered calculator.

It doesn't matter what you're using

or [if] you're using a computer -- [or not].

You're doing some sort of computation.

And now, what kind of computation are we doing?

Number theory.

And that involves this mysterious distribution

of prime numbers -- studying this distribution.

And what we're actually looking at

is 'multiplicative' number theory --

which is questions of

"How do you factorize numbers?"

"How do you tell me if a number is prime?"

-- and so forth.

And we begin with a very simple question, or --

not a question -- a challenge.

We need to build a machine which takes an input --

(And that input is some integer, 'x.')

And all that machine needs to do

is output 'true' or 'false.'

And that is the first step.

Now we will use the

[Khan Academy] computer-science tool

to actually build this machine together.

And one of the questions

that we will be asking is two things --

two aspects to this machine.

How much time --

That's a clock. [CHUCKLES]

How much time does it take to get the solution?

And how much space does it need?

And when I say 'space,'

I mean -- for example, in the case of

this mechanical calculator -- physical space.

How many rooms do we need to hold our machine?

Or if we're using a computer,

how much memory does it need?

So we will be returning

to these two ideas as we go.