Friday, April 28, 2017

[ygkliadl] High precision real and modular cube roots

Computing to high precision a cube root in the field of real numbers is kind of difficult: we need special algorithms like Newton's method and out-of-core FFT-based multiple precision arithmetic.

Computing a cube root in certain fields of modular arithmetic is extremely difficult; this is the basis of the security of RSA.

Are these two difficulties related?  (Probably not.)  It would be interesting if, say, a trillion bits of real precision could be interchanged with a 100 bits of modular precision.

No comments :