A Method for Generating the Multiplicative Inverse over a Finite Field GF(p)
Result description
The essence of the Invention is an effective method for generating the multiplicative inverse in a finite field GF(p) where p is prime, i.e. for generating the modular inverse. This method is derived from the Extended Euclidean Algorithm (EEA). The method is designed for binary execution of operations during the process of generating the modular inverse, with respect to the lowest number of addition, subtraction and shift operations possible. The proposed method avoids redundant operations for converting odd and negative values, which are performed in methods currently in use. To achieve that, negative numbers are represented in the two's complement code, values in the control part of the EEA are shifted to the left, and a new definition of the boundary and control conditions is utilized in the procedure. Minimizing the number of additions and subtractions is desirable for calculations with large numbers often encountered in cryptography.
Keywords
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
čeština
Original language name
Způsob generování multiplikativní inverze nad konečným tělesem GF(p)
Original language description
Podstata řešení spočívá v generování multiplikativní inverse nad konečným tělesem GF(p), kde p je prvočíslo, tj. generováním modulární inverse. Tento postup je odvozen z rozšířeného Euklidova algoritmu. Postup je upraven pro binární vykovávání operací vprocesu generování modulární inverse a to vzhledem na co nejmenší počet operací sčítání, odečítání a posuvu. Navržený přístup odstraňuje redundantní operace pro konverzi lichých a záporných hodnot, které jsou prováděny u dosavadních postupů. K tomu využívá reprezentaci záporných čísel v doplňkovém kódu, posun hodnot doleva v řídící části rozšířeného Euklidova algoritmu a novou definici hlídacích a řídicích podmínek provádění postupu. Minimalizování počtu operací sčítání a odečítání je žádoucí v případěpočítání s velkými čísly, které se vyskytují v kryptografii.
Czech name
Způsob generování multiplikativní inverze nad konečným tělesem GF(p)
Czech description
Podstata řešení spočívá v generování multiplikativní inverse nad konečným tělesem GF(p), kde p je prvočíslo, tj. generováním modulární inverse. Tento postup je odvozen z rozšířeného Euklidova algoritmu. Postup je upraven pro binární vykovávání operací vprocesu generování modulární inverse a to vzhledem na co nejmenší počet operací sčítání, odečítání a posuvu. Navržený přístup odstraňuje redundantní operace pro konverzi lichých a záporných hodnot, které jsou prováděny u dosavadních postupů. K tomu využívá reprezentaci záporných čísel v doplňkovém kódu, posun hodnot doleva v řídící části rozšířeného Euklidova algoritmu a novou definici hlídacích a řídicích podmínek provádění postupu. Minimalizování počtu operací sčítání a odečítání je žádoucí v případěpočítání s velkými čísly, které se vyskytují v kryptografii.
Classification
Type
P - Patent
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2005
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Patent/design ID
294898
Publisher
—
Publisher name
—
Place of publication
—
Publication country
—
Date of acceptance
Feb 7, 2005
Owner name
České vysoké učení technické, Fakulta elektrotechnická, Praha, CZ a Ing. Róbert Lórencz, CSc., Poděbrady, CZ
Method of use
A - Výsledek využívá pouze poskytovatel
Usage type
A - K využití výsledku jiným subjektem je vždy nutné nabytí licence
Basic information
Result type
P - Patent
CEP
JC - Computer hardware and software
Year of implementation
2005