Help with modulus computation problem

[boev]

Your Contact: [email protected] Your environment (OS/HW): not a technical question/problem Detailed Description:

Hello,

I have a computational problem involving the plaintext modulus p^r. I am doing computations in lets say 2^20 (p = 2, lift = 20). Suppose we are multiplying n such numbers. Now if one of those numbers is 0, then the whole product is 0 and that is good. But if 20 out of the n numbers are even or worse - contain multiple factors of 2, then quickly the plaintext modulus becomes divisor of the product and when decrypted, the product is 0. Basically, my question is, if there is a smart way (not introducing much noise or computation cost) to mitigate the problem. I only want to keep the product from becoming 0, any value other than that would be okay.

Thanks for reading, any ideas are welcomed! Yordan

[boev]

PS: I thought about extracting the LSB via extractDigit and then adding 1-LSB to the number, in order to make it odd. I am searching for something more elegant, or a more efficient way to do the LSB trick.

[shaih]

One option would be to work modulo a prime number close to 2^20. Alternatively use multiple instances, each one is modulo a different small prime number, such that the product of all these small primes is close to 2^20. Then you can re-assemble the result after decryption using Chinese-Rmeaindering