Multiplicación paralela para una familia de cuerpos finitos

Abstract

Finite fields have many important applications in various fields, including signal processing, coding theory, cryptography and, more recently, in genetic network models. For this reason, a great deal of effort has gone into developing highly efficient implementations of finite field arithmetic, especially multiplication. Development of parallel multiplication algorithms has been directed almost exclusively to finite fields of characteristic 2. In this work we make use of results of Bollman, Ferrer and Orozco to develop a parallel algorithm for finite fields with large characteristic and discuss its implementation on a shared memory machine.

Los cuerpos finitos son de mucha importancia en muchos campos, incluyendo procesamiento de señales digitales, códigos de corrección de errores, criptografía y, más recientemente, en modelos de redes genéticas. Por este motivo, se realiza un gran esfuerzo para desarrollar implementaciones altamente eficientes para realizar la aritmética en cuerpos finitos, especialmente la multiplicación. Actualmente, el desarrollo de algoritmos de multiplicación paralela en cuerpos finitos está enfocado especialmente en cuerpos de característica 2. En este trabajo, hacemos uso de los resultados de Bollman, Ferrer y Orozco, para desarrollar un algoritmo paralelo de multiplicación en cuerpos finitos de característica grande y discutimos su implementación en una computadora con memoria compartida.