Product of prime factors, why?

[the tree]

In my upcoming maths GCSE, I know that I'm likely to get a question asking me to give a number as a product of it's prime factors.

For instance, writing 50 as:[math]2\times 5\times 5[/math] wich is pretty easy, but what's the point? How could this be useful? Does it lead on to something that I might look at at a later stage or something?

[Primarygun]

I am currently studying for a public exam which is more or less equivalent to GCSE.

At my stage, I think it's the best way to find HCF and LCM.

Also, you may find out how many factors does the integer bear. These are what I think.

[matt grime]

All of the internet's security (ok, white lie, but not much of one) is dependent on the difficulty of factoring large numbers into their prime decompositions.

 

Primes are just important everywhere in mathematics, and even in physics.

 

Plus it's rather pretty. Why must maths have utility? Does music? Does poetry? Did you complain about being asked to read Shakespeare too?

[the tree]

All of the internet's security (ok, white lie, but not much of one) is dependent on the difficulty of factoring large numbers into their prime decompositions.

I don't suppose you could explain that? It sounds interesting but I can't see how that'd work.

Plus it's rather pretty. Why must maths have utility? Does music? Does poetry? Did you complain about being asked to read Shakespeare too?

The thing that bugged me about it was that it was too easy. Not exactly satisfying just to do a couple of divisions.

[BigMoosie]

In my upcoming maths GCSE' date=' I know that I'm likely to get a question asking me to give a number as a product of it's prime factors.

For instance, writing 50 as:[math']2\times 5\times 5[/math] wich is pretty easy, but what's the point? How could this be useful? Does it lead on to something that I might look at at a later stage or something?

 

This is called factorising. If you want to simplify:

 

50

---

100

 

Most people can see that quite easily it is 1/2 but for more obscure numbers or in algebra it is necessary to factorise:

 

2 x 5 x 5

------------

2 x 2 x 5 x 5

 

Cancel the common factors:

 

2 x 5 x 5

------------

2 x 2 x 5 x 5

 

You are left with:

 

1

--

2

[the tree]

Bigmoosie, I see what you mean but why would that have to be done with prime factors?

[math]\frac{50}{100} \rightarrow

\frac{2\times25}{4\times25} \rightarrow

\frac{2}{4} \rightarrow

(\frac{2}{4})/2 \rightarrow

\frac{1}{2}[/math]

[matt grime]

You have started the prime factorizations, but in this particular case you do not need to go all the way.

 

Yes, it is trivial to do in one sense, and they are merely checking that you've understood what a prime number is, ie that you reduce to the correct thing and don't leave any composites (non-primes) in there, it also tests your ability to do arithmetic.

 

If you think it is easy please factorize the following number:

 

235342352345234578345653257547967843

 

into its prime factors.

 

How would you do it? Trial and error? Divide by some small numbers? How long do you think it would take you to work out the answer? The simplest method to factor N takes sqrt(N) operations - just divide by all the numbers from 1 to sqrt(N) and see how it factors. That takes a long time, and each operation takes time as well.

 

Internet security, or at least some of it is based around RSA encryption. You can look at their website http://www.rsasecurity.com and see that if you correctly factor a number you can earn money on the RSA challenge. It should also explain RSA encyption to yous somewhere.

 

The basic idea, though, is to use "keys". Given a message encode it as a string of numbers. You can now do some operations on these numbers to get another string and send it over the internet, or anywhere else, and no matter who reads it, and no matter if they also know how to encode the message, no one but the intended recipient can decode it. It relies on various properties of numbers, and prime numbers in particular.

 

I know it's a cop out to omit the details, but they're quite messy, and much better explained out there already - just look around for RSA encryption.

[BigMoosie]

Instead of checking all the way up to the square root of N, each time you find a factor you can divide that from N and take the square root of that and update your maximum.

[matt grime]

I didn't say it was a good way of doing it, I said it was the simplest way of doing it. It is in fact the worst way of doing it without doing somethind deliberately wrong.

[the tree]

Yeh, I'm pretty sure it'd be more tedious than difficult but I see your point. Thanks

[matt grime]

you might also consider that some problems involvinb prime numbers hvae rewards of 1,000,000 USD for a solution.

 

The thind is that primes are incredibly simple things, really very easy to talk about, anyone can learn the definition immediately and start working with them. That's good as we can all play around with them. But, as you'll learn if you do more maths, the simpler something is to talk about the harder it is to do things with them. Things that are really complicated and have long definitions are easy to work with because they are very strongly constrained by their definitions. So we actually have very few tools to help us with prime numbers.

 

We can calculate the square root of a number to thousands of decimal places very easily, but we cannot tell what the 44th Mersenne Prime will be (I think we're up to 43) because we have no clever tools.

 

Hopefully someday we'll find a way to pick out the prime numbers quickly, using a simple formula, but that day, if it iever comes, is many millenia away.

[5614]

Quantum computers will be able to do this all very quickly, it is the basis of quantum cryptology, one of the things with quantum computers is that they'd be able to break any current security system in 1 or 2 minutes (I read that figure a long time back), whilst quantum computers have been built they are not really very powerful yet, I believe either a 2 or 4 quibit (the quantum version of a bit) have been successfully built, this still has a lot of development to go!

 

Other than that we, currently, don't know how to factorise quicker than is being done by security systems at the moment, which really isn't that fast.

[Dave]

Quantum computers will be able to do this all very quickly, it is the basis of quantum cryptology, one of the things with quantum computers is that they'd be able to break any current security system in 1 or 2 minutes (I read that figure a long time back), whilst quantum computers have been built they are not really very powerful yet[/i'], I believe either a 2 or 4 quibit (the quantum version of a bit) have been successfully built, this still has a lot of development to go!

 

I'm not even sure they've got this far to be honest. Quantum computing is rather tricky to implement at best, although the theory behind it appears to be quite sound.

[5614]

ummm, yes they are! (and they're further than 2 qubit as well!)

 

http://web.mit.edu/newsoffice/1999/quantum-0714.html

 

http://www.theory.caltech.edu/people/preskill/ph229/references.html

 

http://wired-vig.wired.com/news/technology/0,1282,35121,00.html

The lab's researchers describe in the Nature paper how they used a test tube of trans-crotonic acid and a powerful nuclear magnetic resonance spectrometer to create the 7-qubit[/b'] (pronounced kew-bit), or quantum bit, quantum computer.

 

http://domino.research.ibm.com/comm/pr.nsf/pages/news.20011219_quantum.html

SAN JOSE, Calif., December 19, 2001 - Scientists at IBM's Almaden Research Center have performed the world's most complicated quantum-computer calculation to date. They caused a billion-billion custom-designed molecules in a test tube to become a seven-qubit quantum computer[/b'] that solved a simple version of the mathematical problem at the heart of many of today's data-security cryptographic systems.

 

Quantum computers and quantum cryptology could factorise large numbers in small amounts of time, no other made/imagined system could/can... yet.

[Dave]

It appears I'm rather mistaken I've not really kept up to scratch on what's been going on, but from those articles it looks rather interesting. As it says, we're not going to have the power to crack things like RSA encryption anytime soon, though.

 

I could go off into a rant about quantum encryption now, but I think that would take this thread rather a way off-topic Needless to say we're safe for the next 10-20 years or so.

[BigMoosie]

As soon as quantum computers have the ability to crack today's security systems, won't they also have the ability to update more secure ones?

 

Anyway, back to practical reasons why factorising is being studied at school, I very much doubt that the teachers have internet security in mind when planning the syllabus . Tree: I do not know what level of maths you are at but have you ever factorisied polynomials? This may help explain its use:

 

Consider:

 

x^3 + 3x^2 - 144x -432

-------------------------

x^3 +12x^2 -9x -108

 

Looks pretty rigit to most younger students, until you factorise it:

 

(x^2 - 144)(x + 3)

------------------

(x^2 - 9)(x + 12)

 

Then:

 

(x + 12)(x - 12)(x + 3)

-----------------------

(x + 3)(x - 3)(x + 12)

 

Cancel common factors:

 

(x - 12)

---------

(x-3)

 

Understanding how to break integers into their prime factoris is pretty important to know how to break polynomials into their prime factors.

[fuhrerkeebs]

As soon as quantum computers have the ability to crack today's security systems, won't they also have the ability to update more secure ones?

 

Yeah...quantum computers will factor huge numbers extremely fast...but we'll also be able to generate huge numbers too. And besides, the quantum effects come built in with certain "security" features, I guess you could call them.

[the tree]

BigMoosie that's pretty impressive, I'm only doing GCSE maths at the moment, but next year I'll be doing mechanical maths at AS level so I imagine I'll be doing stuff like that.

 

What makes a "polynomial"? From your example it looks like an expresion that involves x to powers of 1, 2 and 3; is that right or is it something more specific? We've used quadratics (where the highest power is of 2) and I understand how factorising sometimes helps with that.

[BigMoosie]

I have never heard of GCSE or AS level before, perhaps they do not exist in my country.

 

A polynomial is a term in the form of:

 

a_n.x^n + a_(n-1).x^(n-1) + ... + a_2.x^2 + a_1 x + a_0

 

You can have zero as any of the coefficients.

 

A binomial: 5x + 5

A trinomial (also called quadratic): 3x^2 - 2x + 5

 

Those are polynomials of first and second degrees respectively. A cubic (perhaps also called a quadnomial or tetranomial, I'm not sure the name) is the type of polynomials I used.

 

A polynomial of the 5th degree: ax^5 + bx^4 + cx^3 + dx^2 +ex + f

 

This is not a polynomial: 3x^2 + 5/x

as it is equivalent to: 3x^2 + 5x^-1

and polynomials can only have a natural number as the exponent.

[matt grime]

Of course the syllabus writers didnt' have encryption in mind when they wrote siad syllabus, but that wasn't the question. I doubt writers of French courses have the works of voltaire in mind when they make you learn what the french for vacuum cleaner is either. They are however testing that you can learn a definition and have some numerate skills in manipulating numbers. I'd hope te question (factorize 20 as a product of primes) does seem facile: it is. But then a lot of questions are easy if you know what the definitions are. The aim ought to be "has the person learned what factorize means and prime" not "can we make them unneccesarily jump through hoops".

 

Your usage of monomial, binomial etc is a little incorrect. bi or mono just refers to the number of the terms and doesn't state what the terms must be:

 

x^2+1 is a binomial expression, x^7 is a monomial.