Dense representation of affine coordinate rings of curves with one point at infinity

ABSTRACT

Traditional methods of representing rational functions on curves are unwieldy and unsuitable for solution of many problems. This paper describes a simple and elegant representation of elements of the affine coordinate ring of an algebraic curve and describes efficient, easy to implement algorithms to perform addition, subtraction, multiplication and polynomial evaluation. This data structure overcomes many of the disadvantages of more unwieldy traditional representations. Elements are represented as vectors of elements of the ground field in a manner similar to the representation of polynomials of one variable as an array of coefficients. This data structure is a fundamental ingredient in the author's decoding method for algebraic geometry codes. The rational function approximation techniques used for decoding could not have been described with multivariate polynomials or truncated infinite series.

REFERENCES

• 1: Goppa, V.D. "Algebraico-Oeometric Codes." Nath . USSR I~est i a . Vol. 21. No. 1. 1983. pp. 75-91.
• 2: Pot k or, S 1 dney C. Decodfrlg Codes A~i$ing F~om Goppa ' $ Construction on Algebraic Cur~es. Ya}e University Ph.D. Dissertation. 1988.
• 3: Porter, Sidney C. "Oecoding Geometric Ooppa Codes." Submitted to IEEE Trans. Inform. Theory.
• 4: Porter, Sidney C. "Euclid's Algorithm, Resultants and Rational Function Representation on Algebraic Curves with a Slngle Point at Infinity." Submitted to iournol of Symbolic Computation.
• 5: Davenport, J.H. On the Zntegration of Algebraic Functions. Lecture Notes in Coaputer Science 102. Spr tnger-Verlag. New York. 1981.
• 6: Seidenberg, A. Elements of the Theory of A}gebrqtc Culves. Addison-Wesley Publishing Co. Reading HA. 1968.
• 7: Porter, Sidney C. "An Efficient Data Structure for Rational Functions on Algebra/c Curves." Submit ted to Journal of Symbolic Computat t on.
• 8: Moreno, Carlos. Algebraic Cu~e$ over Finite Fields and ErTo~ Correcting Codes. Cambridge University Press. 1989.
• 9: Buchberger, B. "Groebner Bases: An Algorithmic ~lethod in Polynomial Ideal Theory." Recent Trends tn Mu I t idimens i on $ys terns Theory, N.K. Bose (ed.). D. Re/de1 Publishing Co. 1985. 184-232.

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  E. Data

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory