/sci/ - Science & Math

>>11899926
> he fell for the engineering meme
The only useful degree from a non-ivy in 2020 is CS.

I'm trying to find cube roots of very large numbers (millions of binary digits), modulo pseudo-mersenne prime in python.

Native python number type is completely useless. pygmp2 is better but still slow. Apparently GMP can't exploit mersenne/solinas prime modulus for fast reductions and sticks with montgomery/berret (which is several magnitudes slower) for relatively sane-sized numbers. For larger moduli (>2^10000 or so) it attempts FFT Schonhage-Strassen, which doesn't work very well either (that one is best suited only for general m).

Does anon know of any library which can do fast modpow() reduction when m is of special fast-reduction-friendly form - for example 2**414032-5 (to get idea of scale, this number is roughly 100k decimal digits and occupies 50kb in memory).