Krdytkyu

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)?

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 $npm 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 &= 4cdot62873\
62872 & = 8cdot7859 \
7860 &= 4·1965 \
1964 &= 4cdot491 \
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$.

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

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}$