Hello Oliver,
thank you for your comments which are very valuable to me.
It is true that I adopted the original design concept of the GF package. I
think the concept of using global variables instead of passing them to
every function call is not too bad. From my point of view it allows the
users code to be as simple as possible.
The slow down you experience with gf_set (by the way: I don't understand
why every function should call gf_set) is not caused by working with
globals. After checking the irreducibility of the reduction polynomial
gf_set always (in case of irreducibility) computes a primitive element and
this really takes some time. Computing a primitive is now 5 - 10 times
faster but nevertheless unnecessary if you don't need it or already have
done it. Due to that I created an additional function gf_minset (at the
moment only in git) just to set minimal information to allow GF-arithmetics
on the fly.
A real slow down occurs when a computation permanently has to toggle
between at least two different fields (or quotient rings) and always needs
a full gf_set. In this situation your idea of reusing the already computed
globals would be a way to avoid unnecessary computations. At the moment
gf_set returns a list containing the computed primitive (or false in case
it doesn't exist) and the reduction polynomial. I can imagine to add all
the necessary information to this list which allows another function
"gf_set_again" to reconstruct the field (setting the globals) by this
information without any recomputations.
The recent version of the GF-package contains a lot of improvements and the
arithmetics are much faster. So I hope in the end you will switch back to
it.
Any ideas are welcome.
Thanks and greetings
Volker van Nek
2012/10/25 Oliver Kullmann <O.Kullmann at swansea.ac.uk>
> Hello,
>
> just a few comments:
>
> Exactly for the purpose of implementing AES (and generalisations) we
> looked at using the gf-package in the past, and we used it for some
> time, but then abandoned the gf-package, since it was very slow, and
> also not convenient to use: due to the reliance on global variables, we
> needed to write a wrapper function for every gf-function, which first
> calls gf_set, and that permanent calling of gf_set (since otherwise you
> don't know what's happening!) makes is even slower.
>
> Apparently the design is taken over, and so I doubt that the package can
> be much of use for us.
>
> It would be very helpful if the gf-package itself would provide the
> wrapper-functions, to make the functionalities of the package
> "functional", i.e., not depending on global variables.
> To achieve that, the gf_set function should return a (light-weight)
> object, which contains all the information, and overloaded versions
> of all the functions would take as additional, last parameter this
> object. Then we would have proper, reliably usable functions, and the
> need to permanently call gf_set would disappear.
>
> Oliver
>
> On Thu, Oct 25, 2012 at 10:00:38PM +0200, Volker van Nek wrote:
> > 2012/10/25 Robert Dodier <robert.dodier at gmail.com>
> >
> > > On 2012-10-25, Volker van Nek <volkervannek at gmail.com> wrote:
> > >
> > > > I am working on a package for Galois Fields. I nearly finished
> coding the
> > > > functions but unfortunately at the moment most of them are not
> > > documented.
> > >
> > > Well, in a sense that's good, since I'd like to suggest changing the
> > > name of the function.
> > >
> > > > (%i2) gf_irr_p(x^4+x+1, 2);
> > > > (%o2) true
> > > >
> > > > which means that x^4+x+1 is irredicible over F2,
> > >
> > > I'd like to suggest spelling out "irreducible" in this function name.
> > > Maxima has a tremendous number of functions and variables and it is
> hard
> > > to keep track of them all, so spelling out names makes Maxima as a
> whole
> > > more comprehensible, especially for names which are not widely used.
> > >
> > > It's OK to use abbreviations for commonly-used names. In this case, I
> > > think it's OK to abbreviate Galois field as gf. (Also, 'GF' is a
> typical
> > > abbreviation anyway.)
> > >
> > > So the name I'll suggest is gf_irreducible_p or maybe gf_irreduciblep.
> > >
> >
> > Robert,
> > gf_irreducible_p is OK by me.
> >
> > The following list shows all the GF-functions I put to src. I hope the
> very
> > short and quick comments explain what these functions do. Feel free to
> make
> > any suggestions about other names.
> >
> > As I posted in a previous mail to this list I coded AES encryption as an
> > application and test case for these functions. That showed me which of
> > these are used frequently.
> > E.g. the conversion functions gf_p2n and friends are used quite often
> and I
> > would like to keep them as short as possible.
> > Frequently used are also the arithmetic functions like gf_add and (in
> small
> > fields) the lookup arrays gf_powers and gf_logs.
> >
> > gf_set : set the field parameters and global variables
> > gf_unset : reset the globals to nil
> > gf_minset : set a minimum of information to allow simple GF-arithmetics
> > gf_rat : option variable - the returned polys are of cre or of general
> form
> > gf_char : return the field characteristic set by gf_set
> > gf_prim : return the primitive element computed by gf_set
> > gf_red : return the reduction polynomial set or computed by gf_set
> > gf_info : print information about globals
> > gf_make_arrays : compute the lookup arrays gf_powers and gf_logs
> > gf_powers : global variable - all powers of gf_prim stored in an array
> > gf_logs : global variable - the corresponding logarithms
> > gf_mult_table : show a multiplication table of the field
> > gf_power_table : show a power table of the field
> > gf_add : add field elements
> > gf_sub : subtract field elements
> > gf_mult : mulitply field elements
> > gf_inv : return the inverse of a field element
> > gf_div : divide field elements
> > gf_exp : return the power of a field element
> > gf_exp : return the field exponent when used with no args
> > gf_ind : return the index of a field element
> > gf_log : return a logarithm wrt the primitive or another element
> > gf_p2n : convert a poly to the corresponding number
> > gf_n2p : convert a number to the corresponding poly
> > gf_p2l : convert a poly to a list of coefficients
> > gf_l2p : convert a list of coefficients to a poly
> > gf_l2n : convert a list of coefficients to a number
> > gf_n2l : convert a number to a list of coefficients
> > gf_irr_p : test of irreducibility
> > gf_prim_p : test of primitivity
> > gf_next_prim : find the next primitive element
> > gf_eval : evaluate an arbitrary poly in the context of the field
> > gf_rand : return a random field element
> > gf_factor : factor an arbitrary poly in the context of the field
> > gf_gcd : return the gcd of two field elements
> > gf_gcdex : return the ext gcd of two field elements
> > gf_ord : return the order of the field
> > gf_deg : return the degree of a field element
> > gf_minpoly : return the minimum poly of a field element
> > gf_normal_p : test if an element is normal
> > gf_normal : find a normal element by brute force
> > gf_random_normal : find a normal element by random
> > gf_normal_basis : compute a normal base
> > gf_nbrep : return a normal base representation of a field element
> > gf_matadd : add two matrices
> > gf_matmult : multiply two matrices
> > gf_matinv : return the inverse of a matrix
> >
> >
> > Greetings
> > Volker
> >
> >
>