A device for generating code which implements modular exponentiation, the device comprising: a first part configured to generate a randomized addition chain of addition chain elements a i, a second part comprising: a memory used to store a lookup table; and a processor in communication with the memory, the processor configured to: receive information for the generated randomized addition chain; output code for implementing the modular exponentiation based upon the generated randomized chain, which loads elements from the lookup table including intermediate results which utilize the information for a generated randomized addition chain; and output code for implementing the modular exponentiation which uses the loaded elements to compute the next element, wherein the randomized addition chain is generated by: initializing the first addition chain element a 0 = 1 and the counter i = 1, setting a boolean value m to zero to mark that there is no overflow, picking a uniform random positive integer r 1 from the range [0, b 1 - 1]; where exponent d and the integer parameters (p 1, b 1, b 2) are input, such that p 1 ≤ b 1 and b 2 is larger than an expected length of the addition chain, and may be used to construct the random addition chain, assigning m = 1, if r 1 ≤ p 1 and 2 · a i-1 > d, assigning a i = a i-1 + a i-1 if r 1 ≤ p 1 and 2 · a i-1 ≤ d, and assigning a i = a i-1 + a j, where j is randomly chosen with 0 ≦ j < i such that a i-1 + a j ≤ d, if r 1 > p 1 or m = 1. a first part configured to generate a randomized addition chain of addition chain elements a i, a second part comprising: a memory used to store a lookup table; and a processor in communication with the memory, the processor configured to: receive information for the generated randomized addition chain; output code for implementing the modular exponentiation based upon the generated randomized chain, which loads elements from the lookup table including intermediate results which utilize the information for a generated randomized addition chain; and output code for implementing the modular exponentiation which uses the loaded elements to compute the next element, wherein the randomized addition chain is generated by: initializing the first addition chain element a 0 = 1 and the counter i = 1, setting a boolean value m to zero to mark that there is no overflow, picking a uniform random positive integer r 1 from the range [0, b 1 - 1]; where exponent d and the integer parameters (p 1, b 1, b 2) are input, such that p 1 ≤ b 1 and b 2 is larger than an expected length of the addition chain, and may be used to construct the random addition chain, assigning m = 1, if r 1 ≤ p 1 and 2 · a i-1 > d, assigning a i = a i-1 + a i-1 if r 1 ≤ p 1 and 2 · a i-1 ≤ d, and assigning a i = a i-1 + a j, where j is randomly chosen with 0 ≦ j < i such that a i-1 + a j ≤ d, if r 1 > p 1 or m = 1. a memory used to store a lookup table; and a processor in communication with the memory, the processor configured to: receive information for the generated randomized addition chain; output code for implementing the modular exponentiation based upon the generated randomized chain, which loads elements from the lookup table including intermediate results which utilize the information for a generated randomized addition chain; and output code for implementing the modular exponentiation which uses the loaded elements to compute the next element, receive information for the generated randomized addition chain; output code for implementing the modular exponentiation based upon the generated randomized chain, which loads elements from the lookup table including intermediate results which utilize the information for a generated randomized addition chain; and output code for implementing the modular exponentiation which uses the loaded elements to compute the next element, wherein the randomized addition chain is generated by: initializing the first addition chain element a 0 = 1 and the counter i = 1, setting a boolean value m to zero to mark that there is no overflow, picking a uniform random positive integer r 1 from the range [0, b 1 - 1]; initializing the first addition chain element a 0 = 1 and the counter i = 1, setting a boolean value m to zero to mark that there is no overflow, picking a uniform random positive integer r 1 from the range [0, b 1 - 1]; where exponent d and the integer parameters (p 1, b 1, b 2) are input, such that p 1 ≤ b 1 and b 2 is larger than an expected length of the addition chain, and may be used to construct the random addition chain, assigning m = 1, if r 1 ≤ p 1 and 2 · a i-1 > d, assigning a i = a i-1 + a i-1 if r 1 ≤ p 1 and 2 · a i-1 ≤ d, and assigning a i = a i-1 + a j, where j is randomly chosen with 0 ≦ j < i such that a i-1 + a j ≤ d, if r 1 > p 1 or m = 1.