Say I have a very large number $n$ = $pq$ where $p$ and $q$ are prime.
A new number $n'$ is generated by increasing these prime factors. How can I find this new number's prime factors?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this communitySay I have a very large number $n$ = $pq$ where $p$ and $q$ are prime.
A new number $n'$ is generated by increasing these prime factors. How can I find this new number's prime factors?
On one hand, what's asked in the question's title is finding the factorization of $n'$ given the factorization of "the previous" $n$ as $n=p\,q$. As far as we know, that can't be done for $n'$ of cryptographic interest, for a definition of "previous" implying a small increase in value.
That's part of surrogate factoring, which is to factorization what perpetual motion is to movement.
On a second hand, what's asked in the question is different: finding the factorization of $n'$ given that it is of the form $p'\,q'$ with $p'$ (resp. $q'$) a prime "generated by increasing" some known $p$ (resp. $q$). That makes the task easy, for a definition of "increasing" implying a small increase in value. All there is to do is explores the integers $p'$ above $p$ sequentially, and try if they divide $n'$, until hitting the factorization; it is not even necessary to check that $p'$ is prime.
On a third hand, a comment tells that "$n$ grows by a digit each round", which implies that at least one of $p$ or $q$ has changed a lot in value. If only one has changed a lot, we can try the above method on both $p$ and $q$. If both have changed, and we have no clue about how, then the factorization of $n$ is useless to find that of $n'$, and we are back to the problem of factorization of $n'$ without clue, which can be handled up to 800 bits (240 decimal digits) give or take 50%, depending on resources.
Let's assume the question as stated is solveable. And knowing the factorization of some number n with smaller p and q prime factors helps us find the larger factors of n'.
I will add that 6=2*3 match the requirements for n=p*q and p,q are obviously smaller than the factors of n'
Since I'm not holding my breath waiting for my Turing award for an efficient factorization algorithm. We conclude in general knowing n=p*q with smaller p and q doesn't help us.
If we know p-p' is small howerver we can just search for primes ot for possible devisors starting at p.
Well, if you know n, p, q and n' it would be simple to brute force to find the factors of p' and q'
PRE-REQUISITE
We will be using the li(x) approximation used to find all prime numbers less than x. Please take a quick look over the prime counting function. (The li(x) function is also described there).
Look into the Miller–Rabin primality test where the time Complexity for determining whether a number is prime is O(log(n)).
Solution
Let us define n' = p'q' where p' > p and q > q'. We can then define the smallest possible prime possible for n' as x >= min(p,q). Note we only >= instead of > for equality simplification.
We can also define the largest possible prime for n' as x' <= n'/min(p,q)
As you can see, our range of prime numbers went from the range of being in between n and n' to x and x'. (Or to be precise, between min(p,q) and n'/min(p, q))
This is where we now look into the li(x) function. Observe that to find the number of primes between x and x' can be defined as:
li(x') - li(x) which can be expressed as
Thus, the number of primes in between these two are quite small relative to the size of li(n') since the growth of primes is logarithmic (which means that we decreased the number of potential prime factors at quite an exponential rate).
Finally, this is where we use the Miller–Rabin primality test to quickly test each large prime to see if it is the prime in O(log(n)) time. Thus, we can brute force and discover the factors of n' since we have a small possibility list and a quick way to check for probabilistic primes.
Example
For example purposes use the primes p = 17, q = 23, p' = 59 and q' = 89 and try to follow the steps by hand till you reach the integral part. Hopefully, it'll make more sense running the algorithm side by side.
if p is the smaller factor
$n = p * q$
$q = \frac{n-p}{p}+1$
By iteration starting from p = 2, p + 1 if the equation is false
$n = p * q$