Standard factorization methods use whole numbers. There is always a certain number of steps including modulo operations, but the numbers are considered from the beginning to the end, i.e. from the Most to the Least Significant Bits (LSBs).
Another approach could be derived from the simple following number puzzle (not sure a solution exists for this one):
A B C * C ----- 1 2 3 5
It is only necessary to look at the end of the numbers, i.e. the C, to see that there is only one solution C=5. This is the raw idea: try to deduce the LSBs first, without processing the whole numbers. A recursive search would systematically look at all pairs of LSB strings:
p = X X 0 0 1 0 * q = X X 0 1 0 0 ----------------- n = X X 1 0 0 0
A common transformation used by other methods is done as following: if n is the product, p and q its factors, it is always possible to set:
n = pq = (a+b)(a-b) = a²-b², or
n + b² = a²
This operation changes the problem into finding a square number b², add it to n and check if the sum if also a square (a²). The LSBs of squares is something that can be tested as well.
In this form, the method would surely not perform very well compared to others. The idea, if even makes any sense, must be developed and optimized, e.g.:
- The assessment of LSBs could be integrated as speed-up in in another factorization method
- A heuristic criterion could reduce the solutions space of the recursive search
- Using another base for the calculations (i.e. start by converting n into this base) may simplify the assessments on LSBs
- It may be possible to replace the recursive search by the resolution of an equations system