Re: nfisincl question

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Mar 15, 2018 at 11:53:15PM +0100, Bill Allombert wrote:
> On Thu, Mar 15, 2018 at 07:31:32PM -0300, Ariel Martin Pacetti wrote:
> > 
> > Hello, today I came with the problem of determining whether (the field given
> > by) a quadratic polynomial is contained in a huge and nasty degree 480
> > polynomial. I did not wanted the morphism, just a boolean answer (0,1). I
> > tried to run nfisincl (which seems like the natural routine), but after one
> > hour, and a lot of memory I gave up.
> > 
> > Instead, I tried polcompositum(p,q), and I checked that the output had the
> > same degree as q (the 480 one). This took less than a minute. My question
> > (now that I solved the theoretical question) is whether there is some flag
> > (I did not find it) that allows nfisincl to give a boolean answer without
> > serching for the morphism (as did polcompositum).
> > 
> > As I said, I solved the problem, but there might be another (more efficient)
> > way to do it that I do not know of.
> 
> The problem is that nfisincl tries to factor the small polynomial over the
> quotient field of the big one. It is usually much faster to do the
> opposite. Then you only need to check if there is a factor of the right
> degree.

Your question leads me to design a new algorithm for nfisincl which uses
the factorization of the big polynomial over the quotient field of the
small one, which is much faster!

Cheers,
Bill.