LSB-based integer factorization

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 , add it to n and check if the sum if also a square (). 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
Advertisements

,

  1. #1 by s-987618 on November 22, 2012 - 14:57

    This is the best idea about integer factorization, written here is to let more people know and participate.
    A New Way of the integer factorization
    1+2+3+4+……+k=Ny,(k<N/2),"k" and "y" are unknown integer,"N" is known Large integer.
    True gold fears fire, you can test 1+2+3+…+k=Ny(k<N/2).
    How do I know "k" and "y"?
    "P" is a factor of "N",GCD(k,N)=P.

    Two Special Presentation:
    N=5287
    1+2+3+…k=Ny
    Using the dichotomy
    1+2+3+…k=Nrm
    "r" are parameter(1;1.25;1.5;1.75;2;2.25;2.5;2.75;3;3.25;3.5;3.75)
    "m" is Square
    (K^2+k)/(2*4)=5287*1.75 k=271.5629(Error)
    (K^2+k)/(2*16)=5287*1.75 k=543.6252(Error)
    (K^2+k)/(2*64)=5287*1.75 k=1087.7500(Error)
    (K^2+k)/(2*256)=5287*1.75 k=2176(OK)
    K=2176,y=448
    GCD(2176,5287)=17
    5287=17*311

    N=13717421
    1+2+3+…+k=13717421y
    K=4689099,y=801450
    GCD(4689099,13717421)=3803
    13717421=3803*3607

    The idea may be a more simple way faster than Fermat's factorization method(x^2-N=y^2)!
    True gold fears fire, you can test 1+2+3+…+k=Ny(k<N/2).
    More details of the process in my G+ and BLOG.

    My G+ :https://plus.google.com/u/0/108286853661218386235/posts
    My BLOG:http://hi.baidu.com/s_wanfu/item/00cd4d3c5a2fd089f5e4ad0a
    Email:wanfu.sun@gmail.com

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: