When $f(x)$ divides $d$ $f(x)=d(c+2ax+dx^2)\mod{N}$

49 Views Asked by At

Given $f(0)$ divides $d$ and $f(1)$ not, how to find other $x$ values that make $f(x)$ divisible by $d$?

$$f(x)=d(c+2ax+dx^2)\mod{N}$$

$a,c,d,x,N$ are positive integers

  • $c$ is a small number
  • $d$ is a big number
  • $c< a < d < N$
  • $gcd(d,n) = 1$
  • $N$ is a number that is hard to factor

The questio is how to find when $f(x)|d$?

Also note the trivial solution: When $dc < N$ than $f(kn)$ solves since $dc +2akN + d(kN)^2=dc (\mod N)$ and since $f(0)$ solves this condition is always true

Edit:

Found a group of solution when $c+2ax+dx^2\mod{N}<\lfloor\frac{N}{d}\rfloor$ but there is no easy way to find those, so the question remains open