All Questions

This is related to cryptography and this question and another question. In short, we are asking about decomposing multivariate polynomial as sum of perfect powers of linear polynomials. Working over $\...

Fix an integer $n>2$. Question. What is the probability that, for a given $h\in\Bbb Z_n,$ there is no $$x\in[0,\varphi(n)-1]\cap\Bbb Z$$ such that $h^{x\bmod\varphi(n)}\equiv x\bmod n$?

The reason I ask this question is that cyclotomic polynomial is critical to the construction of lattice-based cryptography. In most of the existing lattice-based cryptographic schemes, $n$ is usually ...

Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$. $P$ has a binary expansion and so does $Q$. We can set the binary $0/1$ variables to be $x_1$ through $x_{\lceil\log P\rceil}$ and $...

It is shown that Coppersmith method yields optimal integer root extraction for univariate polynomials in https://arxiv.org/abs/1605.08065 and a follow up work attempts this for bivariate polynomials ...

Can we count the no. of $x$ where $ p^{\alpha -1} < x < p^{\alpha}$ , $gcd(x, 2p)=1$ and if $d |x$ and $d < p ^{\beta}$ for some $1< \beta<\alpha-1$ then $ \frac {x} {d} > p^{\alpha -...