1

I am trying to calculate something like this: a^b mod c, where all three numbers are large.

Things I've tried:

  1. Python's pow() function is taking hours and has yet to produce a result. (if someone could tell me how it's implemented that would be very helpful!)

  2. A right-to-left binary method that I implemented, with O(log e) time, would take about 30~40 hours (don't wanna wait that long).

  3. Various recursion methods are producing segmentation faults (after I changed the recursion limits)

Any optimizations I could make?

adbforlife
  • 21
  • 7
  • see [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214) With such big numbers I would try NTT based Schönhage-Strassen multiplication instead of karatsuba ... also power by squaring usualy involves sqr for which is NTT based sqr even faster – Spektre Feb 12 '18 at 15:30

2 Answers2

2

It sounds like you are trying to evaluate pow(a, b) % c. You should be using the 3-argument form, pow(a, b, c), which takes advantage of the fact that a * b mod c == a mod c * b mod c, which means you can reduce subproducts as they are computed while computing a ^ b, rather than having to do all the multiplications first.

chepner
  • 497,756
  • 71
  • 530
  • 681
1

Python uses Karatsuba multiplication so the running time of multiplication is O(n^1.585). But division is still O(n^2).

For exponentiation, Python uses a left-to-right method with a 5-bit window. (It consumes 5 bits at once instead of just 1 bit. It does use more memory but will generally be faster.)

To get faster computations, you may want to look at gmpy2. It wraps the GMP multiple-precision library and will be faster. I ran a quick test and I think it will be ~100x faster.

Disclaimer: I maintain gmpy2.

casevh
  • 11,093
  • 1
  • 24
  • 35
  • I actually used gmpy2 at first. I used gmpy2.powmod(mpz(a), mpz(b), mpz(c)). My computer freezes when it's used for some reason. Is there anything I could do to optimize that? – adbforlife Feb 12 '18 at 02:59
  • Not really. There is no checking for interrupts so the calculation can't be interrupted. BTW, gmpy2.powmod(a,b,c) is sufficient; the arguments are automatically converted to mpz. Is there anything special about any of the values? – casevh Feb 12 '18 at 03:04
  • As far as I know, they are just large numbers (~120000 digits). Specifically, I'm trying to implement a fast decryption of RSA. (a, b, c) here are the ciphertext, the private key, and the modulo, respectively. – adbforlife Feb 12 '18 at 03:09
  • 1
    @abforlife When RSA is used to encrypt in practice, a message of any length is encrypted with a symmetric algorithm (like AES) using a random key. Then that key (only 256 bits long or so) is encrypted with RSA. – Matt Timmermans Feb 12 '18 at 03:19
  • Picking a some numbers at random, the running time on my machine should be around 30 minutes. But what @MattTimmermans said... – casevh Feb 12 '18 at 03:22
  • @casevh This RSA (not used in practice) is designed to be weird I think. I think the desirable time should be around 30 minutes or less but not sure where I'm messing up though. (I'm using a Macbook Pro) – adbforlife Feb 12 '18 at 03:40
  • I'm using on a Skylake CPU @3.7 GHz and I think 30 minutes is possible on that class of CPU. Not sure about a Macbook Pro. – casevh Feb 12 '18 at 03:50