OKlibrary  0.2.1.6
FiniteFields.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 22.3.2008 (Swansea) */
00002 /* Copyright 2008, 2009, 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_plain_include(gf)$
00023 
00024 /* ***************************************
00025    * Finite Field Wrapper Functions      *
00026    ***************************************
00027 */
00028 
00029 /* The gf_* functions are prefixed with an 'e' for 
00030    extended. These functions perform the same duty as their gf_*,
00031    counterparts, but require additionally an argument, that specifies
00032    which field the operation is being performed over, in the form [p,n,ip]
00033    where "p" is the prime characteristic of the field, "n" is the power to
00034    which "p" is raised, and "ip" the irreducible polynomial over GF(p).
00035    Or, alternatively, just [p,ip]; or even [p].
00036  */
00037 
00038 /*
00039    This function provides a generic wrapper function, taking a function
00040    "func" and a list of arguments "args", with the field structure (defined 
00041    above) as the first element in "args", and the arguments to f as the 
00042    remaining elements.
00043 */
00044 egf_func(func,args) := (
00045     apply(gf_set, first(args)),
00046     apply(func,rest(args)))$
00047 
00048 egf_add([args]) := egf_func('gf_add, args)$
00049 egf_sub([args]) := egf_func('gf_sub, args)$
00050 egf_mul([args]) := egf_func('gf_mult, args)$
00051 egf_div([args]) := egf_func('gf_div, args)$
00052 egf_inv([args]) := egf_func('gf_inv, args)$
00053 egf_matmul([args]) := egf_func('gf_matmult, args)$
00054 egf_matinv([args]) := egf_func('gf_matinv, args)$
00055 egf_exp([args]) := egf_func('gf_exp, args)$
00056 egf_rand([args]) := egf_func('gf_rand, args)$
00057 egf_findprim([args]) := egf_func('gf_primitive, args)$
00058 egf_ind([args]) := egf_func('gf_index, args)$
00059 egf_primep([args]) := egf_func('gf_primitive_p, args)$
00060 egf_poly2num([args]) := egf_func('gf_p2n, args)$
00061 egf_num2poly([args]) := egf_func('gf_n2p, args)$
00062 
00063 /* Functions no longer implemented by Maxima: */
00064 
00065 /* gf_coeffs(p, k), where p is a polynomial with integer coefficients, and
00066    k is an integer, is the list of coefficients of terms x^i, 0 <= i <= k,
00067    in the standard-representation of p, with constant coefficient last;
00068    p must be an polynomial in one indeterminate, and the result will be
00069    expressed in the indeterminate used in gf_set:
00070 */
00071 gf_coeffs(p,k) := block([x,V],
00072  p : gf_add(0,p),
00073  V : listofvars(p),
00074  if not emptyp(V) then x : first(V),
00075  create_list(coeff(p,x,k-i), i,0,k))$
00076 egf_coeffs([args]) := egf_func('gf_coeffs, args)$
00077 
00078 
00079 /* ****************************
00080    * Standard representations *
00081    ****************************
00082 */
00083 
00084 /* Computing the standard polynomial representation in
00085    the field f for a given integer polynomial p: */
00086 gf_stand(p) := gf_add(0,p)$
00087 egf_stand(f,p) := egf_func(gf_stand, [f,p])$
00088 
00089 /* Deciding whether two integer polynomials p,q represent the
00090    same element in the field f: */
00091 gf_equalp(p,q) := is(gf_stand(p) = gf_stand(q))$
00092 egf_equalp(f,p,q) := egf_func(gf_equalp, [f,p,q])$
00093 
00094