If $n=\prod_{i=1}^{k} p_i^{e_i}$ is a prime factorization of integer $n$.
Is there a quick way to find the prime factorization of $n+1$?
Or the only way to do it is recalculating the whole factorization?
Any references and/or articles on this problem?
Check out the literature on Fermat numbers, $2^{2^n}+1$. If factoring $m$ helped you factor $m+1$, these numbers would be a cinch, but they're not.
The general philosophy is that multiplication and addition do not "see" each other. So the fact that one knows the multiplicative structure of n does not say anything about the multiplicative structure of n+1. There are several demonstrations of this philosophy.
One of them concerns twin primes: a well-known heuristic, first exploited by Cramer, says that a random number $n$ is prime with probability $1/\log n$ (this is supported by the Prime Number Theorem). However, if we assume that $n$ is a prime number, then it is believed that the probability of $n+2$ being a prime number is still $1/\log n$, provided that there no local obstructions to this (for example, if $n\equiv1\pmod 3$, then this is trivially false). In other words, $n+2$ does not "know" whether $n$ is prime or not. Indeed, a quantitative form of the twin prime conjecture states that
$$|\{n\le x:n~{\rm and}~n+2~{\rm are~prime~numbers}\}|\sim\frac{cx}{\log^2x},$$
where $c$ is some constant which arises due to the local obstructions mentioned above.
A second demonstration of this philosophy is the Erdos-Szemeredi conjecture which, in its simplest form, states that if $A$ is a set of integers and we set
$$A+A=\{a+b:a,b\in A\}\quad{\rm and}\quad A\cdot A=\{a\cdot b:a,b\in A\},$$
then
$$\max\{|A+A|,|A\cdot A|\}\ge c_\epsilon|A|^{2-\epsilon}$$
for every $\epsilon>0$, where $c_\epsilon$ is some constant that depends only on $\epsilon$. Roughly, this conjecture says that $A$ cannot have both additive and multiplicative structure, which would reduce the cardinality of $A+A$ and $A\cdot A$.
To elaborate on azorne's answer. We can do it in a way reminding of how we can take $n$'th powers modulo a number in about $\log n$ time.
Assume that there is a fast way to do what you want, and that we want to factor $n$. Then either $n$ or $n-1$ is divisible by 2. If $n-1$ is divisible by 2 then this reduces down to factor $(n-1)/2$ + one operation of knowing the factorization of $n-1$ to obtain a factorization of $n$. If $n$ is divisible by two we can just divide by two to reduce the factorization to the factorization of $n/2$.
Thus we see that to factor $n$ takes at most the time to factor $[n/2]$ + One operation of knowing the factor of $n-1$ to factor $n$.
If we do this in $\log_2 n$ steps we will come down to trivial numbers to factor, and thus we see that the time it takes to factor a number $n$ will be at most $\log_2 n \times $ "the maximum time it takes to go from knowing the factorization of $m$ to factor $m+1$ for $m \leq n$". This can certainly not be fast (e.g. polynomial time in $\log n$) since it would give a polynomial time algorithm (in $\log n$) to factor an arbitrary number $n$. No such algorithm is known of course. The number field sieve is expected to be the fastest known algorithm discovered yet, although the estimates for the time complexity it takes is just estimated heuristicly and is not proven rigorously.
I don't think there is a way to do so, because then factoring large numbers would be trivial. Assuming 'quick' means polynomial time, we can build up a series of polynomial time computations, starting from a given number, whose factorization is known. This since each subroutine is in polynomial time, and all the main program does is call subroutines to factor consecutive numbers, we'd end up with a polynomial time algorithm to factor integers.
EDIT: the above logic isn't formal, but I'm sure somebody else here can do a better job than me at making it rigourous.
There are two questions asked:
Q1. Does the prime factorization of $n$ give a quick way to find the prime factorization of $n+1$?
A1.No it does not (as noted in other answers). Knowing $n$ is prime is of no use.
Q2. Is it ever of any use or do you always just have to start from scratch? (as I will choose the rephrase the question.)
A2. It is sometimes of use but not usually. When $n$ is a power of a smaller number there may be some help. Since the case of Fermat numbers was raised I will comment that factoring numbers of the form $2^e+1$ is somewhat easier (relative to the size) than numbers of the form $2^e+3$. Given $n=2^e$ we know that $2^{e/f}+1$ is a factor of $n+1$ where $f$ is any odd divisor of $e$. So that is a start to factoring $n+1$. In the case $n=2^{2^e},$ $n+1$ might be prime. To test primality one has Pépin's test. The numbers involved are so huge that this is not practical very far out. ALSO it is known that any candidate factor must be of the form $k2^e+1$ so in attacking $2^{2^{20}}+1$ (known composite, no factors known) we have already ruled out 99.9999% of the possible factors.
Here is an elaboration on the idea. Suppose we knew the prime factorization of many numbers near n. Could we use that information in factoring n?
The one thing we can say: if k is relatively prime to (n+k), then none of the prime factors of (n+k) can be factors of n. Since there are (on average) roughly log(log n) distinct prime factors for (n+k) for small k, one would not be able to elimnate many of the pi(sqrt(n)) candidates for the smallest prime factor of n, unless n is of a special form like a Mersenne or Fermat number, which has its own theory for factorization.
So, apart from elimnating O(log(log(n))) prime factors from consideration (or providing a small factor which could be found quickly with trial factorization), knowing the prime factorization of many numbers near n itself is not likely to help. Even in the special case that n is one away from a power or a small multiple of a power still leaves a lot of work to be done.
Gerhard "Ask Me About System Design" Paseman, 2011.02.10
