Vector and scalar based modular exponentiation

Patent metadata

Field	Value
Publication number	US-9268564-B2
Application number	US-201213994717-A
Country	US
Kind code	B2
Filing date	May 30, 2012
Priority date	May 30, 2012
Publication date	Feb 23, 2016
Grant date	Feb 23, 2016

Abstract

An embodiment includes a method for computing operations, such as modular exponentiation, using a mix of vector and scalar instructions to accelerate various applications such as encryption protocols that rely heavily on large number arithmetic operations. The embodiment requires far fewer instructions to execute the operations than more conventional practices. Other embodiments are described herein.

First claim

What is claimed is:

1. At least one non-transitory machine readable medium comprising a plurality of instructions that in response to being executed on a computing device, cause the computing device to carry out a method comprising:
converting first and second integers from a first format to a second format; wherein the first and second integers each have more digits in the second format than in the first format and each of the digits in the second format is smaller in bit size than in the first format;
performing an arithmetic operation between the first and second converted digits using both scalar and vector instructions; and
determining a modular exponentiation (ME) based on the arithmetic operation.

2. The at least one medium of claim 1 , the method comprising determining an encryption value based on the ME.

3. The at least one medium of claim 1 , wherein the digits in the first format are stored in equally sized first containers, the method comprising storing the digits in the second format in equally sized second containers that are equal in size to the first containers.

4. The at least one method of claim 3 , wherein:
performing the arithmetic operation using the vector instructions comprises generating a carry value; and
the method comprises storing the carry value in an unused portion of one of the second containers.

5. The at least one method of claim 3 , wherein the first format includes a first radix value, the second format includes a second radix value that is unequal to the first radix value, and the second format is redundant.

6. The at least one method of claim 1 , wherein performing the arithmetic operation using the scalar instructions comprises performing arithmetic and logic (ALU) instructions, and performing the arithmetic operation using the vector instructions comprises simultaneously performing single instruction, multiple data (SIMD) instructions.

7. The at least one medium of claim 1 , wherein performing the arithmetic operation using the scalar and vector instructions comprises simultaneously performing the arithmetic operation on multiple digits in the second format and simultaneously performing the scalar and vector instructions.

8. The at least one medium of claim 1 , wherein the first integer in the first format has a first total number of digits extending to and including most significant and least significant digits, the first integer in the second format has a second total number of digits extending to and including most significant and least significant digits, and the second total number of digits exceeds the first total number of digits.

9. The at least one medium of claim 1 , wherein:
performing the arithmetic operation using the vector instructions comprises generating first and second sub-products; and
the method comprises: determining a first carry value for the first sub-product; and summing the first and second sub-products independently of the first carry value.

10. The at least one medium of claim 1 , wherein:
performing the arithmetic operation using the vector instructions comprises generating first and second sub-products; and
the method comprises:
determining first and second carry values respectively for the first and second sub-products;
summing the first and second sub-products to determine a sum of sub-product values; and
summing the first and second carry values to determine a sum of carry values.

11. The at least one medium of claim 10 , the method comprising:
determining an accumulated valued based on the sum of sub-product values and the sum of carry values; and
formatting the accumulated value in the first format.

12. The at least one medium of claim 1 , the method comprising:
performing the arithmetic operation on least significant digits of the first and second converted digits using the scalar instructions; and
performing the arithmetic operation on most significant digits of the first and second converted digits using the vector instructions.

13. An apparatus comprising:
at least one memory;
at least one processor, coupled to the memory, to perform operations comprising:
converting first and second integers from a first format to a second format; wherein the first and second integers each have more digits in the second format than in the first format and each of the digits in the second format is smaller in bit size than in the first format;
performing an arithmetic operation between the first and second converted digits using both scalar and vector instructions; and
determining a modular exponentiation (ME) based on the arithmetic operation.

14. The apparatus of claim 13 , wherein the digits in the first format are stored in equally sized first containers and the operations comprise:
storing the digits in the second format in equally sized second containers that are equal in size to the first containers; and
storing a carry value, generated using the vector instructions, in an unused portion of one of the second containers.

15. The apparatus of claim 13 , wherein performing the arithmetic operation using the vector instructions comprises simultaneously performing the arithmetic operation on multiple digits in the second format.

16. The apparatus of claim 13 , wherein
performing the arithmetic operation using the vector instructions comprises generating first and second sub-products; and
the operations comprise: determining a first carry value for the first sub-product; and summing the first and second sub-products independently of the first carry value.

17. The apparatus of claim 13 , wherein the operations comprise:
performing the arithmetic operation on least significant digits of the first and second converted digits using the scalar instructions; and
performing the arithmetic operation on most significant digits of the first and second converted digits using the vector instructions.

18. A method executed by at least one processor comprising:
converting first and second integers from a first format to a second format; wherein the first and second integers each have more digits in the second format than in the first format and each of the digits in the second format is smaller in bit size than in the first format;
performing an arithmetic operation between the first and second converted digits using both scalar and vector instructions; and
determining a modular exponentiation (ME) based on the arithmetic operation.

19. The method of claim 18 , wherein:
performing the arithmetic operation using the vector instructions comprises generating first and second sub-products;
the method comprises: determining a first carry value for the first sub-product; and summing the first and second sub-products independently of the first carry value.

20. The method of claim 18 , wherein performing the arithmetic operation using the scalar instructions comprises performing arithmetic and logic (ALU) instructions, and performing the arithmetic operation using the vector instructions comprises simultaneously performing single instruction, multiple data (SIMD) instructions.

Assignees

• Gueron Shay
• Krasnov Vlad
• Intel Corp

Inventors

• Gueron Shay
• Krasnov Vlad

Classifications

• G06F9/3001 Primary

  Arithmetic instructions · CPC title

• G06F7/723 Primary

  Modular exponentiation (G06F7/724, G06F7/727, G06F7/728 take precedence) · CPC title

• G06F2207/3828

  Multigauge devices, i.e. capable of handling packed numbers without unpacking them · CPC title