;; -*- Mode:Lisp; Syntax:ANSI-Common-LISP; Coding:us-ascii-unix; fill-column:158 -*-
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
;; @file      use-polygfp.lisp
;; @author    Mitch Richling <https://www.mitchr.me>
;; @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 <https://www.mitchr.me> 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))