Automatically solving equations in finite fields

• US 20020055962A1
• Filed: 04/12/2001
• Published: 05/09/2002
• Est. Priority Date: 11/12/1999
• Status: Abandoned Application

• Current Assignee: Schroeppel, Richard
• Original Assignee: Schroeppel, Richard
• Inventors: Schroeppel, Richard
• Application Number:
  US09/834,363
• Publication Number:
  US 20020055962A1
• Time in Patent Office: Days
• US Class Current: 708/650
• CPC Class Codes: G06F 17/12 Simultaneous equations , e.g. systems of linear equations
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: G06F 7/726 Inversion; Reciprocal calculation; Division of elements of a finite field
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme

Abstract

A new method and apparatus for speeding up cryptographic calculations relies on faster methods for automatically calculating the solutions of certain equations. This includes a faster method for modular division, and a faster method for solving quadratic equations in characteristic 2 fields. The improvement speeds up key exchange, encryption, and digital signatures.

Claims

1. Division

In any circuit or computer program for computing reciprocals in a mathematical system such as a finite field or ring or modular arithmetic system,

where the reciprocal is built up as a linear combination of two or more working variables or registers that are initialized at the start of the computation, and where the building up is a sequence of operations chosen from

shifting a variable,

adding one variable to another,

subtracting one variable from another,

negating a variable,

adding or subtracting a multiple of one variable to or from another,

exchanging variables,

permuting variables,

or renaming variables;

I claim the corresponding method or circuit for computing a quotient of two quantities, a numerator and a denominator, by initializing said working variables or registers, at the start of the computation, to different values, specifically, each working variable or register is initialized to a value equal to the product of the numerator times the corresponding initial value from the reciprocal circuit or program.

2. Quadratic Equations.

I claim any circuit or computer program which solves quadratic equations in a finite field or ring of characteristic 2 of even degree, by adding, subtracting, or xoring selected values from a table, with the selection being determined by examining the coefficients and parameters of the quadratic equation, and quantities derived from the coefficients and parameters, said values being combined together with partial solutions determined by directly examining the coefficients and parameters of the equation and quantities derived from the coefficients and parameters.

3. I claim any method of solving a quadratic equation in a characteristic 2 field or ring that computes some of the solution bits in a first phase, and then fills in the rest of the solution bits in subsequent phases.