Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

The mulmod operation could be accelerated by gmpy2.mpz #98

Closed
tanjuntao opened this issue Apr 8, 2022 · 2 comments
Closed

The mulmod operation could be accelerated by gmpy2.mpz #98

tanjuntao opened this issue Apr 8, 2022 · 2 comments

Comments

@tanjuntao
Copy link
Contributor

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
Copy link
Collaborator

A pull request would be most welcome for this

tanjuntao added a commit to tanjuntao/python-paillier that referenced this issue Apr 14, 2022
According to data61#98, the mulmod operation(mulmod(a, b, c) = a * b % c)
could be accelerated by using gmpy2.mpz when a, b, and c
are very large numbers.

The main changes are:
* add a mulmod funciton in util.py
* use util.mulmod function to wrap the mulmod operation in paillier.py
@tanjuntao
Copy link
Contributor Author

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

hardbyte added a commit that referenced this issue Apr 19, 2022
* Using gmpy2's mulmod to accelerate the mulmod operation

According to #98, the mulmod operation(mulmod(a, b, c) = a * b % c)
could be accelerated by using gmpy2.mpz when a, b, and c
are very large numbers.

The main changes are:
* add a mulmod funciton in util.py
* use util.mulmod function to wrap the mulmod operation in paillier.py

Co-authored-by: Brian Thorne <brian@hardbyte.nz>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants