Fapof programmer guide
======================

Fapof alias factoring polynomials over finite field was created
as a part of school project.

It doesn't use any library for polynomial or big-number manipulation.

The whole project consist of several "modules" or "parts".
They are separated and as long as the needed interface
is provided, they can be freely altered. This is accomplished
by templates [polynomials get a type of finite field,
factorization gets type of finite field and polynomial].
  
The modules are:

- finite fields 
  -------------
  The only finite field is "primal.h". It is just one int,
  therefore the maximum finite field size is 2^31-1 (really a prime).
    All operations ale pretty straightforward, just the mul operation
  uses INTEL assembler. The reason is, that the result of a*b can 
  have up to 62 bits and it must be divided by 31 bit number...
  I had two possibilities - long long [slow] and assembler instruction
  [fast but unportable]. I chose the second possibility. But if
  someone want, they can change the implementation [and see poor result :)]

- polynomials
  -----------
  The fattest module of all.
  It implements operations with polynomials, as fast as possible.
  The operations are coded in different header files, which can
  be included only by polynomial.h.

  Algorithms for the operations are fairly uncommon, you should
  read some polynomial-algebra schoolbook to understand them.

  The most important operation is multiplication, with two implementations
    - recursive approach with time complexity O(n^log_2 3)
    - fft approach with time complexity O(n log_2 n)
  The recursive approach is therefore slower, but it has no other
  demands on the finite field.
    The FFT approach is faster, but when working with polynomials over GF(p),
  it needs GF with at least n*p^2 elements. This could be reduced to
  sqrt(n)*p, which is definitely better, but the FFT would must have been
  run twice and the results combined, which would take time...
    Fapof has a switch to choose the implementation, bench uses
  both and pc uses just recursive approach.

  Most of the operations are implemented as overloaded operators.
  There is a problem in this, because when you write
  c=a+b, the c++ runs operator+(object a, object b), which returns
  another object, which is assigned to c.
    For me, this is unwanted behaviour, because if c had 1000 allocated
  ints, this would deallocate them and allocate 1000 others.
    Therefore, operator+(object a, object b) doesn't return an object,
  but structure to_add { const object &a, &b } instead.
  When this structure is assigned to c, it can compute a+b and
  store the result directly to memory allocated in c.
    I am satisfied with this solution, although it has one disadvantage
  which doesn't matter to me. You cannot write d=a+b+c, because after a+b, 
  there is no operator+, which would add struct to_add and polynomial c. 
  This could be solved
  1) struct to_add could have overloading operator to polynomial
  2) struct to_add would have predecessor operation and there
     would be operator+(operation, object) and the expression
     a+b+c+d+e would create a whole expression tree.

- factorization
  -------------
  This is the core of the project, although it is not very long.
  It uses polynomial and finite field types to factor given polynomial.
  It has static methods factor and test, the first factorise given
  polynomial and the second checks whether the factorization is correct.


The rest is pretty straightforward. Fapof just parse input, call
the factorization method and print the result. Bench factorise,
check that the result is correct, and print the time needed.
And pc is simple calculator using operations from polynomial class.