9
$\begingroup$

Given the prime factorization of $N$, is there a known method for computing the prime factorization of $N-1$ or $N+1$, which is more efficient than the best known method for doing that without it?

I assume that the factors of $N$ can be "skipped" while searching for the factors of $N-1$ or $N+1$, but I don't see how it can improve the general case performance (i.e., for any given value of $N$).

UPDATE:

This question can also be stated as follows: is there a known method for computing the prime factorization of $N$, given the prime factorization of either one of its neighbors (which is more efficient than the best known method for doing that without it)?

$\endgroup$
  • 4
    $\begingroup$ None is known, and the existence of such a method would spoil the widely-used RSA encryption method. $\endgroup$ – MJD Apr 16 '14 at 21:23
  • $\begingroup$ You can indeed skip the factors of $N$. I guess you might be able to use the factors of $N$ in some complicated prime-factorization algorithm, but I'm not sure. $\endgroup$ – Ragnar Apr 16 '14 at 21:24
  • $\begingroup$ The link between the additive $(\pm 1)$ and multiplicative (prime factorisation) properties of the integers is also one way of looking at the Riemann Hypothesis. $\endgroup$ – Mark Bennet Apr 16 '14 at 21:26
  • 3
    $\begingroup$ @Mark Bennet: This sounds very interesting. Can you please elaborate? $\endgroup$ – barak manos Apr 16 '14 at 21:27
  • 3
    $\begingroup$ Btw, if there was a polytime way to factor a number given the factorization of a neighbor, then it would be trivial to factor in polytime, because you could just recursively factor $\frac {N \pm 1}{2^k}$ for whichever largest $k$ yields an integer. $\endgroup$ – DanielV Apr 16 '14 at 22:14
9
$\begingroup$

I am following up on the comment of DanielV, which you did not understand. DanielV said:

If there was a polytime way to factor a number given the factorization of a neighbor, then it would be trivial to factor in polytime, because you could just recursively factor $\frac{N±1}{2^k}$ for whichever largest $k$ yields an integer.

We hypothesize that there is an algorithm $M$ which takes the factorization of $n\pm 1$ and efficiently returns the factorization of $n$. Let's see how the existence of $M$ allows us to quickly factor 1005973.

Both 1005973+1 and 1005973-1 are even, and one of them must be a multiple of 4. We can quickly determine that 1005972=4·251493. So we would like to factor 251493; if we could factor 251493, we would append $2^2$ to the factorization, give the result to $M$, and then $M$ would return the factorization of 1005973 that we wanted.

But 251493 is much smaller than 1005973, and using the same method, we can reduce the problem of factoring 251493 to that of factoring an even smaller number. Using the same method, we determine that:$$\begin{array}{rl} 251492 &= 4\cdot62873\\ 62872 & = 8\cdot7859 \\ 7860 &= 4·1965 \\ 1964 &= 4\cdot491 \\ 492 &= 4·123 \\ 124 &= 4·31 \end{array}$$

We could continue, but I will assume that the prime factorization of 31 is known, so as not to belabor the point.

Now we have a prime factorization for 124, so by hypothesis we can give this to $M$, which will quickly tell us the prime factorization of 123. From this it is trivial to construct the prime factorization of 4·123, because it is the same but with an extra $2^2$. We give this to $M$ to obtain the prime factorization of 491, which is almost the same as the prime factorization of 4·491 = 1964, which we can give to $M$ to obtain the prime factorization of 1965. We proceed in that way up the table until $M$ gives us the prime factorization of 251493; appending $2^2$ to this factorization, we obtain the factorization of 1005972=4·251493, which, given to $M$, produces the factorization of our original number 1005973.

Each step involves a small amount of work (a few divisions by 2 plus a bit of bookkeeping) plus a call to $M$; the number of steps is evidently bounded above by $\log_4 N$. So the running time of the entire algorithm is $O(\log_4(N) \cdot m(N))$ where $m$ is the running time of $M$. If $m(N)$ is polynomial in $N$, so is the entire algorithm.

If $M$ is more limited, say it can only produce the factorization of $N+1$, not $N-1$, given a factorization of $N$, the number of steps at most doubles, to $\log_2 N$.

$\endgroup$
  • $\begingroup$ Nice!!!!!!!!!!! $\endgroup$ – barak manos Apr 17 '14 at 18:01
  • 1
    $\begingroup$ You could have "belabored the point" in the (very nice) example with one more line: $32=32$. $\endgroup$ – Barry Cipra Apr 18 '14 at 13:11
  • $\begingroup$ I did think about that. $\endgroup$ – MJD Apr 18 '14 at 13:26
2
$\begingroup$

Look at the next method. It might help

https://math.stackexchange.com/questions/497370/new-method-derived-out-of-fermats-factorization-method

Case for N=493

  492=4*123
  123=11*12-3*3 then 493=(11+12+3+3)(11+12-3-3)=29*17

or by known factors of 123 (this is not general):

 123=3*41=3(44-3) which must be again of the form x(x+1)-y*y 
 Let us try:
 123=3(11*4-3)
 123=11*12-3*3 and we can again find factors of 493

Numbers that behave best, that directly gives us one part factorization, are from so called main branch of the odd Collatz tree: 1,5,21,85,341,...

5=1(6-1)=2*3-1*1 and 21=(2+3-1-1)(2+3+1+1)
21=3(10-3)=5*6-3*3 and 85=(5+6-3-3)(5+6+3+3) 
85=5(22-5)=10*11-5*5 and 341=(10+11-5-5)(10+11+5+5)
341=11(42-11)=21*22-11*11
1365=21(86-21)=42*43-21*21

Ratio of found factors for these numbers is 1 to 3 +-2

$\endgroup$
  • $\begingroup$ But how can you find $x,y$ such that $x(x+1)-y^2=123$ (or any other number for that matter)? $\endgroup$ – barak manos Apr 19 '14 at 8:40
  • 1
    $\begingroup$ BTW, the use of the $3n+1$ conjecture here is interesting... $\endgroup$ – barak manos Apr 19 '14 at 8:41
  • $\begingroup$ Generally and "sadly" the same way as with Fermat factorization method. Although I have found some exceptions as it is with the main branch of odd Collatz. Maybe there are some more complicated patterns in other branches. $\endgroup$ – Bojan Vasiljević Apr 20 '14 at 17:11
0
$\begingroup$

I found a possible relation, but i don't know if it's efficiently. Here a proff:

We know that:

$n!=\prod_{P_{i} \leq n}p_{i}^{ \alpha_{i}(n)}$; where:

$\alpha_{i}(n)=\sum_{t=1}^{r}[\frac{n}{p_{i}^{t}}]$ and $p^{r} \leq n < p^{r+1}$.

Then:

$n=\frac {n!}{(n-1)!}=\prod_{P_{i} \leq n}p_{i}^{ \beta_{i}(n)}$ (Eq. 1)

Where:

$\beta_{i}(n)= \alpha_{i}(n)-\alpha_{i}(n-1)$

In other words:

$n+1=\prod_{P_{i} \leq n+1}p_{i}^{ \beta_{i}(n+1)}$; where:

$\beta_{i}(n+1)= \alpha_{i}(n+1)-\alpha_{i}(n)$.

Finally, this is the relation:

$\beta_{i}(n+1)= \alpha_{i}(n+1)-\alpha_{i}(n-1)-\beta_{i}(n)$.

In summary, Eq.1 can be used as a method for decomposition in prime factors, let's see an example:

$n=60$

$\beta_{i}(60)=\sum_{t}^{r} \{[\frac {60}{p_{i}^{t}}]-[\frac {59}{p_{i}^{t}}]\}$

Then:

$\beta_{1}(60)=\sum_{t}^{r} \{[\frac {60}{2^{t}}]-[\frac {59}{2^{t}}]\}=2$

$\beta_{2}(60)=\sum_{t}^{r} \{[\frac {60}{3^{t}}]-[\frac {59}{3^{t}}]\}=1$

$\beta_{1}(60)=\sum_{t}^{r} \{[\frac {60}{5^{t}}]-[\frac {59}{5^{t}}]\}=1$

Finally:

$60=2^{2}3^{1}5^{1}$

$\endgroup$

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.