Improve big prime numbers generation

[MarcosNicolau]

Library Benchmark Name Iterations Total Execution Time Average Execution Time
primitive-types biguint_add random 1024 bits 1000000 1.958858 seconds 0.000002 seconds
primitive-types biguint_sub random 1024 bits 1000000 1.955710 seconds 0.000002 seconds
primitive-types biguint_divmod random 1024 bits 1000000 2.547367 seconds 0.000003 seconds
primitive-types biguint_mul random 1024 bits 1000000 9.112737 seconds 0.000009 seconds
primitive-types biguint_pow random 1024 bits 1000 11.822133 seconds 0.011822 seconds
primitive-types biguint_pow_mod random 1024 bits 10 11.150793 seconds 1.115079 seconds
math random_prime 256 bits 1 0.651118 seconds 0.651118 seconds
math random_prime 512 bits 1 4.157772 seconds 4.157772 seconds
math random_prime 1024 bits 1 206.357274 seconds 206.357274 seconds
math is_prime_solovay_strassen 512 bits prime 1 3.817324 seconds 3.817324 seconds
math is_prime_solovay_strassen 1024 bits prime 1 28.215262 seconds 28.215262 seconds
math jacobi 512 bits prime 1 0.042327 seconds 0.042327 seconds
math jacobi 1024 bits prime 1 0.319375 seconds 0.319375 seconds
digital-signature rsa_key_generation 256 bits 1 0.305139 seconds 0.305139 seconds
digital-signature rsa_key_generation 512 bits 1 3.105362 seconds 3.105362 seconds
digital-signature rsa_key_generation 1024 bits 1 17.503724 seconds 17.503724 seconds

As you can see pow and pow_mod are a bit slow... in fact they are what is making the is_prime_solovay_strassen take so long and as a consequence the random_prime and the rsa_key_generation are slow as well. jacobi gets done pretty fast. Right now, rsa_keys of 2048 bits and 4096 bits take too much time to add it to the CI benmarks. On my machine they threw around 60 seconds for 2048 bits and 3 min for 4096.

My intuition is that parallelizing the generation with a few threads + applying a faster multiplication algorithm such as montogomery reduction should make this pretty quick.

Originally posted by @MarcosNicolau in #34 (comment)