  New algorithms for prime factorization that outperform the existing ones or
take advantage of particular properties of the prime factors can have a
practical impact on present implementations of cryptographic algorithms that
rely on the complexity of factorization. Currently used keys are chosen on the
basis of the present algorithmic knowledge and, thus, can potentially be
subject to future breaches. For this reason, it is worth to investigate new
approaches which have the potentiality of giving a computational advantage. The
problem has also relevance in quantum computation, as an efficient quantum
algorithm for prime factorization already exists. Thus, better classical
asymptotic complexity can provide a better understanding of the advantages
offered by quantum computers. In this paper, we reduce the factorization
problem to the search of points of parametrizable varieties, in particular
curves, over finite fields. The varieties are required to have an arbitrarily
large number of intersection points with some hypersurface over the base field.
For a subexponential or poly- nomial factoring complexity, the number of
parameters have to scale sublinearly in the space dimension n and the
complexity of computing a point given the parameters has to be subexponential
or polynomial, respectively. We outline a procedure for building these
varieties, which is illustrated with two constructions. In one case, we show
that there are varieties whose points can be evaluated efficiently given a
number of parameters not greater than n/2. In the other case, the bound is
dropped to n/3. Incidentally, the first construction resembles a kind of
retro-causal model. Retro-causality is considered one possible explanation of
quantum weirdness.
