ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 04 Nov 2016 20:37:05 -0500Speeding up power_modhttp://ask.sagemath.org/question/35296/speeding-up-power_mod/ Recently I've been working a bit with modular arithmetic and big numbers. An incredibly useful tool for that is modular exponentiation by repeated squaring, implemented using power_mod function. Earlier I was using Julia for that (together with BigInt there), and I was quite disappointed to find out that in Sage modular exponentiation is noticably slower for (very) large moduli - slowdown by a factor of 3 modulo 10^5000 and by a factor of almost 10 modulo 10^50000 (I didn't test larger ones). I don't know if the reason for this is that Julia uses some faster modular exponentiation algorithm (I didn't manage to find how it is implemented), or whether it is because the BigInt makes it that significantly easier for CPU to work with these.
So my question is, is there some way to speed up the modular exponentiation in Sage?Fri, 28 Oct 2016 15:00:30 -0500http://ask.sagemath.org/question/35296/speeding-up-power_mod/Comment by Mafra for <p>Recently I've been working a bit with modular arithmetic and big numbers. An incredibly useful tool for that is modular exponentiation by repeated squaring, implemented using power_mod function. Earlier I was using Julia for that (together with BigInt there), and I was quite disappointed to find out that in Sage modular exponentiation is noticably slower for (very) large moduli - slowdown by a factor of 3 modulo 10^5000 and by a factor of almost 10 modulo 10^50000 (I didn't test larger ones). I don't know if the reason for this is that Julia uses some faster modular exponentiation algorithm (I didn't manage to find how it is implemented), or whether it is because the BigInt makes it that significantly easier for CPU to work with these.</p>
<p>So my question is, is there some way to speed up the modular exponentiation in Sage?</p>
http://ask.sagemath.org/question/35296/speeding-up-power_mod/?comment=35303#post-id-35303@Wojowu I found [out](http://doc.sagemath.org/html/en/constructions/number_theory.html#taking-modular-powers) that you can use the gmp implementation within Sage. Did you try it? It should give us roughly the same performance as Julia.Sun, 30 Oct 2016 08:27:50 -0500http://ask.sagemath.org/question/35296/speeding-up-power_mod/?comment=35303#post-id-35303Comment by Mafra for <p>Recently I've been working a bit with modular arithmetic and big numbers. An incredibly useful tool for that is modular exponentiation by repeated squaring, implemented using power_mod function. Earlier I was using Julia for that (together with BigInt there), and I was quite disappointed to find out that in Sage modular exponentiation is noticably slower for (very) large moduli - slowdown by a factor of 3 modulo 10^5000 and by a factor of almost 10 modulo 10^50000 (I didn't test larger ones). I don't know if the reason for this is that Julia uses some faster modular exponentiation algorithm (I didn't manage to find how it is implemented), or whether it is because the BigInt makes it that significantly easier for CPU to work with these.</p>
<p>So my question is, is there some way to speed up the modular exponentiation in Sage?</p>
http://ask.sagemath.org/question/35296/speeding-up-power_mod/?comment=35442#post-id-35442@Wojowu Despite the different environments, ~45s to ~18s is a huge difference. I tested `99999^450.powermod(9999^5000,10^6000)` on my machine and on SMC and both were around 4.7s. Out of curiosity, what is the precise computation that you tested?Fri, 04 Nov 2016 20:37:05 -0500http://ask.sagemath.org/question/35296/speeding-up-power_mod/?comment=35442#post-id-35442Comment by Mafra for <p>Recently I've been working a bit with modular arithmetic and big numbers. An incredibly useful tool for that is modular exponentiation by repeated squaring, implemented using power_mod function. Earlier I was using Julia for that (together with BigInt there), and I was quite disappointed to find out that in Sage modular exponentiation is noticably slower for (very) large moduli - slowdown by a factor of 3 modulo 10^5000 and by a factor of almost 10 modulo 10^50000 (I didn't test larger ones). I don't know if the reason for this is that Julia uses some faster modular exponentiation algorithm (I didn't manage to find how it is implemented), or whether it is because the BigInt makes it that significantly easier for CPU to work with these.</p>
<p>So my question is, is there some way to speed up the modular exponentiation in Sage?</p>
http://ask.sagemath.org/question/35296/speeding-up-power_mod/?comment=35441#post-id-35441@Wojowu I'd expect GMP's .powermod to have a similar performance as Julia since Julia uses GMP too. But you cannot really compare the methods unless you compare them running in the *same* computer under the same load. So using JuliaBox and SageMathCloud makes all the difference to the point that you cannot really make any definitive statement of Julia vs Sage.Fri, 04 Nov 2016 19:26:29 -0500http://ask.sagemath.org/question/35296/speeding-up-power_mod/?comment=35441#post-id-35441Comment by Wojowu for <p>Recently I've been working a bit with modular arithmetic and big numbers. An incredibly useful tool for that is modular exponentiation by repeated squaring, implemented using power_mod function. Earlier I was using Julia for that (together with BigInt there), and I was quite disappointed to find out that in Sage modular exponentiation is noticably slower for (very) large moduli - slowdown by a factor of 3 modulo 10^5000 and by a factor of almost 10 modulo 10^50000 (I didn't test larger ones). I don't know if the reason for this is that Julia uses some faster modular exponentiation algorithm (I didn't manage to find how it is implemented), or whether it is because the BigInt makes it that significantly easier for CPU to work with these.</p>
<p>So my question is, is there some way to speed up the modular exponentiation in Sage?</p>
http://ask.sagemath.org/question/35296/speeding-up-power_mod/?comment=35422#post-id-35422@Mafra Thank you for your replies! I have tested and compared a few methods of computing modular powers. Apart from SageMath's power_mod, I have tried Python's pow, GMP's .powermod and SageMath's modular integer rings. The latter three have noticably outperformed power_mod, but all of them gave improvements of order of 30%, as opposed to 70% provided by Julia (tested using JuliaBox if that makes any difference) (to be precise: 63 seconds for power_mod, ~45s for other three, and 18.5s for Julia). By the way, do you think it makes any difference that I am using SageMathCloud as opposed to having it downloaded? I can't test right now because I don't have Sage on the machine I'm using now.Fri, 04 Nov 2016 09:12:14 -0500http://ask.sagemath.org/question/35296/speeding-up-power_mod/?comment=35422#post-id-35422Comment by Mafra for <p>Recently I've been working a bit with modular arithmetic and big numbers. An incredibly useful tool for that is modular exponentiation by repeated squaring, implemented using power_mod function. Earlier I was using Julia for that (together with BigInt there), and I was quite disappointed to find out that in Sage modular exponentiation is noticably slower for (very) large moduli - slowdown by a factor of 3 modulo 10^5000 and by a factor of almost 10 modulo 10^50000 (I didn't test larger ones). I don't know if the reason for this is that Julia uses some faster modular exponentiation algorithm (I didn't manage to find how it is implemented), or whether it is because the BigInt makes it that significantly easier for CPU to work with these.</p>
<p>So my question is, is there some way to speed up the modular exponentiation in Sage?</p>
http://ask.sagemath.org/question/35296/speeding-up-power_mod/?comment=35302#post-id-35302Julia uses the gmp library (see line 440 of [https://github.com/JuliaLang/julia/blob/master/base/gmp.jl]), whereas Sage uses a hand-made power_mod() function in python (see [https://github.com/sagemath/sage/blob/master/src/sage/arith/misc.py]). So one way to speed up Sage's power_mod() function is to implement it in pynac. Have you compared to Python's built-in pow(a,b,c) function, where c is the modulus? see here [https://docs.python.org/3/library/functions.html#pow]Sun, 30 Oct 2016 07:50:20 -0500http://ask.sagemath.org/question/35296/speeding-up-power_mod/?comment=35302#post-id-35302