The mulmod operation could be accelerated by gmpy2.mpz

[tanjuntao]

The mulmod(x, y, z) = x * y % z operation in paillier.py could be accelerated by gmpy2.mpz when all the three parameters are very large. Below is the test results on my CentOS-7.4 with a 8-core Intel CPU.

Code

from phe import generate_paillier_keypair
import gmpy2
from secrets import randbelow
import time

pub_key, priv_key = generate_paillier_keypair(n_length=1024)
n_squared = pub_key.n ** 2
n_suqared_mpz = gmpy2.mpz(n_squared)
SIZE = 100_0000
x_list = [randbelow(n_squared) for _ in range(SIZE)]
y_list = [randbelow(n_squared) for _ in range(SIZE)]
print('generation done.')

# Raw Python mulmod
start = time.time()
for x, y in zip(x_list, y_list):
    res = x * y % n_squared
print('Python buildin mulmod time: {}'.format(time.time() - start))

# gmpy2 mulmod
start = time.time() 
for x, y in zip(x_list, y_list):
    x = gmpy2.mpz(x)
    y = gmpy2.mpz(y)
    res = int(gmpy2.mod(gmpy2.mul(x, y), n_suqared_mpz))
print('gmpy2 mulmod time: {}'.format(time.time() - start))

Results

[dev@zhaohang ~]$ python3 mulmod_test.py 
generation done.
Python buildin mulmod time: 14.533275842666626
gmpy2 mulmod time: 4.743465423583984

I also increased the key size from 1024 bits to 2048 bits, here is the result.

[dev@zhaohang ~]$ python3 mulmod_test.py 
generation done.
Python buildin mulmod time: 48.953245639801025
gmpy2 mulmod time: 10.765974283218384

As you can see, using gmpy2.mpz() to wrap the big Python integers can accelerate the mulmod operation. I'm willing to submit a pull request if you like.

[hardbyte]

A pull request would be most welcome for this

[tanjuntao]

I've implemented a gmpy2's version of mulmod, you can refer it at #99.