The best known factorization algorithms have a cost which depends on the modulus size, not on the size of the individual factors, so using more smaller factors should have no impact. On the negative side, using too small factors may weaken the modulus. More generally, with $k$ factors, the expected CRT speedup is in about $k^2$. For instance, if you have a 1536-bit modulus which is the product of three 512-bit primes, then the CRT replaces one 1536-bit exponentiation with three 512-bit exponentiations which are, individually, 27 times faster (assuming a classic cubic modular exponentiation algorithm), for a total speedup of 9, compared to the usual 4 with two factors. The Chinese Remainder Theorem still applies (see for instance in section 5.1.2, the description accommodates more than two primes). On the plus side, this may offer some performance improvement. Having more than two prime factors is supported by the PKCS#1 standard.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |