;; -*- Mode:Lisp; Syntax:ANSI-Common-LISP; Coding:us-ascii-unix; fill-column:158 -*- ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; ;; @file use-polygfp.lisp ;; @author Mitch Richling ;; @date 2015-08-20 ;; @version VERSION ;; @brief Univariate polynomials over prime order fields -- i.e. GF(p)[x].@EOL ;; @std Common Lisp ;; @copyright ;; @parblock ;; Copyright (c) 1997,1998,2004,2010,2015, Mitchell Jay Richling All rights reserved. ;; ;; Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: ;; ;; 1. Redistributions of source code must retain the above copyright notice, this list of conditions, and the following disclaimer. ;; ;; 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions, and the following disclaimer in the documentation ;; and/or other materials provided with the distribution. ;; ;; 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software ;; without specific prior written permission. ;; ;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE ;; IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE ;; LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS ;; OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT ;; LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH ;; DAMAGE. ;; @endparblock ;; @todo Unit Tests!!!@EOL@EOL ;; @todo mjr_polygfp_roots: OPTIMIZE!@EOL@EOL ;; @todo mjr_polygfp_irreducible?: IMPLEMENT!@EOL@EOL ;; @todo mjr_polygfp_factor-berlekamp: IMPLEMENT!@EOL@EOL ;; @todo mjr_polygfp_factor-cantor-zassenhaus: IMPLEMENT!@EOL@EOL ;; @todo mjr_polygfp_factor-shoup: IMPLEMENT!@EOL@EOL ;; @warning This package is experimental.@EOL@EOL ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defpackage :MJR_POLYGFP (:USE :COMMON-LISP :MJR_GFP :MJR_GPOLY) (:DOCUMENTATION "Brief: Univariate polynomials over prime order fields -- i.e. GF(p)[x].;") (:EXPORT #:mjr_polygfp_help ;; Autogenerated from #:mjr_gpoly #:mjr_polygfp_simplify #:mjr_polygfp_diff #:mjr_polygfp_- #:mjr_polygfp_+ #:mjr_polygfp_* #:mjr_polygfp_scale #:mjr_polygfp_truncate #:mjr_polygfp_rem #:mjr_polygfp_mod #:mjr_polygfp_divides? #:mjr_polygfp_iexpt #:mjr_polygfp_imul #:mjr_polygfp_degree #:mjr_polygfp_density #:mjr_polygfp_index #:mjr_polygfp_leading-coeff #:mjr_polygfp_constant-coeff #:mjr_polygfp_zerop #:mjr_polygfp_onep #:mjr_polygfp_eval #:mjr_polygfp_gcd ;; Unique stuff to this polynomial ring #:mjr_polygfp_roots #:mjr_polygfp_irreducible? #:mjr_polygfp_factor-berlekamp #:mjr_polygfp_factor-cantor-zassenhaus #:mjr_polygfp_factor-shoup )) (in-package :MJR_POLYGFP) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun mjr_polygfp_help () "Univariate, dense polynomials over prime order finite fields.. Polynomials are represented as in MJR_POLY." (documentation 'mjr_polygfp_help 'function)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (mjr_gpoly_make-coeff "gfp" "p") (mjr_gpoly_make-simplify "gfp" "p") (mjr_gpoly_make-scale "gfp" "p") (mjr_gpoly_make-+ "gfp" "p") (mjr_gpoly_make-- "gfp" "p") (mjr_gpoly_make-* "gfp" "p") (mjr_gpoly_make-iexpt "gfp" "p") ;;(mjr_gpoly_make-imul "gfp" "p") ;; More efficient to do this (mjr_gpoly_make-eval "gfp" "p") (mjr_gpoly_make-diff "gfp" "p") (mjr_gpoly_make-constant-coeff "gfp" "p") (mjr_gpoly_make-leading-coeff "gfp" "p") (mjr_gpoly_make-degree "gfp" "p") (mjr_gpoly_make-density "gfp" "p") (mjr_gpoly_make-index "gfp" "p") (mjr_gpoly_make-zerop "gfp" "p") (mjr_gpoly_make-onep "gfp" "p") (mjr_gpoly_make-truncate "gfp" "p") (mjr_gpoly_make-mod "gfp" "p") (mjr_gpoly_make-rem "gfp" "p") (mjr_gpoly_make-divides? "gfp" "p") (mjr_gpoly_make-gcd "gfp" "p") ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun mjr_polygfp_imul (p poly n) "See: mjr_poly_imul -- not generated by gpoly for performance." (mjr_polygfp_simplify p (map 'vector (lambda (x) (mjr_gfp_* p x n)) poly))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun mjr_polygfp_roots (p poly) "List of roots of POLY" (loop for i from 0 upto (1- p) when (zerop (mjr_polygfp_eval p poly i)) collect i)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun mjr_polygfp_irreducible? (p poly) "non-NIL if POLY is irreducible References: Michael Rabin (1980); Probabilistic algorithms in finite fields; SIAM Journal on Computing 9; DOI: 10.1137/0209024 http://en.wikipedia.org/wiki/Factorization_of_polynomial_over_finite_field_and_irreducibility_tests http://en.wikipedia.org/wiki/Berlekamp%27s_algorithm" (or p poly)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun mjr_polygfp_factor-berlekamp (p poly) "Factor the square-free polynomial POLY References: Elwyn Berlekamp (1967); Factoring Polynomials Over Finite Fields; Bell Systems Technical Journal 46 Donald Knuth (1997); The Art of Computer Programming. v2 3rd; ISBN: 0201896842; pp439-461,678-691 http://en.wikipedia.org/wiki/Factorization_of_polynomial_over_finite_field_and_irreducibility_tests" (or p poly)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun mjr_polygfp_factor-cantor-zassenhaus (p poly) "Factor the square-free polynomial POLY An equal-degree factorization algorithm. References: David Cantor and Hans Zassenhaus (1981); A New Algorithm for Factoring Polynomials Over Finite Fields; Mathematics of Computation http://en.wikipedia.org/wiki/Factorization_of_polynomial_over_finite_field_and_irreducibility_tests http://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm" (or p poly)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun mjr_polygfp_factor-shoup (p poly) "Factor the square-free polynomial POLY (note that p>2) An equal-degree factorization algorithm. References: Victor Shoup (1990); On the deterministic complexity of factoring polynomials over finite fields; Information Processing Letters http://en.wikipedia.org/wiki/Factorization_of_polynomial_over_finite_field_and_irreducibility_tests" (or p poly))