OKlibrary  0.2.1.6
FiniteFields.hpp File Reference

Plans on handling finite fields. More...

Go to the source code of this file.


Detailed Description

Plans on handling finite fields.

Todo:
Move to Ringframes/Fields.
Todo:
Write tests for all functions provided
Todo:
Complete docus
  • All functions need to be covered, using prime fields GF(p) and more complex fields GF(p^n).
Todo:
Demos
Todo:
Maxima bugs
  • All items below need to be updated w.r.t. the new Maxima version 5.29 (which is a complete revision).
  • Register all gf-bugs we are aware of with the Maxima bug-tracker, and also send a summarising e-mail to the Maxima mailing list.
    1. Consider also the kind-of-bugs as in, e.g., okltest_gf_stand.
    2. In any way, the gf-documentation should discuss the representation issue.
  • A list of the known bugs here, which can be marked as the bugs are reported to the Maxima bug-tracker and mailing list.
    • "gf_matmul" can not multiply square matrices of dimension 1.
    • This should be solved with Maxima 5.29.1: "gf_exp" returns 1 for "gf_exp(p,-1)" for any "p", i.e the handling of negative exponents is incorrect.
      (%i2) gf_set(2,2,x^2+x+1); 
      Evaluation took 0.0040 seconds (0.0060 elapsed) using 75.617 KB.
      (%o2) true
      (%i3) gf_exp(x,-1);
      Evaluation took 0.0000 seconds (0.0003 elapsed) using 2.305 KB.
      (%o3) 1
           
    • "gf_exp" is defined both as a variable internal to the "gf" package and also as the exponential function. This leads to problems when using "gf_exp" with higher order functions
      (%i2) gf_set(2,1,x);
      Evaluation took 0.0000 seconds (0.0007 elapsed) using 15.203 KB.
      (%o2) true
      (%i3) map(gf_exp,[1],[1]);
      gf_exp evaluates to 1
      Improper name or value in functional position.
       -- an error.  To debug this try debugmode(true);
      (%i4) map('gf_exp,[1],[1]);
      Evaluation took 0.0000 seconds (0.0004 elapsed) using 2.961 KB.
      (%o4) [1]
           
    • DONE (gf_primitive() works now) "gf_findprim" produces an error when called on the field with 2 elements, however 1 is a primitive root of this field
      (%i2) gf_set(2,1,x);
      Evaluation took 0.0000 seconds (0.0007 elapsed) using 15.203 KB.
      (%o2) true
      (%i3) gf_findprim();
      Use `fasttimes' only on CRE polynomials with same varlists
      #0: gf_binpower(p=x,n=2)(gf.mac line 241)
      #1: mainpowers()(gf.mac line 343)
      #2: gf_findprim()(gf.mac line 435)
       -- an error.  To debug this try debugmode(true);
            
    • gf_set(2,1,x) followed by gf_primitive_p(1) yields a Lisp-error. </li.
    • Setting "largefield" to false seems to break "gf_set" for some fields
      (%i2) largefield : false; gf_set(2,2,x^2+x+1);
      Evaluation took 0.0000 seconds (0.0000 elapsed) using 104 bytes.
      (%o2) false
      Use `fasttimes' only on CRE polynomials with same varlists
      #0: gf_binpower(p=x,n=2)(gf.mac line 603)
      #1: mainpowers()(gf.mac line 343)
      #2: gf_findprim()(gf.mac line 435)
       -- an error.  To debug this try debugmode(true);
           
      The same with the example from the documentation, "gf_set(2,4,x^4+x+1);".
    • Perhaps we should set "GF_IRREDUCIBILITY_CHECK : false".
      1. With 5.15.0 the default value is "false".
      2. And actually it seems that whenever it is set to true, and gf-operations are performed, then it is reset to false!. This looks like a bug, which might be corrected in 5.16.3.
    • Perhaps also "largefield : false" should be used, but then we should not permanently reset the field.
      1. With 5.15.0 the default value is "true".
      2. We should ask for the possibility to store and re-store actively the values computed by gf_set.
      3. Setting largefield to false results in 5.15.0 in the error "Use `fasttimes' only on CRE polynomials with same varlists" (when adding 0 to a polynomial).
  • Neither gf_test.mac nor gf_hard_test.mac contains tests for example for findprim.
Todo:
Missing functionality
  • The standard Maxima functions have the field of complex numbers apparently hardcoded?
  • So apparently everything needs to be re-implemented.
  • How to do linear algebra over finite fields?
    1. Only gf_matmul and gf_matinv exist.
    2. We need to check for linear independence; or, more powerful, we need the rank.

Definition in file FiniteFields.hpp.