# Device for determining sign of modular number

FIELD: information technology.

SUBSTANCE: device includes input registers for temporary storage of bits of the initial number, memory for storing products

EFFECT: faster operation of the device for determining the sign of a number and reducing equipment.

3 dwg

The invention relates to computing and can be used to determine the signs of modular numbers included in computing device operating in the system of residual classes. It is known device for determining the signs of the numbers represented in the system of residual classes (A.S. NO. 1552181, BI No. 11, 1990), consisting of a block 1 number determination interval, charts 3 and 4 compare, items, or 5 and 6. However, this device has the following disadvantages: low speed and large hardware costs. The closest to the technical nature of the claimed device is a device for determining the sign of the number represented in the system of residual classes (A.S. NO. 1674121, IB No. 32, 1991), containing the block number determination interval, the comparison circuit, group encryption and decryption, the adder and logic elements "or".

The disadvantages of the known devices are low speed determine the sign and large hardware costs.

The aim of the present invention is to improve performance and reduce hardware costs.

This objective is achieved in that in the known device introduced lookup tables (LUT) and a parallel adder.

Consider the method of determining the sign of the number with high performance and low cost equipment is tion.
The method of rapid determination of the sign of modular numbers are based on the use of Chinese theorem rests numbers, which connects the position number And its representations in the residuals (α_{1}α_{2}, ..., α_{n}), where α_{i}the least non-negative residue numbers modulo p_{1}p_{2}, ..., p_{n}.

The numbers α_{i}the view on the selected modules are formed as follows

where_{i}- base (modules) - mutually Prime numbers. In number theory it is proved that if ∀i≠j(p_{i}p_{j})=1, then the representation (1) is only under the condition 0≤A < P, where

Famous Chinese theorem on residues that binds positional number And its representation in the residuals (α_{1}α_{2},...,α_{n}), where α_{i}the smallest non-negative deductions number, relative to the modules of the system of residual classes p_{1}p_{2}, ..., p_{n}the following expression

where_{i}modules JUICE,_{i}relative to p_{i}and

If (3) divided by a constant P, then we obtain an approximate value

where_{i}- the digits that can be represented in the JUICE, while the value of each amount will be in the interval [0, 1). The end result amount is determined after summation and drop the integer part to preserve the fractional part of the sum. The fractional part can be written as Amod1, because

Consider the case where the operating range is divided into two intervals

It is known that when encoding additional code, the negative part of the dynamic range is at the upper limit of the full range. Positive number of additional range are displayed on the area of

This circumstance can lead to the error of the comparison, since negative numbers are in the upper part of the full range and all negative numbers will give errors, which is not true due to the diversity of the dynamic range.

To overcome this difficulty it is necessary to produce a negative shift by residual rotation of the ring in the position indicated in figure 2. The dashed line shows the area that is moved to the beginning of the range.

The result is a negative number will be displayed in the initial part of the dynamic range.

Shown in figure 2, the rotation is called the offset polarity and can be done by adding before the comparison of modular numbers constants

If_{ic}denotes the residual digits after the shift polarity.

The method of determination of such positional characteristics of modular code, as the definition of the sign showed, in contrast to the known, the simplicity of its computation, so as to implement is not in use calculation of the coefficients of the round, which requires large hardware and time costs. For this reason, this method is of particular importance and is one of the best decisions at the present time. These operations are essential for machine modular arithmetic and their use can provide significant benefits not only in applications in which the bulk of computing falls on the exact multiplication, exponentiation of large numbers in combination with addition and subtraction, but also in which often you will need to compare and determine the sign of the number. It is known that coding theorem Szabo says that there is no better method of determining positional characteristics that do not utilize their uniqueness, che is the translation of numbers from the JUICE in the round, because of the magnitude of the numbers in modular representation depend essentially on all residue numbers. However, studies have been conducted to determine the approximate characteristics that solve the problem of formation of structures comparison, do not meet the approval of this theorem clogs. Thus we can conclude that theorem Szabo only works with exact methods.

To improve the efficiency of data processing in modular arithmetic consider the application of approximate methods for determining the sign of the number.

The definition of a symbol of modular numbers

It is known that to determine the sign of the numbers are the numbers of intervals in which there is a number that allows you to obtain an estimate of the investigated number on its value up to a value of the interval. The numerical range of P can be divided into p_{i}interval value

As a second machine zero is chosen point numeric range

If given the representation (α_{1}α_{2},...,α_{n}), in order to establish the sign of the number that it represents the residual to solve the problem of set this number to a specific interval.
If p_{i}=2 it is enough to solve the problem of supplies this number to the first_{1}=2. All known methods implement this algorithm is based on the use of absolute values, here we propose to use relative values, which greatly simplifies the conversion, while maintaining the basic functionality.

Figure 3 shows the diagram of a device for determining the sign of modular integers modulo p_{1}p_{2}, ..., p_{n}.

The device consists of an input register 3 modules p_{1}p_{2}, ..., p_{n}for temporary storage of digits JUICE (each discharge JUICE is represented by a binary code), lookup tables (LUT) for storing works of art constants discharges JUICE._{i}module JUICE,

The operation of the device to determine the sign of the modular number is defined as follows.

The input registers (RGi) 3 input 1 of the device for determining the sign of the number served, the original number is represented in the system of residual classes A=(α_{1}α_{2},...,α_{n}). Output 2 is formed by the modular sign of the number. The outputs of the registers are address inputs lookup tables (LUT) (memory), the elements of which are stored values of

Code number A for which you want to define a gap, which is equivalent to determining the sign of the number, is fed to the input registers RG_{i}in binary code (each digit JUICE is encoded in binary code). The signals from the outputs of the registers are received at the inputs of the lookup table LUT. In the screening tables are stored works constants k_{i}and residues α_{i}

The output signals of the screening tables in additional binary code is fed to the input of the adder, which is already recorded constant of 0.5 during the initial installation. (Additional code is used for the subtraction operation to replace the operation of addition). The sign of the result of the addition interval: first or second, respectively, determines the sign of the number.

Example 4. Let the given system bases p_{1}=2, p_{2}=3, p_{3}=5, p_{4}=7. Then P=210. Constants k_{i}respectively equal to k_{1}=0,5, k_{2}≈0,3333, k_{3}or =0.6, k_{4}≈0,5714.

Given the number of a=(1, 1, 2, 0). You want to determine the sign of the number A.

Solution. In the registers RG_{1}=1, RG_{2}=1, RG_{3}=2, RG_{4}=0. In accordance with these values of registers (address inputs LUT) on the outputs of which are formed of LUT values_{1}=0,5, LUT_{2}=0,3333·1=0,3333,_{4}=0.

Thus, when the summation sign in the discharge of the accumulator is 0, which indicates that the number is in the first interval, so

The definition of a symbol is summation for n, where n is the number of bases (modules) JUICE. Time su the remuneration is determined by the logical depth of the unit (the number of series-connected elements) and time summation adder. To reduce the time summation diagram of the adder can be implemented on the principle of tree (recursive doubling). Additionally, the implementation of the adder can be performed on artificial neural networks.

Device for determining the sign of modular numbers, characterized in that it introduced the input registers for modules p_{1}p_{2}, ..., p_{n}for temporary storage of bits of JUICE, a parallel adder for summing the_{i}the outputs are connected to inputs of the adder, the second input of which receives the constant

**Same patents:**

FIELD: information technology.

SUBSTANCE: device includes input registers, sign determining circuits, number polarity shifting circuits, look-up tables (memory) for storing constants

EFFECT: faster operation of the device and cutting hardware costs.

3 dwg

FIELD: information technology.

SUBSTANCE: method comprises steps of: concurrently writing the remainder on base p_{1} of a multiplicand in memory elements; concurrently counting the number of units b_{i} in each column of the i-th matrix; shifting the binary number b_{1} one bit to the right; summing with a number b_{2}; shifting the obtained sum _{3}. Similarly, the obtained sums are shifted and summed with subsequent numbers to obtain a sum _{1} is the first multiplication bit s_{1}, the least significant bit of each obtained sum _{2*m}. If s is greater than p_{1}, the obtained product s is corrected by successive subtraction of the base p_{1} from s until s is less than p_{1}, otherwise correction is not performed; similarly, products of m-bit residues on the rest of the bases are calculated and corrected; the powers of multipliers are simultaneously summed up and the resultant sum is the power of the determined product.

EFFECT: faster computation.

2 dwg

FIELD: information technology.

SUBSTANCE: device has an n-bit adder, an (n+1)-bit adder, a multiplexer and a register.

EFFECT: broader functional capabilities due to introduction of the modulo addition operation.

1 dwg

FIELD: information technology.

SUBSTANCE: remainder on base p_{i} of a multiplicant is concurrently recorded in matrix memory elements of the i-th multiplier; the number of units b_{i} in each column of the i-th matrix is concurrently counted; the binary number b_{1} is shifted by one bit to the right and summed with number b_{2}; the obtained sum b^{s} _{2} is shifted by one bit to the right and summed with number b_{3}. Similarly, the obtained sums are shifted and summed with subsequent numbers to obtain a sum b^{s} _{2*m-1}, wherein the least significant bit of the number b_{1} is the first multiplication bit s_{1}, the least significant bit of each obtained sum b^{s} _{i} is the i-th multiplication bit. The binary number b^{s} _{2*m-1} is shifted, the least significant bit of the obtained number is the (2*m)-th bit of the determined product s_{2*m}. If s_{i} is greater than p_{i}, the obtained product s_{i} is corrected by successive subtraction of the base p_{i} from s_{i} until s_{i} is less than p_{i}, otherwise correction is not performed; powers of multipliers are simultaneously summed up and the resultant sum is the power of the determined product.

EFFECT: faster computation.

2 dwg

FIELD: information technology.

SUBSTANCE: invention can be used in digital computers as well as digital signal processing devices and cryptographic applications. The device has logic elements NOT, AND, OR.

EFFECT: high speed of operation of the adder due to parallel execution of the modulo addition operation.

1 dwg, 1 tbl

FIELD: information technology.

SUBSTANCE: apparatus has input registers, projection generating circuits, memory units, adders, an analysis circuit, AND logic elements, a flip-flop and a projection counter.

EFFECT: high speed of determining functional characteristics and cutting hardware costs.

1 dwg

FIELD: information technology.

SUBSTANCE: homogeneous computing environment cell has an XOR element, an AND element and two flip-flops.

EFFECT: faster operation and reliability.

3 cl, 6 dwg, 3 tbl

FIELD: information technology.

SUBSTANCE: device for generating remainder on arbitrary modulus of a number has first and second registers, a group of AND elements, a unit of half-adders and a delay element, where the device also includes (K-1) half-adders, to whose second data inputs a modulus code is transmitted, and a number code "1" is transmitted to the first data input of the first half-adder and the second data input of the group of AND elements, the output of the i-th half-adder is connected to the second data input of the group of AND elements and with shift of one bit towards the most significant bits to the first data input of the i+1 half-adder, where i=1,…,K-2, the K-1 output of the half-adder is connected to the second data input of the group of AND elements.

EFFECT: cutting the size of equipment.

2 dwg

FIELD: information technologies.

SUBSTANCE: invention may be used in digital computing devices, and also in devices to generate elements of end fields and in cryptographic applications. The device comprises summators, multipliers, inverters and multiplexors.

EFFECT: expanded range of input number values.

1 dwg

FIELD: information technologies.

SUBSTANCE: device comprises n+1 single-digit parallel summators by module, where n - number of digits of summation numbers, at the same time each single-digit summator by module comprises two single-digit summators, two logical AND elements, a logical OR element, two logical NOT elements.

EFFECT: expansion of functional capabilities of the device by introduction of a summation operation by module.

2 cl, 2 dwg, 1 tbl

FIELD: computers.

SUBSTANCE: device has N blocks for calculating remainders, each of which has N devices for calculating remainders from bases of modular notation scale, including multiplication blocks, module adders of 3N numbers and tabular calculators.

EFFECT: higher speed of operation.

5 dwg, 1 ex

FIELD: computer science.

SUBSTANCE: device has harmonic signal generator, controlled phase changers, means for measuring phase of harmonic signal, phase changers for fixed phase values, transformers of binary number code to unary in accordance to first and second sub-modules, coder and table calculation means.

EFFECT: lower costs.

3 dwg

FIELD: computer science, possible use for engineering of signals processing microprocessors, and of digital filters.

SUBSTANCE: device uses neural-network technologies and polynomial residuals system, wherein as system base minimal polynomials p_{i}(z), where input=1,2,...,n, are utilized, determined in expanded Galois fields GF(2^{V}), while device has clock counter, two blocks for calculating sums of paired results of multiplication by arbitrary base, error correction block, modular adder and block for calculating sums of paired results of multiplication based on control base.

EFFECT: decreased hardware requirements, improved speed of operations.

2 dwg, 3 tbl

FIELD: automatics and computer science, possible use for engineering of computing structures functioning in modular computation system.

SUBSTANCE: device has encoder, controlled phase shifter, harmonic signal generator, phase shifters for fixed phase value, device for measuring the phase of harmonic signal, multiplexer, commutator, amplitude detector and harmonic signal amplifier.

EFFECT: simplified construction of device.

3 dwg

FIELD: computer science, in particular, modular neuron-computer means.

SUBSTANCE: network has input layer of neurons, neuron network of end ring for determining number rank, neuron network of end ring for calculating remainder at base n+1, n-neuron networks of end ring for calculating scaled number, neuron network for calculating difference in numbers between input remainders and base remainder.

EFFECT: decreased volume of equipment, increased speed of numbers rounding and expanded functional capabilities.

1 dwg

FIELD: cryptographic method and chip-card for encoding information, methods for creating electronic signatures.

SUBSTANCE: at least one calculation step is performed, providing for realization of E operation of modular exponentiation in accordance to formula E=x^{d}(mod p·q), where d and mod p·q are components of a secret key, while parallel represent first simple multiplier, q is second simple multiplier, d is level coefficient, and x represents base, while operation E of modular exponentiation is performed in accordance to Chinese theorem about remainders.

EFFECT: decreased amount of computing operations and machine time costs during simultaneous increase of level of data protection from unsanctioned access.

4 cl

FIELD: computer science, possible use in computing devices functioning in system of remainder classes, and also communication equipment for transferring information in remainder classes system codes.

SUBSTANCE: device contains a group of constant memorizing devices, a group of registers, discharge-parallel modulus adder.

EFFECT: decreased volume of equipment and increased speed of operation when transforming a number from remainder classes system to positional code.

1 dwg

FIELD: computer engineering, possible use in digital computing devices, and also in devices for forming elements of finite fields.

SUBSTANCE: device contains adders, inverters, multipliers, multiplexer.

EFFECT: expanded functional capabilities due to expanded range of input number values.

1 dwg

FIELD: computer engineering, possible use in digital computing devices, and also in devices for forming finite field elements.

SUBSTANCE: device contains multiplier, adders, inverters, constant multipliers, multiplexer.

EFFECT: expanded functional capabilities.

1 dwg

FIELD: computer engineering, possible use in digital computing devices for forming code series, creation of which is based on finite fields theory.

SUBSTANCE: device contains block for forming partial remainders, modulus multiplexers, modulus adders.

EFFECT: expanded functional capabilities due to creation of remainders by double modulus, by calculating partial remainders from polynomial powers with their following addition in acc to coefficients of polynomial powers.

3 dwg