Home

Podstata vynálezu spočívá ve vytvoření zapojení pro efektivní generování multiplikativní inverze nad konečným tělesem GF(p), kde p je prvočíslo, tj. generováním modulární inverze. Zapojení je upraveno pro binární vykonávání operací v procesu generování modulární inverze, a to vzhledem k co nejmenšímu počtu operací sčítání, odečítání a posuvu. Postup realizovaný navrženým zapojením odstraňuje redundantní operace pro konverzi lichých a záporných hodnot, které jsou prováděny u dosavadních postupů. K tomu se využívá reprezentace záporných čísel v doplňkovém kódu, posun hodnot doleva v řídicí části rozšířeného Euklidova algoritmu a nová definice 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.

In the present invention, there is disclosed a circuit arrangement for generating efficient multiplicative inversion above final GF (p) body wherein p represents a prime number, i.e. by generating modular inversion. The circuit is adapted to carry out operations by binary way within the process of generation of the modular inversion relative to the least possible number of addition, subtraction and shift operations. The process implemented by the circuit here proposed removes redundant operations after conversion of odd and negative values that are carried out in so far employed processes. For this purpose there is used a representation of negative numbers in an additional code, shift of values to left in the control section of Euclid algorithm and novel definition of monitoring and control conditions serving for execution of the process. Minimizing the number of adding and subtracting operations is desirable in case of calculation with large numbers that occur in cryptography.