Class / Patent application number | Description | Number of patent applications / Date published |
708491000 | Residue number | 45 |
20080201398 | Determination of a Modular Inverse - In side-channel attack-resistant encoding methods, a return value (r) is determined as the modular inverse of an input value (a), by a module (M). A resistance to side-channel attack can be achieved with minimal restrictions on implementation on determination of the modular inverse with minimal technical complexity. To this end, in a first sub-step, a first product (d) of the input value (a) and a random number is generated (c), in a second sub-step, the modular inverse (e) of the first product (d) is determined by the module (M), in a third sub-step, a second product (b) of the random number (c) is determined by the modular inverse (e) and in a fourth sub-step the return value (r) is set to the same as the second product (b). | 08-21-2008 |
20080294710 | Extending a Repetition Period of a Random Sequence - A method is provided for extending a sequence repetition period of a random number generator in systems based on the availability of random sequences. The method includes performing RNS arithmetic operations to express a random number in a sequence as RNS residue values. Each generated random number has a value between zero and n!−1. The method also includes converting each of the RNS residue values to a relatively prime base number system so that each of the RNS residue values includes at least one digit. The method further includes generating an arbitrary permutation ordering of output sequence numbers using a select combination of digits associated with each of the RNS residue values. The arbitrary permutation ordering is applied to a cyclic structure having n elements. Each of the n elements has an associated output sequence number. | 11-27-2008 |
20090077151 | Multi-Input, Multi-State Switching Functions and Multiplications - Methods to create an implementation for a multi-input n-state logic function with at least one inverter at an input by modifying the truth table according to the inverter into a reduced truth table are provided. Implementations of the reduced truth table by gates and inverters are also disclosed. Applying reduced truth tables in n-state multiplications are also provided. N-state multiplications may be used in filters, Digital Signal Processing or in Linear Feedback Shift Registers (LFSRs). Using implementations of reduced truth tables in n-state multiplications are disclosed. | 03-19-2009 |
20090089350 | MODULAR REDUCTION OPERATOR - This invention concerns an improved modular reduction device. The modular reduction device includes a multiplier using an alternative of the Montgomery multiplication process using a high numeration base r with r being equal to or greater than 4. It applies more particularly to the calculation components used for asymmetrical cryptography. | 04-02-2009 |
20090100120 | Modular multiplication method, modular multiplier and cryptosystem having the same - Provided are a modular multiplication method with an improved arithmetic operation, a modular multiplier and a cryptograph calculating system having the modular multiplier. The modular multiplication method comprises performing a first arithmetic operation including a first multiplication on a first bit string of a multiplicand and a first bit string of a multiplier and a first reduction for eliminating partial bits of the first multiplication result, performing a second arithmetic operation including a second multiplication on a second bit string of the multiplicand and a second bit string of the multiplier and a second reduction for eliminating partial bits of the second multiplication result, and calculating a modular multiplication result using the result of the first arithmetic operation and the result of the second arithmetic result. The first arithmetic operation and the second arithmetic operation are independently performed. | 04-16-2009 |
20090106342 | Circuit and method for performing multiple modulo mathematic operations - A multi-function modulo processor architecture is capable of performing multiple modulo mathematic operations. The modulo processor includes a pipeline processing portion that iteratively computes a running partial modulo product using the operands of a modulo mathematic argument to obtain one or more final partial modulo products. The final partial modulo product is post-processed to obtain the final result. | 04-23-2009 |
20090119358 | Computational method, system, and apparatus - A method, system, and apparatus for performing computations. | 05-07-2009 |
20090144353 | Method and apparatus for efficient modulo multiplication - A method of a hardware based Montgomery reduction contemplates preparing a table comprising a plurality of sets of values of 2 | 06-04-2009 |
20090240756 | Method for Processing Data Involving Modular Exponentiation and Related Device - A data processing method, whereby an element is subjected to a first operation with a given operand. The method includes a step of updating by a second operation a first variable (B; a | 09-24-2009 |
20090248776 | ADVANCE TRIP COUNT COMPUTATION IN A CONCURRENT PROCESSING ENVIRONMENT - A method for computing a trip count for a loop in advance of the execution of the loop is provided. The method comprises identifying the elements of a loop; returning infinity, if a first index value satisfies a first condition and that a first step size is equal to zero; modifying the first index value and the first step size, if the first index value satisfies the first condition, when the first step size is not equal to zero, and the first step size is greater than half of a first modulus; returning the result computed by applying a formula that divides the difference between a first condition value and the first index value by the first step size and rounds up to a next integer when there is a non-zero remainder; and returning a second trip count for a second loop based on the elements of the first loop. | 10-01-2009 |
20100005131 | Power-residue calculating unit and method of controlling the same - A power-residue calculating unit according to one embodiment of the present invention includes a multiplication residue calculating unit performing a multiplication calculation and a residue calculation based on a multiplicand, a multiplier, and a divisor, a power storing portion separately storing value of each bit when a power is shown by a binary number, a first selecting circuit outputting one of an output of the multiplication residue calculating unit and the multiplicand depending on the value of the bit that is referred, and a result storing register storing an output value of the first selecting circuit as a calculation result. | 01-07-2010 |
20100005132 | APPARATUS AND METHOD FOR GENERATING PERMUTATION SEQUENCE IN A BROADBAND WIRELESS COMMUNICATION SYSTEM - An apparatus and method for generation of an M-length permutation sequence in a broadband wireless communication system are provided. Operations of a generator include splitting an L2-length seed value into a first part and a second part, determining coefficients of a generator polynomial using values of the first part and the second part, and calculating the permutation sequence using the generator polynomial. | 01-07-2010 |
20100005133 | APPARATUS AND METHOD FOR GENERATING PERMUTATION SEQUENCE IN A BROADBAND WIRELESS COMMUNICATION SYSTEM - An apparatus and method for generation of an M-length permutation sequence in a broadband wireless communication system are provided. Operations of a generator include splitting an L2-length seed value into a first part and a second part, determining coefficients of a generator polynomial using values of the first part and the second part, and calculating the permutation sequence using the generator polynomial. | 01-07-2010 |
20100011047 | Hardware-Based Cryptographic Accelerator - A system, method, and apparatus for performing hardware-based cryptographic operations are disclosed. The apparatus can include an encryption device with a hardware accelerator having an accumulator, a multiplier circuit, an adder circuit, and a state machine. The state machine can control successive operation of the hardware accelerator to carry out a rapid, multiplier-based reduction of a large integer by a prime modulus value. Optionally, the hardware accelerator can include a programmable logic device such as a field-programmable gate array with one or more dedicated multiple-accumulate blocks. | 01-14-2010 |
20100023571 | Modular multiplication calculation apparatus used for Montgomery method - REDC (A*B) is calculated for the values A and B by using a Montgomery's algorithm REDC. The part related to the A*B is performed by the three-input two-output product-sum calculation circuit. One digit a | 01-28-2010 |
20100030832 | Method and Apparatus for Performing Computations Using Residue Arithmetic - The subject invention pertains to a method and apparatus for performing computations using residue arithmetic. The subject method and apparatus can utilize logic gates for performing calculations such as multiplication by a constant, computing a number theoretic logarithm of a residue for a given base α | 02-04-2010 |
20100100578 | DISTRIBUTED RESIDUE-CHECKING OF A FLOATING POINT UNIT - A distributed residue checking apparatus for a floating point unit having a plurality of functional elements performing floating-point operations on a plurality of operands. The distributed residue checking apparatus includes a plurality of residue generators which generate residue values for the operands and the functional elements, and a plurality of residue checking units distributed throughout the floating point unit. Each residue checking unit receives a first residue value and a second residue value from respective residue generators and compares the first residue value to the second residue value to determine whether an error has occurred in a floating-point operation performed by a respective functional element. | 04-22-2010 |
20100138467 | METHODS OF CALCULATING NEGATIVE INVERSE OF MODULUS - Provided is a method of calculating a negative inverse of a modulus, wherein the negative inverse, which is an essential element in Montgomery multiplication, is quickly obtained. The method includes setting a modulus, defining P obtained by converting the modulus to a negative number, and defining S obtained by subtracting 1 from P, and calculating a negative inverse of the modulus by using P and S. | 06-03-2010 |
20100146027 | RESIDUE CALCULATION WITH BUILT-IN CORRECTION IN A FLOATING POINT UNIT - A residue generator for calculation and correction of a residue value. The residue generator includes a residue-generation tree connected with an operand register at an input of the residue generator including a plurality of register-bits receiving and carrying bits of numerical data. The residue-generation tree includes a multiplexer connected with respective register-bits which carry unused bits, and selectively providing logical zeros or a correction value when provided, at the respective register-bits carrying the unused bits, a plurality of decoders, each decoder receiving the bits of numerical data from the respective registers-bits including the logical zeros or the correction value when provided and decoding the numerical data, and a plurality of residue condensers, receiving the decoded numerical data from the decoders including the logical zeros or the correction value when provided, and calculating the residue value and correcting while calculating the residue value using the correction value when provided by the multiplexer. | 06-10-2010 |
20100146028 | METHOD AND APPARATUS FOR MODULUS REDUCTION - A modulo reduction is performed on a value a represented as an ordered sequence of computer readable words. The lowest order words are eliminated by substituting an equivalent value represented by higher order words for each of the lower order words. The lowest order words are eliminated until the sequence has a word length corresponding to the modulus. Carries and borrows resulting from the substitution are propagated from lower order words to higher order words. Further reduction is performed to maintain the word length of the sequence to that of the modulus. The further reduction may be determined by examination of a carryover bit or may be performed a predetermined number of times without examination. | 06-10-2010 |
20100146029 | METHOD AND APPARATUS FOR MODULAR OPERATION - The modular operation apparatus of the present invention that enables to improve the tamper resistance to the side channel attacks includes an operator that carries out a Montgomery multiplication according to one of a first multiplicand and a second multiplicand, a multiplier, and a divisor, a first multiplicand register that stores an operation result of the Montgomery multiplication as the first multiplicand, a subtractor that subtracts the divisor from the operation result of the Montgomery multiplication, a second multiplicand register that stores a subtraction result of the subtractor as the second multiplicand, and a selector that outputs one of a value of the first multiplicand register and a value of the second multiplicand register according to a comparison result between the operation result of the Montgomery multiplication and the divisor. | 06-10-2010 |
20100293216 | Modular multiplier apparatus with reduced critical path of arithmetic operation and method of reducing the critical path of arithmetic operation in arithmetic operation apparatus - Provided are a modular multiplier apparatus in which a value of a long path carry (LPC) is predicted to reduce a critical path of an arithmetic operation of Montgomery modular multiplication, and a method of reducing the critical path of the arithmetic operation. The modular multiplier apparatus for obtaining a quotient and a result of an arithmetic operation of modular multiplication by using a modulus and two arbitrary constants includes: a reduction unit for obtaining a short path carry (SPC) included when a result of a modular arithmetic operation is obtained at a current stage, by using a medium calculation result; a carry predictor for predicting a long path carry (LPC) included when the result of the modular arithmetic operation is obtained at the current stage, by using the medium calculation result; and an accumulator for accumulating the result of the modular arithmetic operation by using the SPC and the LPC, wherein the medium calculation result is obtained by adding a result of a modular arithmetic operation obtained at a previous stage and a partial product of the two constants obtained at the current stage. | 11-18-2010 |
20110016168 | METHOD AND APPARATUS FOR MODULO N CALCULATION - A modulo N calculating method for an M1*M2-bit binary integer, wherein N, M1 and M2 are integers, includes the steps of dividing the M1*M2-bit binary integer into M1 bits and performing AND operation on each M1 bits and a specific binary integer; and changing a value of an output register depending on the AND operation result and storing the value thereto. A modulo N calculating apparatus includes an input unit for receiving an M1*M2-bit binary integer, wherein N, M1 and M2 are integers; and an AND operation unit for performing AND operation on the M1*M2-bit binary integer and a specific binary integer. Furthermore, when the M1 and the N may be 4 and 3, respectively, the specific binary value may be 1010 or 0101. | 01-20-2011 |
20110060784 | ARRANGEMENT FOR GENERATING POLY-PHASE SEQUENCES - The electronic circuit arrangement is used for generating poly-phase sequences as synchronization sequences and/or reference sequences in radio communications systems. It comprises a first adder, a first multiplier, a first register, a second register, a first counter and a trigonometry device. The first adder adds a value (k | 03-10-2011 |
20110145311 | METHOD AND APPARATUS FOR MODULO N OPERATION - A method and apparatus for a modulo N operation are provided. The method for a modulo N operation on a positive integer X includes converting the positive integer X into a binary number, determining whether a modulo N is expressed by a product of 2 to the m | 06-16-2011 |
20110161390 | MODULAR MULTIPLICATION PROCESSING APPARATUS - A modular multiplication processing apparatus is provided that can process modular multiplication of data exceeding a bit length which a coprocessor can readily process, by using the coprocessor based upon Montgomery multiplication In the modular multiplication processing apparatus, data to be subjected to modular multiplication is decomposed, and the decomposed data elements are transformed into a form suitable for Montgomery multiplication, respectively. Further, after respective data elements are transformed to have sizes that can be inputted into a coprocessor, Montgomery multiplication is repeatedly performed in the coprocessor. A remainder of Montgomery multiplication of an original bit length is restored from the obtained remainder. | 06-30-2011 |
20110231467 | MONTGOMERY MULTIPLIER HAVING EFFICIENT HARDWARE STRUCTURE - A radix-2k Montgomery multiplier including an input coefficient generation unit to receive a multiplier, a multiplicand, a modulus, a sum and a previous sum, to generate and to output a partial product and a multiple modulus by using at least one of the multiplier, the multiplicand, the modulus and the sum, and to divide and to output the received previous sum into units of k bits, an accumulator circuit to receive the partial product, the multiple modulus and k bits of the previous sum from the input coefficient generation unit, and to generate and to output a carry and a sum by summing the partial product, the multiple modulus and the previous sum, and a carry propagation adder (CPA) circuit to generate and to output an ultimate sum by using the carry and the sum. | 09-22-2011 |
20110270906 | METHOD AND APPARATUS FOR PROVIDING FLEXIBLE BIT-LENGTH MODULI ON A BLOCK MONTGOMERY MACHINE - Techniques are disclosed for utilizing a block Montgomery machine designed only to operate at a fixed block length to perform operations using non-block length (flexible)moduli. In one embodiment, a new modulus n′ is obtained having a block length equal to the fixed block length of the Montgomery machine or a multiple thereof. At least one modular additive operation is performed with the new modulus n′, and at least one modular multiplicative operation is performed with the non-block length modulus n. In this way, the result of the at least one additive operation is sufficiently reduced when a carry stems from the additive operation. | 11-03-2011 |
20120096062 | MODULAR CALCULATOR, OPERATION METHOD OF THE MODULAR CALCULATOR, AND APPARATUSES HAVING THE SAME - A modular calculator and a method of performing a modular calculation are provided. The modular calculator includes a first register to receive and to store a first integer, a second register to receive and to store a second integer, a calculator connected to an output terminal of the first register and an output terminal of the second register, and a controller to determine an arithmetic operation of the calculator by referring to a sign of the first integer and a sign of the second integer and to control the calculator to perform the determined arithmetic operation on one of an addition and a subtraction of the first integer and the second integer and a modulus value. | 04-19-2012 |
20120284319 | METHOD AND APPARATUS FOR PERFORMING COMPUTATIONS USING RESIDUE ARITHMETIC - The subject invention pertains to a method and apparatus for performing computations using residue arithmetic. The subject method and apparatus can utilize logic gates for performing calculations such as multiplication by a constant, computing a number theoretic logarithm of a residue for a given base α | 11-08-2012 |
20120290634 | MODULAR EXPONENTIATION METHOD AND DEVICE RESISTANT AGAINST SIDE-CHANNEL ATTACKS - A modular exponentiation comprising iterative modular multiplications steps and taking as input a first modulus N, a secret exponent d and a base x. During at least one modular multiplication step aiming at computing a result c from two values a, b and the first modulus N so that c=a·b mod N, a processor takes as input the two values a, b and the first modulus N from which are obtained two operands a′, b′ and a second modulus N′ using operations with at most linear complexity—at least one of the two operands a′, b′ is different from the two values a, b, and the two operands a′, b′ are different when a is equal to b—so that the modular multiplication c=a·b mod N from a side-channel viewpoint behaves like a modular squaring except for when a′ equals b′. | 11-15-2012 |
20130080493 | MODULAR EXPONENTIATION WITH PARTITIONED AND SCATTERED STORAGE OF MONTGOMERY MULTIPLICATION RESULTS - Embodiments of techniques and systems for side-channel-protected modular exponentiation are described. In embodiments, during a modular exponentiation calculation, Montgomery Multiplication (“MM”) results are produced. These MM results are scattered through a table for storage, such that storage of the values may not lead to discovery of a secret exponent value by a spy process through a side-channel attack. The scattering may be performed in order to reduce a number of per-result memory operations performed during each MM result storage or retrieval. In embodiments, a window size of 4 may be used in the modular exponentiation, along with partitioning of the MM result into 32-bit partition values which are scattered with offsets of 64-bytes. In embodiments, while use of a window size of 4 may result in additional MM calculations during modular exponentiation than other window sizes, the reduction in memory operations may provide a positive performance offset. | 03-28-2013 |
20130198253 | METHODS OF CALCULATING NEGATIVE INVERSE OF MODULUS - Provided is a method of calculating a negative inverse of a modulus, wherein the negative inverse, which is an essential element in Montgomery multiplication, is quickly obtained. The method includes setting a modulus, defining P obtained by converting the modulus to a negative number, and defining S obtained by subtracting 1 from P, and calculating a negative inverse of the modulus by using P and S. | 08-01-2013 |
20130204916 | RESIDUE-BASED ERROR DETECTION FOR A PROCESSOR EXECUTION UNIT THAT SUPPORTS VECTOR OPERATIONS - A residue generating circuit for an execution unit that supports vector operations includes an operand register and a residue generator coupled to the operand register. The residue generator includes a first residue generation tree coupled to a first section of the operand register and a second residue generation tree coupled to a second section of the operand register. The first residue generation tree is configured to generate a first residue for first data included in the first section of the operand register. The second residue generation tree is configured to generate a second residue for second data included in a second section of the operand register. The first section of the operand register includes a different number of register bits than the second section of the operand register. Configuring a residue-generation tree to be split into multiple residue generation trees facilitates residue checking multiple independent vector instruction operands within a full width dataflow in parallel or alternatively residue checking a full width operand of a standard instruction. | 08-08-2013 |
20130246495 | Quantum Arithmetic On Two-Dimensional Quantum Architectures - 2D nearest-neighbor quantum architectures for Shor's factoring algorithm may be accomplished using the form of three arithmetic building blocks: modular addition using Gossett's carry-save addition, modular multiplication using Montgomery's method, and non-modular multiplication using an original method. These arithmetic building blocks may assume that ancillae are cheap, that concurrent control may be available and scalable, and that execution time may be the bottleneck. Thus, the arithmetic building blocks may be optimized in favor of circuit width to provide improved depth existing nearest-neighbor implementations. | 09-19-2013 |
20130311532 | RESIDUE NUMBER ARITHMETIC LOGIC UNIT - Methods and systems for residue number system based ALUs, processors, and other hardware provide the full range of arithmetic operations while taking advantage of the benefits of the residue numbers in certain operations. In one or more embodiments, an RNS ALU or processor comprises a plurality of digit slices configured to perform modular arithmetic functions. Operation of the digit slices may be controlled by a controller. Residue numbers may be converted to and from fixed or mixed radix number systems for internal use and for use in various computing systems. | 11-21-2013 |
20130311533 | MODULAR MULTIPLIER AND MODULAR MULTIPLICATION METHOD THEREOF - A modular multiplier and a modular multiplication method are provided. The modular multiplier includes: a first register which stores a previous accumulation value calculated at a previous cycle; a second register which stores a previous quotient calculated at the previous cycle; a quotient generator which generates a quotient using the stored previous accumulation value output from the first register; and an accumulator which receives an operand, a bit value of a multiplier, the stored previous accumulation value, and the stored previous quotient to calculate an accumulation value in a current cycle, wherein the calculated accumulation value is updated to the first register, and the generated quotient is updated to the second register. | 11-21-2013 |
20140164462 | RESIDUE-BASED ERROR DETECTION FOR A PROCESSOR EXECUTION UNIT THAT SUPPORTS VECTOR OPERATIONS - A residue generating circuit for an execution unit that supports vector operations includes an operand register and a residue generator coupled to the operand register. The residue generator includes a first residue generation tree coupled to a first section of the operand register and a second residue generation tree coupled to a second section of the operand register. The first residue generation tree is configured to generate a first residue for first data included in the first section of the operand register. The second residue generation tree is configured to generate a second residue for second data included in a second section of the operand register. The first section of the operand register includes a different number of register bits than the second section of the operand register. | 06-12-2014 |
20140164463 | EXPONENT FLOW CHECKING - A technique for checking an exponent calculation for an execution unit that supports floating point operations includes generating, using a residue prediction circuit, a predicted exponent residue for a result exponent of a floating point operation. The technique also includes generating, using an exponent calculation circuit, the result exponent for the floating point operation and generating, using the residue prediction circuit, a result exponent residue for the result exponent. Finally, the technique includes comparing the predicted exponent residue to the result exponent residue to determine whether the result exponent generated by the exponent calculation circuit is correct and, if not, signaling an error. | 06-12-2014 |
20140188965 | RESIDUE BASED ERROR DETECTION FOR INTEGER AND FLOATING POINT EXECUTION UNITS - An error detection unit including one or more register files that store at least one operand and at least one operand residue, an operand multiplexor operable to receive the operand, a residue multiplexor operable to receive the operand residue, a source operand residue generator operable to generate at least one generated residue from the operand, a first comparator that compares the operand residue to the generated residue, the result of the first comparator being sent to a reorder buffer, an execution unit that supplies the operand to a residue calculator and a result residue generator, wherein the residue calculator operable to determine an expected residue and the result residue generator operable to generate a result residue, and a second comparator that compares the expected residue with the result residue, the result of the second comparator being sent to the reorder buffer. | 07-03-2014 |
20150301800 | Modulo9 and Modulo7 Operation on Unsigned Binary Numbers - Simultaneous results of modulo7 and modulo9 operations on an unsigned binary number N are achieved by dividing N by a number d, d being power of 2 then the resulting quotient and remainder are used to calculate modulo 7 and modulo9 by repeatedly split-and accumulate operations. The solution allows shared use of a significant amount of logic components, by a scalable architecture modulo7 and modulo9 can be found on large numbers and allows flexible use if only modulo7 or only modulo9 calculation is required. | 10-22-2015 |
20150339103 | PRODUCT SUMMATION APPARATUS FOR A RESIDUE NUMBER ARITHMETIC LOGIC UNIT - Methods and systems for residue number system based ALUs, processors, and other hardware provide the full range of arithmetic operations while taking advantage of the benefits of the residue numbers in certain operations. In one or more embodiments, an RNS ALU or processor comprises a plurality of digit slices configured to perform modular arithmetic functions. Operation of the digit slices may be controlled by a controller. Residue numbers may be converted to and from fixed or mixed radix number systems for internal use and for use in various computing systems. | 11-26-2015 |
20160004511 | METHOD FOR IMPLEMENTING PRECOMPUTATION OF LARGE NUMBER IN EMBEDDED SYSTEM - Disclosed is a method for implementing precomputation of a large number in an embedded system. A modulo module, a modulo adding module, and a Montgomery modular multiplier are invoked according to a data format of a modulus length and a value of each data bit of a binary number corresponding to the modulus length, to perform an iterative operation, so that a precomputation result of a large number can be obtained when the modulus length is an arbitrary value, thereby improving the data processing speed. | 01-07-2016 |
20160034255 | Arithmetic Devices, Montgomery Parameter Calculation Method and Modular Multiplication Method Thereof - Disclosed are arithmetic devices, a method of a Montgomery parameter calculation thereof and a Montgomery multiplication method thereof. The method of the Montgomery parameter calculation of the arithmetic devices includes detecting a position of a most significant bit (MSB) of a modulus, calculating an initial value using position information about the detected MSB, and calculating an intermediate value and a Montgomery parameter by repeatedly performing a Montgomery addition or a Montgomery multiplication with respect to the initial value. | 02-04-2016 |
20190146756 | SEGMENT DIVIDER, SEGMENT DIVISION OPERATION METHOD, AND ELECTRONIC DEVICE | 05-16-2019 |