# US 10,120,837 B2 · Matrix application apparatus, matrix application method and program

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,120,837 B2
- Document ID: US10120837B2
- Status: Granted
- Kind: B2
- Application number: 15/567,812
- Filed: 2016-05-11
- Published: 2018-04-19
- Granted: 2018-11-06
- Earliest claimed: 2015-05-12
- Assignees: Nippon Telegraph and Telephone Corporation
- Applicants: Nippon Telegraph and Telephone Corporation
- Inventors: Dai Ikarashi
- Web page: https://patentgrep.com/patent/US10120837B2

## CPC

- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F 7/724: {Finite field arithmetic (for error detection or correction in general H03M13/00, in computers G06F11/10)}
- H03M 13/15: Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes (H03M13/17 takes precedence)
- H03M 13/158: {Finite field arithmetic processing}
- H03M 13/1515: {Reed-Solomon codes}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

To reduce the processing amount of a field multiplication. A matrix application apparatus computes a vector b by multiplying a vector a and a matrix A, provided that a denotes a k-th order vector having elements a0, . . . , ak−1 (a0, . . . , ak−1εGF(xq)), b denotes an m-th order vector having elements b0, . . . , bm−1 (b0, . . . , bm−1∈GF(xq)), and A denotes a m-by-k Vandennonde matrix. A polynomial multiplication part computes a value bi. An order reduction part designates gi−hif′ as the value bi by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q.

## Claims

### Claim 1

A matrix application apparatus that computes a vector b by multiplying a vector a and a matrix A, wherein
x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(xq), q denotes an extension degree of the extension field GF(xq), d denotes the order of a term of the highest order of a polynomial f′ obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2, m denotes an integer equal to or greater than 1, (m−1)(k−1)≤q−d, a denotes a k-th order vector having elements a0, . . . , ak−1 (a0, . . . , ak−1 ∈GF(xq)), b denotes an m-th order vector having elements b0, . . . , bm−1(b0, . . . , bm−1∈GF(xq)), A denotes a m-by-k Vandermonde matrix, and
the matrix application apparatus comprising:
circuitry configured to:
compute a value bi for i (i∈{0, . . . , m−1}) according to the following formula:
b
i
=
∑
0
≤
j
<
k
⁢
a
j
⁢
x
ij
;
and
designate gi-hif′ as the value bi for i (i∈{0, . . . , m−1}) by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q.

### Claim 2

A matrix application apparatus that computes a vector b by multiplying a vector a and a matrix A, wherein
x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(xq), q denotes an extension degree of the extension field GF(xq), d denotes the order of a term of the highest order of a polynomial f′ obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2, m denotes an integer equal to or greater than 1, a denotes a k-th order vector having elements a0, . . . ,ak−1 (a0, . . . ak−1∈GF(xq), b denotes an m-th order vector having elements b0. . . , bm−1 (b0, . . . , bm−1∈GF(xq), A denotes a m−by −k Vandermonde matrix, α denotes a positive integer equal to or smaller than q−d, and
the matrix application apparatus comprising:
circuitry configured to:
designate aj and 0 as a′j and dj, respectively, (a′j=aj, dj=0) for j (j∈{0, . . . , k−1});
compute the value bi for i (i∈{0, . . . , m−1}) according to the following formula:
b
i
=
∑
0
≤
j
<
k
⁢
a
j
′
⁢
x
ij
-
d
j
;
designate gi-hif′ as the value bi for i(i∈{0, . . . , m−1}) by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q; and
update a′j and dj according to a′j:=a′jxα and dj:=dj+α, respectively, for i (i∈{0, . . . , m−1}) and j (j∈{0, . . . , k−1}) if i≠m−1 and (i+1)j−d≥q−d.

### Claim 3

A matrix application method of computing a vector b by multiplying a vector a and a matrix A, wherein
x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(xq), q denotes an extension degree of the extension field GF(xq), d denotes the order of a term of the highest order of a polynomial f′ obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2, m denotes an integer equal to or greater than 1, (m−1)(k−1)≥q−d, a denotes a k-th order vector having elements a0, . . . , ak−1 (a0, . . . , ak−1∈GF(xq)), b denotes an m-th order vector having elements b0, . . . , bm−1 (b0, . . . , bm−1∈GF(xq), A denotes a m-by-k Vandermonde matrix, and
the matrix application method comprising:
computing, by circuitry of a matrix application apparatus, a value bi for i(i∈{0, . . ., m−1}) according to the following formula:
b
i
=
∑
0
≤
j
<
k
⁢
a
j
⁢
x
ij
;
and
designating, by circuitry of the matrix application apparatus, gi-hif′ as the value bi for i (i∈{0, . . . , m−1}) by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q.

### Claim 4

A matrix application method of computing a vector b by multiplying a vector a and a matrix A, wherein
x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(xq), q denotes an extension degree of the extension field GF(xq), d denotes the order of a term of the highest order of a polynomial f obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2,m denotes an integer equal to or greater than 1, a denotes a k-th order vector having elements a0, . . . ak−1 (a0, . . . ak−1∈GF(xq)), b denotes an m-th order vector having elements b0, . . . , bm−1 (b0, . . . , bm−1∈GF(xq)), A denotes a m-by-k Vandennonde matrix, α denotes a positive integer equal to or smaller than q−d, and
the matrix application method comprising:
designating, by circuitry of a matrix application apparatus aj and 0 as a′j and dj, respectively, (a′j=aj, dj=0) for j (j∈{0, . . . , k−1});
computing, by circuitry of the matrix application apparatus, the value bi for i (i∈{0, . . . , m−1}) according to the following formula:
b
i
=
∑
0
≤
j
<
k
⁢
a
j
′
⁢
x
ij
-
d
j
;
designating, by circuitry of the matrix application apparatus, gi-hif′ as the value bi for i (i∈{0, . . . , m−1}) by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q; and
updating, by circuitry of the matrix application apparatus, a′j and dj according to a′j:=a′jxα and dj:=dj+α, respectively, for i (i∈{0, . . . , m−1}) and j(j∈{0, . . . , k−1}) if i≠m−1 and (i+1)j−d≥q−d.

### Claim 5

A non-transitory computer readable medium including computer executable instructions that make a matrix application apparatus, wherein
x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(xq), q denotes an extension degree of the extension field GF(xq), d denotes the order of a term of the highest order of a polynomial f′ obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2, m denotes an integer equal to or greater than 1, (m−1)(k−1)≥q−d, a denotes a k-th order vector having elements a0, . . . , ak−1 (a0, . . ., ak−1∈GF(xq)), b denotes an m-th order vector having elements b0, . . . , bm−1 (b0, . . . , bm−1∈GF(xq)), A denotes a m-by-k Vandermonde matrix,
perform a method comprising:
computing, by circuitry of a matrix application apparatus, a value bi for i (i∈{0, . . . , m−1}) according to the following formula:
b
i
=
∑
0
≤
j
<
k
⁢
a
j
⁢
x
ij
;
and
designating, by circuitry of the matrix application apparatus, gi-hif′ as the value bi for i (i∈{0, . . . , m−1}) by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q.

### Claim 6

A non-transitory computer readable medium including computer executable instructions that make a matrix application apparatus, wherein
x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(xq), q denotes an extension degree of the extension field GF(xq), d denotes the order of a term of the highest order of a polynomial f′ obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2, in denotes an integer equal to or greater than 1, a denotes a k-th order vector having elements a0, . . . , ak−1 (a0, . . . , ak−1∈GF(xq), b denotes an m-th order vector having elements b0, . . . , bm−1 (b0. . . , bm−1∈GF(xq)), A denotes a m-by-k Vandermonde matrix, α denotes a positive integer equal to or smaller than q−d, and
perform a method comprising:
designating aj and 0 as a′j and dj, respectively, (a′j=aj, dj=0) for j (j∈{0, . . . , k−1}));
computing the value bi for i (i∈{0, . . . , m−1}) according to the following formula:
b
i
=
∑
0
≤
j
<
k
⁢
a
j
′
⁢
x
ij
-
d
j
;
designating gi-hif′ as the value bi for i (i∈{0, . . . , m−1}) by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q; and
updating and a′j and dj according to a′j:=a′jxα and dj:=dj+α, respectively, for i (i∈{0, . . . , m−1}) and j (j∈{0, . . . , k−1}) if i≠m−1 and (i+1)j−d≥q−d.