Q-adic transform revisited

ABSTRACT

We present an algorithm to perform a simultaneous modular reduction of several residues. This enables to compress polynomials into integers and perform several modular operations with machine integer arithmetic. The idea is to convert the X-adic representation of modular polynomials, with X an indeterminate, to a q-adic representation where q is an integer larger than the field characteristic. With some control on the different involved sizes it is then possible to perform some of the q-adic arithmetic directly with machine integers or floating points. Depending also on the number of performed numerical operations one can then convert back to the q-adic or X-adic representation and eventually mod out high residues. In this note we present a new version of both conversions: more tabulations and a way to reduce the number of divisions involved in the process are presented. The polynomial multiplication is then applied to arithmetic and linear algebra in small finite field extensions.

REFERENCES

• 1: Jean-Guillaume Dumas. Efficient dot product over finite fields. In Victor G. Ganzha, Ernst W. Mayr, and Evgenii V. Vorozhtsov, editors, Proceedings of the seventh International Workshop on Computer Algebra in Scientific Computing, Yalta, Ukraine, pages 139--154. Technische Universitat Munchen, Germany, July 2004.
• 2: Jean-Guillaume Dumas, Laurent Fousse, and Bruno Salvy. Compressed modular matrix multiplication. In Milestones in Computer Algebra 2008, Tobago, May 2008.
• 3: Jean-Guillaume Dumas, Thierry Gautier, Pascal Giorgi, Clement Pernet, Jean-Louis Roch, and Gilles Villard. Givaro 3.2.9: C++ library for arithmetic and algebraic computations, 2007. ljk.imag.fr/CASYS/LOGICIELS/givaro.
• 4: Jean Guillaume Dumas , Thierry Gautier , Clément Pernet, Finite field linear algebra subroutines, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.63-74, July 07-10, 2002, Lille, France [doi>10.1145/780506.780515]
• 5: Jean-Guillaume Dumas , Pascal Giorgi , Clément Pernet, FFPACK: finite field linear algebra package, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.119-126, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005304]
• 6: Jean-Guillaume Dumas, Pascal Giorgi, and Clement Pernet. Dense linear algebra over prime fields. ACM Transactions on Mathematical Software, 2008. to appear.
• 7: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 8: Kazushige Goto and Robert van de Geijn. On reducing TLB misses in matrix multiplication. Technical Report TR-2002-55, University of Texas, November 2002. FLAME working note #9.
• 9: Vincent Lefevre. The Euclidean division implemented with a floating-point division and a floor. Technical report, INRIA RhÆone-Alpes, 2005. http://hal.inria.fr/inria-00000154.
• 10: Vincent Lefevre. The Euclidean division implemented with a floating-point multiplication and a floor. Technical report, INRIA RhÆone-Alpes, 2005. http://hal.inria.fr/inria-00000159.
• 11: The LinBox Group. Linbox 1.1.4: Exact computational linear algebra, 2007. www.linalg.org.
• 12: B. David Saunders. Personal communication, 2001.
• 13: Victor Shoup. NTL 5.4.1: A library for doing number theory, 2007. www.shoup.net/ntl.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms

Keywords:
dqt (discrete q-adic transform), finite field, fqt (fast q-adic transform), kronecker substitution, modular polynomial multiplication, redq (simultaneous modular reduction), small extension field