FiniteField(Extension)-Problem

[Ralf Hemmecke]

Hello Johannes,

as one of the authors of the finite field implementation you might
probably be able to tell me what is happening here, see attachment.

The last

coerce(c2)$F4

takes nearly 18 seconds on my laptop (first time only, of course).
That's probably due to the computation of the discrete logarithm table.

Unfortunately, for p>10^6 that makes the finite field implementation
impractical (at least for my purpose).

Actually, I wonder why it takes so long. Is there really need to trigger
the computation of the table. Doesn't this "coerce" (inclusion of F2
into F4) just mean consider c2 as a constant polynomial in the
representation (SAE) of F4?

Maybe some background for my problem.
In fact, I want to implement algebraic numbers via the following paper.

@article{Steel:AlgebraicallyClosedFields:2010,
author = {Allan K. Steel},
title = {Computing with algebraically closed fields},
journal = {Journal of Symbolic Compuation},
volume = 45,
number = 3,
pages = {342--372},
year = 2010,
issn = {0747-7171},
doi = {10.1016/j.jsc.2009.09.005},
url =
{http://www.sciencedirect.com/science/article/pii/S0747717109001497},
keywords = {Algebraic closure, Algebraic number field, Algebraic
function field, Field extension, Inseparability,
Non-perfect field, Polynomial factorization, Root
finding},
}

As far as I understand, this needs an "evaluation (finite) field" in
which there are enough roots. So potentially, I'd need the algebraic
closure of a prime field of a prime characteristic close to machine
integer size.

Any idea how such a field could be implemented in FriCAS?

I thought, I could somehow use FiniteFieldExtension to dynamically grow
this "evaluation field", but the above problem hinders me in thinking
further in this direction.

Ralf

[Prof. Dr. Johannes Grabmeier privat]

I looked at it, but will have to go into more detail, perhaps a good
starting point to revise the whole field staff after 28 years, but would
take its time. Right now I had worked
on a such kind of domains anyway, as for a project I need

TranscendentalExtensionField

and

FiniteTranscendentalExtensionField

etc. to be able to construct towers of field extensions, either
algrebraic or transcendental.


Am 07.11.19 um 17:52 schrieb Ralf Hemmecke:

--
Mit freundlichen Grüßen

Johannes Grabmeier

Prof. Dr. Johannes Grabmeier
Köckstraße 1, D-94469 Deggendorf
Tel. +49-(0)-991-2979584, Tel. +49-(0)-151-681-70756
Tel. +49-(0)-991-3615-141 (d), Fax: +49-(0)-32224-192688

[Waldek Hebisch]

Ralf Hemmecke wrote:
>
> Hello Johannes,
>
> as one of the authors of the finite field implementation you might
> probably be able to tell me what is happening here, see attachment.
>
> The last
>
> coerce(c2)$F4
>
> takes nearly 18 seconds on my laptop (first time only, of course).
> That's probably due to the computation of the discrete logarithm table.

To answer question "what/why takes time" use profiler. sbcl
profiler shows that time is spent in factorizer. Namely to
really build F4 we need an irreducible polymomial. We compute
it by factoring candidates. It is possible that smarter
selection of candidates would limit work in factoring.
But the main point is that ATM factoring over finite field
extentions is slow (over prime fields we use much better
routine).

--
Waldek Hebisch

[Ralf Hemmecke]

> To answer question "what/why takes time" use profiler. sbcl
> profiler shows that time is spent in factorizer.

Thank you. I think that helps me to continue.

Still I would be interested in how exactly I would have use the profiler
and how to interpret the output.

I used what Qian suggested some time ago

)lisp (require :sb-sprof)
)lisp (sb-sprof:start-profiling)
-- fricas computation here
coerce(c2)$F4
)lisp (sb-sprof:stop-profiling)
)lisp (sb-sprof:report)

But couldn't exactly make sense out of the output.
As far as I can tell it just counts the number of times a certain
function is called, but not the time it spents in a function.

Ralf

[oldk1331]

The "Count" you see is not the number of times a certain
function is called, instead, the calling stack is interrupted
and examined periodically to see which function is being called:
so this is a statistical method to get how much time each
function is spending -- the time spent by a function is
proportional to the count it gets during those examination.

Also notice the difference between "Count" and "Total Count",
"Count" means how much time is spent by function body,
"Total Count" means how much time is spent by function body and
sub-function calls.

[Waldek Hebisch]

Counts give estimate for time. Nice feature of sbcl profiler
is that it gives you also estimate for time spent in functions
called from given function. One needs to look for times that
are suspicously high, in this case:

10654 98.1 |FFPOLY;createIrreduciblePoly;PiSup;16| [364]
25 0.2 10654 98.1 |FFPOLY;nextIrreduciblePoly;SupU;11| [62]
1 0.0 |DDFACT;ddffact1| [39]
1 0.0 SB-KERNEL::INTEXP [75]
6 0.1 |LIST;setfirst!;$2S;12| [101]
2 0.0 |FFP;index;Pi$;17| [137]
4 0.0 TRUNCATE [11]
11 0.1 |FFPOLY;revListToSUP| [99]
200 1.8 |SAE;index;Pi$;35| [56]
10399 95.7 |DDFACT;irreducible?;FPB;8| [94]

Indented line ('nextIrreduciblePoly') is function under consideration.
Before is infor about callers, in this case 'createIrreduciblePoly'.
After is info about called functions, clearly 'irreducible?'
dominates here. You can see that also 'index' takes some time.
This is hint that 'nextIrreduciblePoly' makes many iterations.

Looking at 'createIrreduciblePoly' we can see the problem, namely
it starts at x^2. 'nextIrreduciblePoly' linearly increases
constant term checking if result is irreducible. But your
base field is extention of degree 2 of Z_p, so _all_ polynomials
with coefficients in Z_p of degree 2 are reducible over your
field. So 'nextIrreduciblePoly' has any chance of success only
when it passes all 1000002 nonzero elements of Z_p and starts
using elements of the extention.

Attached is a patch that works around the problem: if base field
is an extention of Z_p it starts in place intended to be in
appropriate extention. I wrote "intended" because we have
no warranty that represention of the field is by polynomials
and 'index' may work differently. But in any case it should
avoid long streches of trials in base field where we have
no chance.

Idealy we should make 'createIrreduciblePoly' smarter. For
binomial polynomal there is an easy criterion for existence
of irreducible polynomial: all prime diving n must divide
q - 1 (size of multiplicative group of the field) and if 4
divides n then 4 must divide q - 1. It may happen that
fraction of irreducible binomials is quite low, but there
is systematic procedure to generate them.

I am not sure about trinomials x^n + x + c. It seems that
when there is no irreducible binomial in many cases there is
irreducible trinomial of such a form. But if not, then
we can spent a lot of time trying trinomials of such a form.
So it would be nice to have some results about possiblity
of finding trinomials of such a form.

Another question is rationale for current method. It seems
that Johannes wanted deterministic procedure, that is in each
run generate the same polynomial. Also, there is some gain
if we can use "simple" irreducible polynomials. But then
there is question if "simple" irreducible polynomials
exist and home much time we need to spent to generate
them. Note that in general dense monic polynomial is
irreducible with probablity of order 1/n (where n is
degree of the polynomial), so we could get random
irreducible polynomial in resonable expected time.


--
Waldek Hebisch