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?
-
1$\begingroup$ Is there are specific algorithm you use when you increase your prime factors, or do you use any arbitrary $p', q'$ which are greater than $p, q$? $\endgroup$ – poncho Apr 17 '18 at 12:27
-
$\begingroup$ The algorithm is unknown - only the current iteration count and $n′$ is provided. $\endgroup$ – don juan Apr 17 '18 at 12:44
-
1$\begingroup$ If $p'-p$, $q'-q$ is guessable (e.g. $p'$ is the next prime larger than $p$), then simple algebra will provide the factorization. If $p'$ is just some arbitrary prime that is guaranteed to be larger than $p$, well, there ain't much you can do. $\endgroup$ – poncho Apr 17 '18 at 12:47
-
$\begingroup$ What's the order of magnitude of $n$ and $n'-n$ (say, their number of bits / base-2 logarithm)? Is it correct that the factorizations of both $n$ and $n'$ are not known? $\endgroup$ – fgrieu♦ Apr 17 '18 at 14:19
-
2$\begingroup$ Actually, if $n \approx 10^{120} \approx 2^{400}$, then that is small enough to factor directly; look up "Factoring as a Service". $\endgroup$ – poncho May 17 '18 at 19:36
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ Unless $p'-p$ and $q'-q$ are small (which the OP did not state; only that these values are positive), then this search is infeasible. And, if they are small, then there are easier ways to do the search (which don't even need knowledge of $p, q$) $\endgroup$ – poncho Apr 17 '18 at 18:33
-
$\begingroup$ Agreed, in order for this to work p′−p and q′−q need to be small which I misread. As for easier ways, I feel this would be more optimized in solving the problem $\endgroup$ – Haris Nadeem Apr 17 '18 at 20:12
-
$\begingroup$ @poncho Intuitively, I would have followed the same scheme as the one from Haris Nadeeem ; Would you mind sharing your "search method" ? Thank you ;-) $\endgroup$ – Jérémy Métairie Apr 18 '18 at 8:23
-
3$\begingroup$ @JérémyMétairie: well, if we denote $a = p'-p$ and $b = q'-q$, then we know $N=pq$ and $N'=(p+a)(q+b)$. A bit of algebraic shuffling gives $(N'-N-ab)^2 - 4abN = (bp-aq)^2$; in other words, when the LHS is a perfect square. So, for various guesses of $ab$, we compute the LHS modulo various small primes; for an incorrect guess, the LHS has a circa 0.5 probability of being a quadratic nonresidue, and hence cannot be the correct $ab$. Once an $ab$ passes the tests, then we can run fuller tests. Most arithmetic is done single precision, hence it ought to be faster than prime testing... $\endgroup$ – poncho Apr 18 '18 at 12:27
-
$\begingroup$ @poncho that's very interesting! I would never have thought of that, thanks for sharing! $\endgroup$ – Haris Nadeem Apr 18 '18 at 16:25
$\begingroup$
$\endgroup$
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$
