Patent ID: 7552164
Filing Date: 2009-06-23
Classification: G06F,H04L

Abstract:
1. A method for accelerating prime sieving of a multiword prime candidate in a computing device, the method comprising: pre-computing a prime-product table by performing a bin packing optimization to create a plurality of prime products in the prime-product table from a fixed set of distinct prime numbers; wherein an objective function of the bin packing optimization is to minimize a number of prime products of the plurality of prime products such that a sum of logarithm of constituent prime numbers used in each prime product in the plurality of prime products is less than logarithm of a single machine word of the computing device, in order to keep the each prime product less than the single machine word; pre-arranging the plurality of prime products to a plurality of ordered prime products in the prime-product table by sorting the plurality of prime products based on a smallest prime number among the constituent prime numbers used in the each prime product; reading the multiword prime candidate from a first memory location in the computing device; partitioning the multiword prime candidate to a plurality of single-word candidate segments; for each ordered prime product in the prime-product table, if the greatest common divisor is greater than one, then incrementing a counter associated with the each ordered prime product in the prime-product table; re-sorting the plurality of ordered prime products to a plurality of re-sorted prime products in the prime-product table based on the counter; and generating RSA keys for security or key management in a cryptographic operator in said computing device, by a RISC processor in a security module in a computer.