revision of finite fields: WITHOUT

[Prof. Dr. Johannes Grabmeier privat]

Hi all,

I started a revision of the field stuff. E.g. Simple algebraic
extensions are MonogenicAlgebra 's, so I included this and learnt, that
in this case one inherits DifferentialExtension with more differential
operators.
I think noone needs them (please indicate, if there are other
opionons).  Actuallly, I also do not know, why we have a trivial
differential operator ( 0) in FiniteFieldCategory, because this category
claims to inherit vom DifferentialRing. Can anyone tell me, who needs
this, otherwise I would like to drop it. In any case, some domains have
functions inherited, which are no longer needed. E.g.
We have a degree function with values in OnePointCompletion
PositiveInteger to allow the degree of a transcendent element to be
infinite. However, in an algebraic extension of a finite field we never
have a transcendent element, hence degree should map to PositiveInteger.
So I want to drop the inherited degree function, because it is
superfluous. .

A suggestion an question to the compiler specialists: Similar to "with"
can't we have a "without" to drop Categories or single functions.

--
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

[Ralf Hemmecke]

Hello Johannes,

That sounds like great news.

For implementation of an ACF a la Steel, it would be good to also have
the algebraic closure of GF(p) implemented. I think that should be
doable by reducing by a triangular set of extension polynomials.

Will you also look into this or should I implement it myself?

Thank you
Ralf

PS: In Aldor instead of "without", I've seen "Meet" (the dual to Join),
but I think that it is also not really implemented in Aldor.

https://github.com/pippijn/aldor/blob/master/aldor/lib/aldor/src/lang/sal_lang.as#L93

[Waldek Hebisch]

Johannes Grabmeier wrote:
>
> I started a revision of the field stuff. E.g. Simple algebraic
> extensions are MonogenicAlgebra 's, so I included this and learnt, that
> in this case one inherits DifferentialExtension with more differential
> operators.
> I think noone needs them (please indicate, if there are other

> opionons).  Actuallly, I also do not know, why we have a trivial

> differential operator ( 0) in FiniteFieldCategory, because this category
> claims to inherit vom DifferentialRing. Can anyone tell me, who needs
> this, otherwise I would like to drop it.

This is mainy issue of consistency: we build structures by recursion,
so trivial cases are necessary as base case. Also, we like to
use generic algorithms and they may need such trivial operations.
So definitely they should be present.

> In any case, some domains have
> functions inherited, which are no longer needed. E.g.
> We have a degree function with values in OnePointCompletion
> PositiveInteger to allow the degree of a transcendent element to be
> infinite. However, in an algebraic extension of a finite field we never
> have a transcendent element, hence degree should map to PositiveInteger.
> So I want to drop the inherited degree function, because it is
> superfluous. .
>
> A suggestion an question to the compiler specialists: Similar to "with"
> can't we have a "without" to drop Categories or single functions.

Again, such inherited functions must be present for consitency:
they may be called by generic routines from categories. It would
be nice to be able to tell compiler and interpreter that they
are "second class" and overload resolution should strongly
prefer other version, but ATM even this is not possible.

--
Waldek Hebisch

[Prof. Dr. Johannes Grabmeier privat]

Hallo Ralf,

I found a criterium for binomials over finite fields to be irreducible,
this can be easily applied to your problem and I will implement this
criterium into FiniteFieldPolynomials in my revision:

(1) -> )r ffproblemSolved
-- of Ralf Hemmecke of Nov. 2019
P ==> PositiveInteger

                                                                                         
Type: Void
                                                                                        
Time: 0 sec
Z ==> Integer

                                                                                         
Type: Void
                                                                                        
Time: 0 sec
SI ==> SingleInteger

                                                                                         
Type: Void
                                                                                        
Time: 0 sec
maxi2 ==> shift(max()$SI, -1)::Z

                                                                                         
Type: Void
                                                                                        
Time: 0 sec
p := qcoerce(prevPrime(maxi2)$IntegerPrimesPackage(Z))@P


   (5)  2305843009213693921
                                                                              
Type: PositiveInteger
                                                                         
Time: 0.00 (OT) = 0.00 sec

p := nextPrime 1000000


   (6)  1000003
                                                                              
Type: PositiveInteger
                                                                                        
Time: 0 sec
F ==> PrimeField p

                                                                                         
Type: Void
                                                                                        
Time: 0 sec
f := (x^4+x+1)::UP('x, F)


         4
   (8)  x  + x + 1
                                                   Type:
UnivariatePolynomial(x,PrimeField(1000003))
                                                                                        
Time: 0 sec
factor f


         4
   (9)  x  + x + 1
                                         Type:
Factored(UnivariatePolynomial(x,PrimeField(1000003)))
                                                                                        
Time: 0 sec
F2 ==> FiniteField(p, 2)

                                                                                         
Type: Void
                                                                                        
Time: 0 sec
ff := factor(f::UP('x, F2))


           2                                      2
   (11)  (x  + 264505 %B x + 244860 %B + 157432)(x  + 735498 %B x +
755143 %B + 157432)
                                      Type:
Factored(UnivariatePolynomial(x,FiniteField(1000003,2)))
                                                  Time: 0.00 (IN) + 0.00
(EV) + 0.00 (OT) = 0.00 sec
fl := factorList ff


   (12)
                               2
   [[flag = "prime", factor = x  + 264505 %B x + 244860 %B + 157432,
exponent = 1],
                               2
    [flag = "prime", factor = x  + 735498 %B x + 755143 %B + 157432,
exponent = 1]]
Type: List(Record(flag: Union("nil","sqfr","irred","prime"),factor:
UnivariatePolynomial(x,FiniteField(1000003,2)),exponent:
NonNegativeInteger))
                                                                                        
Time: 0 sec
c2 := coefficient(fl.1.factor, 0)


   (13)  244860 %B + 157432
                                                                       
Type: FiniteField(1000003,2)
                                                                                        
Time: 0 sec

w : F2 := primitiveElement()


   (14)  %B + 2
                                                                       
Type: FiniteField(1000003,2)
                                                                                        
Time: 0 sec
order w


   (15)  1000006000008
                                                                              
Type: PositiveInteger
                                                                                        
Time: 0 sec
f2 : SUP F2 := monomial(1,2) - w


          2
   (16)  ?  + 1000002 %B + 1000001
                                            Type:
SparseUnivariatePolynomial(FiniteField(1000003,2))
                                                                                        
Time: 0 sec

--F4 ==> FiniteFieldExtension(F2, 2)
F4 ==> FiniteFieldExtensionByPolynomial(F2, f2)

                                                                                         
Type: Void
                                                                                        
Time: 0 sec
coerce(c2)$F4


   (18)  244860 %B + 157432
             Type:
FiniteFieldExtensionByPolynomial(FiniteField(1000003,2),?^2+(1000002*%B+1000001))
                                                                                        
Time: 0 sec




Am 22.11.19 um 17:45 schrieb Ralf Hemmecke:

[Prof. Dr. Johannes Grabmeier privat]

I agree with your arguments. I would be content to have an
WITHOUT-statment, which "only" suppresses output of these functions in
)show and in )hd, perhaps with an additional )showall or so to see also
these still present, but for the user superfluous functions. And of
course the interpreter always should choose the functions of not WITHOUT
first (see my degree example)

Am 23.11.19 um 17:04 schrieb Waldek Hebisch:

[Waldek Hebisch]

Johannes Grabmeier wrote:
> I found a criterium for binomials over finite fields to be irreducible,

Criterion for all fields is given in S. Lang "Algebra", in Polish
edition this is Chaper 8, section 9, theorem 16 (this follows
section on Kummer theory). The criteion is easily specialized
to finite fields. As I wrote one gets from it criterion
for existence of irreducible binomials.

Another question is if we can _quickly_ find irreducible binomial?
Already in Z_p we are in trouble, as fraction of suitable elements
may be quite low. And if we want to use sequential search, then
we are on shaky ground. IIUC already for quadratic extension
ability to quicky find quadratic nonresidue depends on GRH (
generalized Riemman hypothesis).

--
Waldek Hebisch