AN OPTIMIZATION ALGORITHM OF RSA KEY GENERATION IN EMBEDDED SYSTEM
Dongjiang Li, Yandan Wang · 2012
To reduce the time complexity, this paper proposes an optimization algorithm to generate the large prime number. Before the primality test, an improved prescreening algorithm is used to get rid of most of odd composite numbers. Then we introduce the Fermat’s little theorem to make a further judgement, which can decrease the times of using prescreening algorithm. At last, Miller-Rabin algorithm is used to make a final primality test. The results show that the speed of key generation has been greatly improved.