# Binary representation of the inverse of a big number [closed]

In one of the first FHE schemes by Gentry, the KeyGen algorithm is defined as follow:

For a security parameter $$\lambda$$, set $$N = \lambda ^ 2, P = \lambda ^ 2, Q = \lambda ^ 5$$.

KeyGen$$(\lambda)$$: Generate a random $$P$$-bit odd integer, $$p$$. A set $$\vec{y} = \{ y_1, y_2, \ldots, y_\beta\}$$ is generated with $$y_i$$ bits. There must exist a sparse subset $$S \subset \vec{y}$$ of $$\alpha$$ elements such that $$\sum\limits_{y_j \in S} (y_j) = \frac{1}{p} \mod 2$$.

Set $$sk$$ to be a binary encoding of the subset $$S$$, where $$s = (0,1)^\beta$$. Set $$pk \leftarrow (p, \vec{y})$$.

My problem here is with the subset S. Especially, for a large enough security parameter, the random integer $$p$$ is so large that I don't see how to print its inverse on my terminal. Are there some specific libraries in Python or C to handle this kind of inverse? I have tried to shift it by the size of p in base 10 but the problem remains as I can't convert p to float/double before dividing.

This may not be the most accurate forum for this question, and I apologize in advance if it is not.

The first $$k$$ digits on the right of the decimal point of the representation of $$1/p$$ in base $$b$$ also are the representation in base $$b$$ of $$\left\lfloor b^k/p\right\rfloor$$ left-padded to $$k$$ digits with zeroes.

If we want to perform computations to $$k$$ places after the decimal point for quantity $$x\in\Bbb R$$, we can use the integer quantity $$\left\lfloor b^k\,x\right\rfloor$$, or better $$\left\lfloor b^k\,x+\frac12\right\rfloor$$.

Any language (e.g. python) or library (e.g. GMP) capable of handling arbitrary precision integers let you make the necessary computations.

E.g. in python 3,

p = 3**161
print("{0:b}".format(2**700//p))


yields a 445-bit bitstring which, padded with 255 0 on the left, and then 0. on the left, is $$1/p$$ in binary to 700 binary places.

• hmmm your example actually works but for my case with larger p (especially the example above of 16k bits) I simply get 0... And this size in bits can be potentially bigger than 16k (I tried both on my IDE and in a terminal with different versions of python 3) – Binou Nov 9 '18 at 8:34
• Oh sorry I think I understood my mystake, I was keeping 2**700 for my bigger p but of course I need to update it... Thanks for your help! – Binou Nov 9 '18 at 8:42