15
$\begingroup$

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?

$\endgroup$
5
  • 6
    $\begingroup$ A lower bound on the difficulty: if it were too easy to do this, we could do it twice and either prove or disprove the twin prime conjecture. $\endgroup$ Feb 10, 2011 at 12:40
  • 8
    $\begingroup$ One special case not mentioned so far: With the factorization of $n$ you can determine if $n + 1$ is prime or not, see en.wikipedia.org/wiki/Lucas_primality_test (This is significantly faster than finding the factorization if $n+1$ is not a prime.) $\endgroup$ Feb 10, 2011 at 14:23
  • 6
    $\begingroup$ A trivial observation: $n+1$ and $n$ have no prime factors in common. $\endgroup$ Feb 10, 2011 at 21:54
  • 1
    $\begingroup$ The answer is no, but there is a quick way to rigorously prove if $n+1$ is prime, see e.g. <primes.utm.edu/prove/prove3_1.html>. $\endgroup$ Feb 4, 2020 at 15:31
  • $\begingroup$ The problem: "Given the factorization of n, find the factorization of n+1" is as hard as factoring in general. Suppose we had an algorithm for the n+1 problem. Then we can factor an arbitrary n using a "double-and-add" algorithm: On input n: Start with a=0, a_factors = None; For all bits b of n from MSB to LSB { if b = 1 { let a, a_factors = nplusone(a, a_factors) }; let a = a*2 and add 1 to the exponent of 2 in a_factors; } undo the last (extra) mul by 2 in a, a_factors; return a_factors; This ends with a=n, by double-and-adding, updating the prime factors at each step. $\endgroup$ Oct 1, 2023 at 20:21

6 Answers 6

22
$\begingroup$

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.

$\endgroup$
1
  • 8
    $\begingroup$ And Fermat numbers are just one such example. Other examples with the factorization of $m$ being known and that of $m+1$ being hard include primorial $n$#$ + 1$, factorial $n!+1$, Proth $k⋅2^n+1$, generalized Fermat $b^{2^n}+1$, ... Actually, I might start to cry if the factorization of these numbers turned out to be trivial. $\endgroup$ Feb 10, 2011 at 13:42
13
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ "Polynomial time" in this context means polynomial in the length of $n$, which is to say polynomial in $\log n$. So to carry out this idea, you'd have to find an easily factored number pretty close to $n$ first, and I'm not sure there's a guarantee such a thing exists. You're right that factoring $n$ doesn't much help you to factor $n+1$, but I don't think the supporting argument is right. $\endgroup$ Feb 10, 2011 at 11:24
  • 2
    $\begingroup$ A remark regarding the supporting argument merely rephrasing azome's answers a bit, which I believe at least under standard conjectures on gaps between primes makes it sound. There (conjecturally) always exists a prime below $n$ at distance polynomial in $\log n$. So, one could start testing for primes below $n$, using for each test something polynomial in $\log n$ polynomialy in $\log n$ often so still polynomial. Having found a prime, factorization of it is of course for free, and then go back up the polynomially in $\log n$ many steps to $n$. $\endgroup$
    – user9072
    Feb 10, 2011 at 18:24
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I would say "not much use", as knowing n prime and sufficiently large gives that n+1 is even. Otherwise, I agree with your post. For more on the subject, I recommend Hans Riesels book on computer methods for factorization and primality testing. Gerhard "Ask Me About System Design" Paseman, 2011.02.24 $\endgroup$ Feb 24, 2011 at 18:25
2
$\begingroup$

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

$\endgroup$

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