Calculation of Fourier-Galois transforms in reduced binary number systems
Chernov V.M.

 

Image Processing Systems Institute оf RAS – Branch of the FSRC “Crystallography and Photonics” RAS, Samara, Russia,
Samara National Research University, Samara, Russia

 PDF

Abstract:
The paper proposes a new method for calculating Fourier-Galois transforms (number-theoretical transforms), which are a modular analog of the discrete Fourier transform. A number of specific problems related to the calculation of transforms in a finite field can be solved by representing the elements of these fields in “exotic” number systems, which are reductions of the canonical number systems proposed by I. Katai when mapping the corresponding ring of an integer quadratic field into a field of the prime residue classes modulo. The case of binary reduced number systems is studied in detail. It is proved that such number systems exist for any prime number.

Keywords:
Fourier-Galois transforms, finite fields, canonical and reduced number systems.

Citation:
Chernov VM. Calculation of Fourier-Galois transforms in reduced binary number systems. Computer Optics 2018; 42(3): 495-500. DOI: 10.18287/2412-6179-2018-42-3-495-500.

References:

  1. Nussbaumer HJ. Fast Fourier transform and convolution algorithms. Berlin, Heidelberg: Springer-Verlag; 1982. ISBN: 978-3-540-11825-1.
  2. Blahut RE. Fast algorithms for digital signal processing. Boston, MA: Addison-Wesley Publishing Company, Inc.; 1985. ISBN: 978-0201101553.
  3. Rader C.M. Discrete convolution via Mersenne transforms. IEEE Trans Comp 1972; C-21(12): 1269-1273. DOI: 10.1109/T-C.1972.223497.
  4. Schönhage A, Strassen V. Schnelle Multiplikation großer Zahlen. Computing 1966; 7(3-4): 281-292. DOI: 10.1007/BF02242355.
  5. Varichenko LV, Labunetc VG, Rakov MA. Abstract algebraic systems and digital signal processing [In Russian]. Kiev, “Naukova dumka” Publisher; 1986.
  6. Alfredson L-I. VLSI architectures and arithmetic operations with application to the Fermat number transform. Linköping, Sweden: Linköping University, 1996. ISBN: 91-7871-694-2.
  7. Golomb SW. Properties of the sequence 3•2n+1. Math Computing 1976; 30(135): 657-663. DOI: 10.1090/S0025-5718-1976-0404129-8.
  8. Chernov VM. Fast algorithm for “error-free” convolution computation using Mersenne–Lucas codes. Chaos, Solitons and Fractals 2006; 29(2): 372-380. DOI: 10.1016/j.chaos.2005.08.081.
  9. Chernov VM. Quasiparallel algorithm for error-free convolution computation using reduced Mersenne–Lucas codes [In Russian]. Computer Optics 2015; 39(2): 241-248. DOI: 10.18287/0134-2452-2015-39-2-241-248.
  10. Chernov VM. Arithmetic methods of fast algorithm of discrete orthogonal transforms synthesis [In Russian]. Moscow: “Fizmathlit” Publisher; 2007. ISBN: 5-9221-0940-6.
  11. Koblitz N. Algebraic aspects of cryptography. Berlin, Heidelberg: Springer-Verlag; 1998. ISBN: 978-3-540-63446-1.
  12. Borevich ZI, Shafarevich IR. Number theory. New York, London: Academic Press Inc; 1966.
  13. Kátai I, Kovács B. Canonical number systems in imaginary quadratic fields. Acta Mathematica Hungarica 1981; 37(1-3): 159-164. DOI: 10.1007/BF01904880.
  14. Bogdanov PS, Chernov VM. Classification of binary quasicanonical number systems in imaginary quadratic fields [in Russian]. Computer Optics 2013; 37(3): 391-400.
  15. Thuswardner J. Elementary properties of canonical number systems in quadratic fields. In Book: Bergum GE, Philippou AN, Horadam AF, eds. Application of Fibonacci numbers. Dordrecht: Springer; 1998: 405-414. DOI: 10.1007/978-94-011-5020-0_45.
  16. Bogdanov PS. On convergence some algorithms of binary and ternary machine arithmetic for calculations in imaginary quadratic fields [In Russian]. Computer Optics 2015; 39(2): 249-254.
  17. Ireland K, Rosen M. A classical introduction to modern number theory. New York: Springer-Verlag; 1982.
  18. The on-line encyclopedia of Integer Sequences® (OEIS®). Source: áhttps://oeis.org/ñ.
  19. Gregory RT, Krishnamurty EV. Methods and applications of error-free computation. New York: Springer; 1984. ISBN: 978-1-4612-9754-3.
© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: journal@computeroptics.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20