Does FACTORING have optimal substructure or analog to it?

Question

Is there any approach to FACTORING that can leverage optimal substructure allowing the problem to be decomposed into smaller subproblems? That is, perhaps being unnecessarily verbose, until an easily solvable instance is encountered, at which point the ancestry of subproblems can be successively reconstructed from the sequence of solved instances to arrive finally at the solution of the original problem.

In terms of original research toward this question I considered the following two possibilities. It is not thought that either of these are to be very workable, and are here to attempt to illustrate the intended meaning of the question, which then asks whether it is likely there are approaches that could be workable that display optimal substructure or analogous structure:

1. The hypothetical, magical FACTOR_SUCCESSOR function, which when given an integer factorization for X, returns the integer factorization for X+1 in polynomial time in log(X). [This can be used to construct a factoring algorithm to factor N using the binary (or any other) base representation of N.] This hypothetical function seems difficult to construct since, for example, see here.

2. An approximation approach. This would make use of the idea that if large (>500 decimal) N is hard to factor (say a semiprime), then perhaps if N-m is k-smooth, with factors in a multiset F, and then perhaps good approximations to base representation vectors of p and q could be obtained by forming p' and q' from disjoint covering subsets of F. The choice of k determines how expressive F is in being able construct varied factors of about equal size to p and q. It is unclear both if p' and q' would be good approximations to p and q even if they were of similar size and m were small, and even if they were good approximations, the algorithm appears more of a one-shot, and not amenable to iterative betterment of that guess. This is accounting for the idea of 'randomly modifying' parts of the guess p' and q' to then give an m' < m, with the same k-smooth property, and beginning the search for selections of disjoint covering subsets of F nearby to p' and q'. It is unclear whether m' could be easily found, also if the algorithm would get stuck in a local optima, removed from p and q. Which makes it seem quite unworkable.

Edit: it is incorrect to say optimal substructure is a meaningless term since it has both a generally accepted meaning (in computer science referring to problems by which larger instances are amenable to solution using the solution of smaller instances) and also a derivable meaning in that if one considers the possible meanings of "optimal" and "substructure" put together one arrives at a conclusion that such a concatenation is likely to refer to the state of having a substructure which is in some way optimal. In the context of the solution of problems, the intended meaning naturally follows. Maybe Raphael simply doesn't like the question or the answer or both, because they're so meaningful!

Answer 1

No. There's no known optimal substructure like that. Such a substructure would naturally lead to algorithms for factoring large composite numbers, which is a notoriously hard problem. For numbers that are products of two primes, there is no known optimal substructure; these are the kinds of numbers that are used in the RSA cryptosystem, and factoring them has been studied in great depth in the literature. However, the best factoring algorithms known don't use optimal substructure; instead, they use other number-theoretic ideas.

Another way to put it: recursion does not seem like a useful approach to factoring products of two primes efficiently. The natural way to recurse is to find a divisor $d$ of $n$, then recurse on $d$ and $n/d$; but that's a chicken-and-egg problem, because finding a divisor of $n$ is exactly the problem that's hard. For instance, when $n$ is a product of two primes, factoring is the problem of finding a (non-trivial) divisor of $n$. So, the problem is that, to figure out what to recurse on, you first need to solve the problem itself. My thanks to @Raphael for this helpful way of thinking about things.