Factorization Using Statistical Methods

Question

We consider a number $N=AB$ where $A$ and $B$ are primes. Along the whole number-line from $1$ to $N$ we have two success points or target points: $A$ and $B$. If we had millions of target points the situation perhaps could have been better.

In the interval from $1$ to $N$, $A$ occurs $B$ times as a factor with different numbers:$1A,2A,\cdots,AB$

$B$ occurs as a factor with other numbers $A$ times:$1B,2B,3B,\cdots,AB$.

So we have a huge number of targets but we have to try out $gcd$ on the computer between $N$ and arbitrary large numbers less than $N$[using the division method]. Numbers larger than N might also be taken.

For a four hundred digit number we will have about $2*10^{200}$ target points for a bombing operation instead of two points $A$ and $B$, on the interval 1 to N.

There is a large increase in the density of targets in the range from 1 to N [to be precise on the interval from $\sqrt{N}$ to N].

For gaining efficiency, we may bend the number-line (from $1$ to $N$) round and round and then fire at the "targets" to improve the probability of success. Is it really going to help in any way if we work out the exercise on a computer using statistical methods?

A Simple Strategy:

Just imagine the number line from 1 to N=AB[and beyond] with the target points A ,2A,3A......AB,A(B+1),A(B+2).....[or B,2B,3B....AB,B(A+1),B(A+2)......] lying on it. Turn it round at the point AB and bring it down parallel to the first line. This will not give us any advantage[of increased target density] since the target points will lie against each other on the composite line. Suppose we do the turning at the point (AB)+1 and bring down the turned line parallel to the first one. The target points will not lie against each other on the composite line. The second line is turned again at the position corresponding to one on the first line or at some other suitable postion . This up and down turning action is repeated over and over again till two targets lie against each other on a pair of lines. Now on the composite line we have more than one,rather several targets on the interval $x$ to $x+\sqrt{N}$ if the composite line is viewed wrt the first line. In the selection process we should choose a point in the first line ,then another on the second and move forward across the lines and test for the gcd[by division method] for each selected point on the composite line with AB.

Some Introductory Calculations: [According to the Suggested Strategy]

We consider the number line from 1 to AB and beyond [from left to right] and extend it to AB+k . Then we bring it down parallel to the initial line to the point one[on the old line].We choose k such that 2k is integral. The extremities on the left are marked $P_1,P_2….$

$P_1=1,P_2=1+2(AB-1)+2k$.

For n similar turns we have:

$P(n)=1+n(2AB-2+2k)$

Let $n=A+j$, where j is a positive integer.[remembering that A is unknown]

$$P(j)=1+(A+j)(2AB-2+2k)$$ $$P(j) =(2AB-2+2k)j+A(2AB-2+2k)+1$$ The above equation is of the form :$y=mx+C$

Where,

$m=(2AB-2+2k)$

$C=A(2AB-2+2k)+1$

[y-mx=C and C-1 contains A as a factor]

Incidentally m and C are integers .”m” is known to us and C-1 contains A as a factor. Of course we don't know C.But we can increase m in steps of one through integral values[by increasing k in steps of 0.5 starting from 0.5] . C will increase in integral steps of A[=2kA] starting from some unknown value on the y-axis. For an integral value of x we can have an integral value of y only[since m and c are integral. On the graph we have an infinite number of inclined straight lines emanating from (0,C) The minimum value of gradient=2AB-1 ,[for k=.5].The gradient is allowed to increase/decrease in integral steps according to our choice.If the gradient increases/decreases by unity the intercept goes up/down by A. If we consider the vertical lines: x=n,where n is an integer., both x and y at the intersections should be integral.

Each line on the graph represents a particular type of bending[a particular value of 2k=integer]. If we move upwards for a fixed, integral value of $x$ the convenient integral points (x,y)on the different lines for which [y-mx-1=C-1 is a multiple of A] are separated by a distance $x+A$.[ k is increased in steps of 0.5]. This information could be used in a trial method where two or more values of x[ie j]are used.

For consecutive x[=j],the portion of a graph-line contains several target points.We may bend these lines over and over again to increase the density of points and consider their projections on the x-axis.

[We may ,alternatively, rotate the different graph lines[after bending them] to make them parallel wrt each other and then bring all the target points on the same straight line to increase the target density]

Answer 1

Most of the state of the art factorization methods, e.g. Quadratic Sieve, Number Field Sieve, Elliptic Curve Factorization use variants of the ideas you suggest. The Elliptic curve method is completely probabilistic in that you pick a curve and a point raise the point to a power and check to see if you have found a factor (this is vastly oversimplified, but a detailed description would take quite a while google is your friend). The sieving methods are more deterministic in that you search for relations (each of which in a sense tells you a little about a factor) until you find enough relations until you have enough relations to form an invertible binary matrix.

Statistical arguments are used to choose optimal parameters for all these methods.

Answer 2

Unfortunately, the increase in density of targets isn't as great as you think; as you note there are $B$ multiples of $A$ less than $n$ and $A$ multiples of $B$ less than $n$. This gives you $A+B$ 'targets' to hit in an interval of size $n$. Picking $B\gt A$ for clarity, this means there are less than $2B$ total targets to hit, giving a probability of $\leq {2B\over n}$ for each shot to hit one, and meaning that it will take on average $\geq {n\over 2B} = \Theta(A)$ shots before you find a number $t$ with $\mathrm{GCD}(t,n)\gt 1$; this is no faster fundamentally than testing all the numbers up to $A$ (i.e., the smallest factor of $n$).

On the other hand, similar statistical ideas were used for some of the first real algorithmic speedups for factoring; in particular, the Pollard $\rho$ method takes avantage of an instance of the Birthday Paradox to factor $n=A\cdot B$ in time proportional to $\sqrt{A}$ rather than time proportional to $A$.