Skip to main content
Springer Nature Link
Log in

Arithmetic Unit for Computations in GF(p) with the Left-Shifting Multiplicative Inverse Algorithm

  • Conference paper
Architecture of Computing Systems – ARCS 2013 (ARCS 2013)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7767))

Included in the following conference series:

Abstract

We present the hardware architecture of an arithmetic unit intended for computing basic operations over a Galois field GF(p). The arithmetic unit supports addition, subtraction, multiplication, and multiplicative inverse modulo a prime p. To compute the multiplicative inverse, we use the promising left-shifting algorithm that is based on the extended Euclidean algorithm. We discuss the potential applications of the arithmetic unit, including elliptic curve cryptography.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
CHF34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
CHF 24.95
Price includes VAT (Switzerland)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
CHF 47.00
Price excludes VAT (Switzerland)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
CHF 59.00
Price excludes VAT (Switzerland)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bernal, A.: Conception et Etude d’une Architecture Numerique de Haute Performance pour le Calcul de la Fonction Exponentielle Modulaire. PhD thesis, Institut National Polytechnique de Grenoble (1999)

    Google Scholar 

  2. Ciet, M., Joye, M., Lauter, K., Montgomery, P.L.: Trading Inversions for Multiplications in Elliptic Curve Cryptography. Designs, Codes and Cryptography 39(2), 189–206 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  3. Daly, A., Marmane, W., Kerins, T., Popovici, E.: An FPGA Implementation of a GF(p) ALU for Encryption Processors. Microprocessors and Microsystems 28(5-6), 253–260 (2004)

    Article  Google Scholar 

  4. Meurice de Dormale, G., Bulens, P., Quisquater, J.-J.: An Improved Montgomery Modular Inversion _targeted for Efficient Implementation on FPGA. In: International Conference on Field-Programmable Technology, FPT 2004, pp. 441–444 (2004)

    Google Scholar 

  5. Gutub, A.: New Hardware Algorithms and Designs for Montgomery Modular Inverse Computation in Galois Fields GF(p) and GF(2n). PhD Thesis, Department of Electrical & Computer Engineering, Oregon State University (2002)

    Google Scholar 

  6. Hars, L.: Modular Inverse Algorithms without Multiplications. EURASIP Journal on Embedded Systems 32192:2006, 1–13 (2006)

    Article  Google Scholar 

  7. Hitchcock, Y., Dawson, E., Clark, A., Montague, P.: Implementing an Efficient Elliptic Curve Cryptosystem over GF(p) on a Smart Card. In: Proc. of 10th Computational Techniques and Applications Conference, CTAC 2001. ANZIAM J., vol. 44, pp. C354–C377 (2003)

    Google Scholar 

  8. Hlaváč, J.: Hardware Implementation of Algorithms for Computations in Finite Fields. PhD thesis, Czech Technical University in Prague (2010)

    Google Scholar 

  9. Hlaváč, J., Lórencz, R.: Improved Hardware Architecture for Computing the Modular Inverse using AMI. In: International Conference on Computer, Communication and Control Technologies, CCCT 2003 and ISAS 2003, vol. III, pp. 255–260 (2003)

    Google Scholar 

  10. IEEE Computer Society: IEEE Standard Specifications for Public-Key Cryptography. Document No. IEEE 1363-2000 (2000) ISBN: 0-7381-1956-3

    Google Scholar 

  11. Kaliski Jr., B.S.: The Montgomery Inverse and Its Applications. IEEE Trans. on Computers 44(8), 1064–1065 (1995)

    Article  MATH  Google Scholar 

  12. Knuth, D.E.: The Art of Computer Programming, 3rd edn. Seminumerical Algorithms, vol. 2. Addison-Wesley (1998)

    Google Scholar 

  13. Lórencz, R.: Method for Generating the Multiplicative Inverse in a Finite Field GF(p). U.S. Patent No. 7574469 (2009)

    Google Scholar 

  14. Lórencz, R.: New Algorithm for Classical Modular Inverse. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 57–70. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  15. Montgomery, P.L.: Modular Multiplication Without Trial Division. Mathematics of Computation 44(170), 519–521 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  16. Morháč, M., Lórencz, R.: Modular System for Solving Linear Equations Exactly, I. Architecture and Numerical Algorithms. Computers and Artificial Intelligence 11(4), 351–361 (1992)

    MathSciNet  MATH  Google Scholar 

  17. Wolkerstorfer, J.: Dual-Field Arithmetic Unit for GF(p) and GF(2m). In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 500–514. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  18. Yan, X.: Modified Modular Inversion Algorithm for VLSI Implementation. In: 7th International Conference on ASIC – ASICON 2007, pp. 90–93 (2007)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Information Technology, Czech Technical University in Prague, Thákurova 9, 160 00, Praha, Czech Republic

    Josef Hlaváč & Róbert Lórencz

Authors
  1. Josef Hlaváč
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Róbert Lórencz
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. FIT, Czech Technical University, Thákurova 9, 160 00, Prague 6, Czech Republic

    Hana Kubátová

  2. Elektrotechnik und Informationstechnik, TU Darmstadt, Merckstraße 25, 64283, Darmstadt, Germany

    Christian Hochberger

  3. Department of Signal Processing, Institute of Information Theory and Automation, Pod Vodárenskou věží 4, 18208, Prague 8, Czech Republic

    Martin Daněk

  4. Intelligent Embedded Systems, University of Kassel, Wilhelmshöher Allee 73, 34121, Kassel, Germany

    Bernhard Sick

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hlaváč, J., Lórencz, R. (2013). Arithmetic Unit for Computations in GF(p) with the Left-Shifting Multiplicative Inverse Algorithm. In: Kubátová, H., Hochberger, C., Daněk, M., Sick, B. (eds) Architecture of Computing Systems – ARCS 2013. ARCS 2013. Lecture Notes in Computer Science, vol 7767. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36424-2_23

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-36424-2_23

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-36423-5

  • Online ISBN: 978-3-642-36424-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation

  NODES
Idea 1
idea 1
INTERN 4
Note 2