CoCoA » CoCoALib

When char=2 we can readily use (binary) integers to represent field elements.

The idea is to find a generator theta of the cyclic group of units in the finite field; this will also be a field generator. Then the integer 10 = 1010 (binary) represents theta^3+theta^1.

The idea for finding a generator is simply to try all possible monic polynomials of the required degree in increasing lex order until one is found whose root is a generator of the cyclic group (involves factorizing the integer p^deg - 1, not a problem for small values).

If CoCoALib offers a function which creates a (non-prime?) finite field given just its cardinality (or maybe characteristic and extension degree?) then we can choose freely how that field is represented, and what it is an extension of.

Such a "freely determined" finite field should be a simple algebraic extension of F_q[x] where F_q is the (unique?) prime field of characteristic radical(q); see issue #785.

If we construct a F_p[x]/(f) would it be possible to convert it internally to your F_q? (I'm very ignorant on this subject)

Certainly an explicit quotient ring which is a finite field will be isomorphic to one of "my" finite fields. It might even be possible to make the quotient ring recognize when this happens, and then create one of my fields inside itself. To take advantage of this it would also have to create a pair of "complementary" isomorphisms between the two fields; this involves factorizing a univariate polynomial over a (small prime) finite field.

I'd need to implement this to understand how complicated it might become in code.

I have just tried a simplistic speed test (on the "new" computer here in Kassel). The aim was to see how costly it is to convert a "compressed" value into vector<int> where the compressed value is simply "sum of a[i]*b^i" where the base "b" is at least the characteristic of the field.

It simply converted millions of machine integers into vector<int> being a representation in base 3; I then repeated the loop but used bit shifting (by 2 bits) instead of division... so strictly it produced a representation in base 4 instead of base 3. Anyway, division-and-remainder took about 200s whereas bit-shifting took about 36s; that's almost 6 times faster.

ADDENDUM: with base=11, and 4 bits the times were 104s vs 32s

I'm not yet sure what this implies for making a good/fast implementation using log/exp tables.

• (A) use a CoCoALib quotient ring
• (B) use a special impl with vector<int> repr for elements
• (C) use a special impl with "compressed" repr for elements (vector compressed into long)
• (D) use a special "compressed" impl for char 2

(A) already exists; it has no particular limits, but is (very probably) quite slow.
(B) largely exists as a "dirty" prototype; assumes a single generator, only limit is that characteristic must be suitable for SmallFpImpl; should be faster than (A), but I'm not sure how much faster.
(C) is the "most obvious" specialized impl if we want to use log/exp tables for multiplication, but previous comment suggests that conversion between compressed and uncompressed (for addition/substraction) may be costly; there is a limit on cardinality of the extension field;
(D) is the impl Werner desires; the big advantage compared to (C) is that addition can be achieved via xor.

The compression/decompression problem of (C) could be avoided by using the "log(x+1)" trick which enables one to compute x+y = x*(y/x+1); in other words, compute y/x as log(y)-log(x), use the new table to get log(y/x+1), then add log(x), and finally exp the result (if not using a logarithmic repr).

A very simple speed test: compute the order of the field/group generator by naive repeated multiplication.
Prototype impl (B) is typically 10-20 times faster than impl (A).

Since this naive test involves only multiplication, I expect that a log/exp impl would be much faster.

I should also devise a more realistic test; perhaps naive multiplication of two random univariate polys? That will involve as many additions as multiplications (but no divisions).

Another possible test could be gaussian reduction of a random matrix?

JAA will try to implement this before xmas (2015!)
But first some Gluehwein ;-)

Aha! Now you have to click on Edit to add a new progress message (previously it was Update, IIRC).

I have added one simple test (but still tough enough to have unearthed a silly (embarassing) bug last night).
I have added one simple example which I hope covers most of the special extra operations one might need to do to a non-prime finite field.

Still no doc: I am not yet happy with the user interface.

Currently elements of a RingFq print in a non-standard way. I think it is quite easy to read, so am happy to leave it as a temporary solution until a better idea strikes me.

Printing of elems of a (non-prime) finite field needs to be sorted out.

In fact the way an element of a (non-prime) finite field prints is quite independent of how the canonical "lift" to the element in the polyring prints out. So it would be possible to print out the element as a polynomial but with a variable name of our choosing rather than the variable name used in the polyring "sitting above" our quotient ring.

However a user might find it strange that an element of FFq which prints out as 12*sqrt2-17 lifts to 12*x-17, say... assuming we had chosen sqrt2 as the print name inside the quotient ring.

I'm not sure whether this is a good idea or a bad one :-/

John Abbott wrote:

However a user might find it strange that an element of FFq which prints out as 12*sqrt2-17 lifts to 12*x-17, say... assuming we had chosen sqrt2 as the print name inside the quotient ring.

If we choose a name I think we should use it also for creating the associated polynomial ring....(but I think sqrt2 is not a valid symbol name)
Leaving the freedom could lead to some confusion.

ADDENDUM refer to issue #568 for valid symbol heads; sqrt2 is now allowed.

I quite understand the concern about possible confusion.

I am also concerned about creating a "shadow" polyring for every non-prime finite field. My (rather ignorant) guess is that these polyrings will hardly ever be used; they would serve only to "look inside" the structure of an algebraic number.

I suppose the KISS philosophy would favour having the same name in both the polyring and the quotient ring (the alg extn). Perhaps we can implement that, but keep an eye out for possible problems related to the creation of many polyrings (each with its own MemPool).

What name(s) should we use if the user does not supply one? My suggestion would be something like alg[3] or even AlgNum[3], though the longer name could impede readability in a large polynomial with many algebraic coefficients.