There are methods to find out prime factorization of a given number but Is there a method to find the prime factorization of a number(integer) if the prime factorization of the previous number(integer)?. (Using only the information of previous number.)
3
-
3$\begingroup$ As @robert-israel points out this is easily shown to not work. Perhaps a more interesting question would be -- given a number $n$ and an oracle that will factor any number that is not a multiple of $n$, can you efficiently factor $n$? ... although I seriously doubt there would be any interesting way to use the oracle, proving so is probably very hard. $\endgroup$– Alex MeiburgCommented Sep 8, 2016 at 6:42
-
$\begingroup$ @AlexMeiburg: well, if you can find one factor then the oracle deals with the rest, so there's a significant advantage if $n$ has a small prime factor and a couple of large hard-to-find prime factors. For instance if $n$ is twice your RSA public key then you're in trouble ;-) $\endgroup$– Steve JessopCommented Sep 8, 2016 at 9:54
-
$\begingroup$ Worth mentioning in this context: the Pollard p-1 algorithm, which is a special-purpose algorithm for factorizing $n$ for which the prime factors $p$ of $n$ have the property that $p-1$ is a product of small coprime factors. Not at all the same thing as a way of factorizing $n$ when you know the factors of $n-1$, though: it's $p-1$ rather than $n-1$ and what matters is what the factors are like rather than whether you know them. $\endgroup$– Gareth McCaughanCommented Sep 8, 2016 at 9:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
The prime factorization of $2^{1048576}$ is very easy, but no prime factors of $2^{1048576}+1$ are known.
answered Sep 8, 2016 at 6:38
-
$\begingroup$ But it's still possible that a) there is an algorithm $A$ for computing the prime factorization of $n+1$ given the prime factorization of $n$, b) $A$ runs faster than any algorithm that does not take as given the prime factorization of $n$, and c) $A$ is too slow, in practice, to find the prime factors of $2^{1048576}+1$. [Or c') $A$ hasn't been discovered yet.] $\endgroup$ Commented Sep 8, 2016 at 13:23