While working on integer factorization algorithm I came to the next problem:

$$\frac{a}{ex} = \lfloor{\frac{a}{ex}\rfloor} + c$$

  • $a$ the number I want to factor
  • $x$ factor of $a$
  • $e$ positive integer that I choose

For $e = 1$ I found a linear representation for short sequences of $\lfloor{\frac{a}{x}\rfloor}$, this allows me to compare it to $\frac{a}{x}$ and find the value of $x$. The problem is that there are to many sequences, for this to be efficient. So I decrease their amount by using $e > 1$. Unfortunately it created $c$, and now I have to test all its possible values, it looks some thing like this:

  • for $e=2$, $c$ can be $\frac{1}{2}$
  • for $e=3$, $c$ can be $\frac{1}{3}$ or $\frac{2}{3}$
  • for $e=4$, $c$ can be $\frac{1}{4}$ or $\frac{2}{4}$ or $\frac{3}{4}$

Is there any way that I can predict the values of $c$, or give it a better estimation?


The value of $c$ is given by the formula $$ c = \frac{(a/x) \pmod{e}}{e}. $$

| cite | improve this answer | |
  • $\begingroup$ I doubt this answer is helpful. If it isn't, could you explain what you're actually after? $\endgroup$ – Yuval Filmus Jan 28 '15 at 19:48
  • $\begingroup$ $c$ is the bottle neck of my algorithm, I want to reduce the values it may have. When factoring large numbers like 1024 bit, $e$ have to be some where at 500+ bits, it makes it very unclear to what $c$ might be. $\endgroup$ – Ilya Gazman Jan 28 '15 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.