Efficient exponentiation method and apparatus

Apparatus for calculating an encrypted value representing a data string raised to a power represented by a processed exponent value, the apparatus comprising:

• means for applying a signed digit algorithm to the processed exponent value to generate a processed exponent value;
• a look-up table of substrings that are likely to be encountered in the processed exponent value each entry in the look-up corresponding to the data string raised to the power represented by the respective substring;
• means for applying a string replacement method to traverse the processed exponent value and to record pointers to the values in the look-up table that correspond to the matching substrings in the processed exponent value and to replace the matching substrings in the processed exponent value by zeros to produce a modified exponent value;
• and
• means for applying a multiply-square chain algorithm to the modified exponent value to calculate the encrypted value representing the data string raised to the processed exponent value.

A computer readable carrier including computer program instructions, the instructions causing a computer to perform a method calculating a value representing a data string raised to a power represented by a processed exponent value, the method comprising the steps of:

• applying a signed digit algorithm to the processed exponent value to generate a processed exponent value;
• constructing a look-up table of substrings that are likely to be encountered in the processed exponent value each entry in the look-up table being a respective intermediate value corresponding to the data string raised to the power represented by the respective substring;
• applying a string replacement method to traverse the processed exponent value and to record pointers to the values in the look-up table that correspond to the matching substrings in the processed exponent value and replacing the matching substrings in the processed exponent value by zeros to produce a modified exponent value;
• and
• applying a multiply-square chain algorithm to the modified exponent value to calculate the value representing the data string raised to the exponent value.

A method for encrypting a data string by calculating an encrypted value representing the data string raised to a power represented by a exponent value, the method comprising the steps of:

• applying a signed digit algorithm to the exponent value to generate a processed exponent value;
• constructing a look-up table of substrings that are likely to be encountered in the processed exponent value each entry in the look-up table corresponding to the data string raised to the power represented by the respective substring;
• applying a string replacement method to traverse the processed exponent value and retrieving, from the lookup table, and recording, intermediate values corresponding to matching substrings in the processed exponent value and replacing the matching substrings in the processed exponent value by zeros and a reference to the look-up table to produce a modified recoded string representation of the exponent value;
• and
• applying a multiply-square chain algorithm to the recoded exponent value using the look-up table to calculate the encrypted value representing the data string.

Apparatus for encrypting a data string by calculating an encrypted value representing the data string raised to a power represented by a binary exponent value, the apparatus comprising:

• means for applying a signed digit algorithm to the binary exponent value to generate a processed exponent value;
• a look-up table of substrings that are likely to be encountered in the processed exponent value each entry in the look-up corresponding to the data string raised to the power represented by the respective substring;
• means for applying a string replacement method to traverse the processed exponent value and to record pointers to the values in the look-up table that correspond to the matching substrings in the processed exponent value and to replace the matching substrings in the processed exponent value by zeros to produce a modified exponent value;
• and
• means for applying a multiply-square chain algorithm to the modified exponent value to calculate the encrypted value representing the data string.

A computer readable carrier including computer program instructions, the instructions causing a computer to perform a method of encrypting a data string by calculating a value representing a data string raised to a power represented by a binary exponent value, the method comprising the steps of:

• applying a signed digit algorithm to the binary exponent value to generate a processed exponent value;
• constructing a look-up table of substrings that are likely to be encountered in the processed exponent value each entry in the look-up table being a respective intermediate value corresponding to the data string raised to the power represented by the respective substring;
• applying a string replacement method to traverse the processed exponent value and to record pointers to the values in the look-up table that correspond to the matching substrings in the processed exponent value and replacing the matching substrings in the processed exponent value by zeros to produce a modified exponent value;
• and
• applying a multiply-square chain algorithm to the modified exponent value to calculate the encrypted value representing the data string.