0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ I doubt this answer is helpful. If it isn't, could you explain what you're actually after? $\endgroup$
    – Yuval Filmus
    Commented Jan 28, 2015 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
    Commented Jan 28, 2015 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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