source: CGBLisp/trunk/src/modular-poly.lisp@ 59

;;; -*- Mode: Lisp; Syntax: Common-Lisp; Package: Grobner; Base: 10 -*-
#|
        $Id: modular-poly.lisp,v 1.2 2009/01/22 04:04:10 marek Exp $
  *--------------------------------------------------------------------------*
  |  Copyright (C) 1994, Marek Rychlik (e-mail: rychlik@math.arizona.edu)    |
  |    Department of Mathematics, University of Arizona, Tucson, AZ 85721    |
  |                                                                          |
  | Everyone is permitted to copy, distribute and modify the code in this    |
  | directory, as long as this copyright note is preserved verbatim.         |
  *--------------------------------------------------------------------------*
|#

(defpackage "MODULAR-POLY"
  (:export modular-trace modular-trace-1)
  (:use "MODULAR" "POLY" "COMMON-LISP"))
    
(in-package "MODULAR-POLY")

(proclaim '(optimize (speed 3) (space 0) (safety 0) (debug 0)))

(defun modular-trace (plist modulus)
  "Return PLIST with coefficients reduced modulo prime MODULUS."
  (mapcar #'(lambda (p) (modular-trace-1 p modulus)) plist))

(defun modular-trace-1 (p modulus)
  "Return a polynomial P with coefficients reduced modulo prime MODULUS."
  (mapcar
   #'(lambda (term) (cons (car term) (mod (cdr term) modulus)))
   p))

(defun frobenius-kernel (n modulus)
  "Return a list of N polynomials of the form XI**MODULUS-XI, where
XI is the I-th variable. Work in internal alist representation."
  (let* ((zero (make-list n :initial-element 0))
         (plist (make-list n :initial-element (list (cons zero 1) (cons zero (- modulus 1))))))
    (dotimes (i n plist)
      (setf (elt plist i) (copy-tree (elt plist i))
            (elt (caar (elt plist i)) i) modulus
            (elt (caadr (elt plist i)) i) 1))))