The Primitive and Irreducible Polynomial Server (PIPS)
Extension towers over finite fields
This experimental server aims at providing irreducible and primitive polynomials over finite fields. Its primary purpose is to be an example application of the
ZEN library.
Overview
The principle is to build irreducible or primitive polynomials on the current finite field and use them in order to build extension towers. For instance, one can ask a primitive polynomial P(X) of degree 16 over GF(2) and then ask a new irreducible polynomial of degree 32 over the extension GF(2)[X]/P(X), which is a representation of GF(216).
In order to limit the computation load of the server, it is only proposed three levels of extension. Besides, the computational time is limited, and at most two computations can be launched simultaneously.
Cunningham factorization
Since version 1.7 of PIPS, some results of the
Cunningham project
are used to accelerate primitive polynomials computation.
Hints
- Each computation is different from another. The server tries to behaves randomly. Hence, the same question may lead to a solution if you are lucky, and a timeout if you are not.
- Small sub-degree polynomials are harder to find but makes computations faster in the extension.
- Trinomials may be faster to compute.
- Checking primitivity of a polynomial is a time-consuming procedure, since factorization of qd-1 must be performed (no table is used for the moment).
- Don't launch two queries at the same time, it's more likely that you would have timeouts.
- Remember also that some problems may have no solution, and that the server do not check for that. For instance, asking an irreducible trinomial of degree 8 over GF(2) will always result in a timeout.
If you desperately need for an answer to a given problem and the server always ends with a timeout, send me a mail and I will try to make the computation.
The computations may appear long. They are not guaranteed efficient nor correct. This server is experimental and may be down at any time.
Bug report
If you observe strange behavior, please
report
it with the following informations:
- date,
- hour,
- web browser,
- and the host from which you made the query.
As your queries are logged, I try to correct bugs when I notice a query that results in a timeout and should give a solution. Versions of PIPS are indicated at the end of a succesful result.
|
