Re: Special form numbers factorization

From: Phil Carmody (thefatphil_demunged_at_yahoo.co.uk)
Date: 09/20/04 

Date: 20 Sep 2004 11:38:35 +0300

alessandra_cabrini@virgilio.it (Sandra) writes:

> Hi, I'm studying something about factorization and I have a curiosity.
> I've often read that there are some 'special form numbers' very easy
> to be factored, but I have only find few examples of these numbers.
> Do you know if there is a list of the 'special forms'?

There are some forms which factor algebraically. These are on the
whole of the form (a^n+/-b^n). They factor into cyclotomic numbers.
Some of the cyclotomic numbers factor into Aurefeuillian parts too.
e.g. x^12-1 = Phi(1).Phi(2).Phi(3).Phi(4).Phi(6).Phi(12)
            = (x-1)(x+1)(x^2+x+1)(x^2+1)(x^2-x+1)(x^4-x^2+1)
There's no guarantee that any of those terms is prime, but the large
task of factoring x^12-1 has been split into 6 smaller tasks.

However, if you're thinking of numbers whose factors have a secial form,
and therefore it can be easier to find those factors as there are fewer
places to look, then those would be Cyclotomic numbers which include:
  Mersennes - Phi(p,2), p=prime
  Fermat Numbers - Phi(2^n, 2)
  Generalised Fermat Numbers - Phi(2^n, b)
  Generalised Eisenstein Fermats Norms - Phi(2^n*3^m, b)

Phil 

-- 
They no longer do my traditional winks tournament lunch - liver and bacon. 
It's just what you need during a winks tournament lunchtime to replace lost 
... liver.   -- Anthony Horton, 2004/08/27 at the Cambridge 'Long Vac.'