Integer factorization, etc.
in [Math]
|
From: Risto Lankinen on 30 Mar 2008 16:26 Hi! Given integers x >=y, define a=(x+y)/2 and d=(x-y)/2 . Semanticly 'a' is the average of x and y, and 'd' is the difference of 'a' and either. Then (a+di)^2 = (a^2-d^2)+2ad = xy + 2adi . Consequently, to factorize a given n = xy one needs to find a square root of (n+ki) [where k needs to be computed] so that SQRT(n+ki) = (a+di). Done that, the factors x=a+d and y=a-d are trivially found. Is there any literature [preferably pointers to the 'net] about any factorization algorithm that relies on this premise? - Risto - P.S. I am a layman. To avoid getting the crackpot treatment on sci.* fora, here are pointers to some of my earlier stuff: http://groups.google.fi/group/sci.math/tree/browse_frm/thread/fdc68ab01562961c/b232bb30bba1455b http://groups.google.fi/group/sci.math/msg/0184d65ab913e0b5
From: rossum on 30 Mar 2008 17:01 On Sun, 30 Mar 2008 13:26:18 -0700 (PDT), Risto Lankinen <rlankine(a)gmail.com> wrote: >Is there any literature [preferably pointers to the 'net] about >any factorization algorithm that relies on this premise? Yes, see Fermat's Factorisation Method: http://en.wikipedia.org/wiki/Fermat's_factorization_method rossum
From: Dik T. Winter on 2 Apr 2008 08:46 In article <5eeefe46-445d-4580-b3fc-aae57ecb0550(a)i29g2000prf.googlegroups.com> Risto Lankinen <rlankine(a)gmail.com> writes: .... > Fermat's Factorization indeed uses the same premise, but > it puts the emphasis on solving the real part a^2-d^2 = N > only, while it totally disregards the imaginary part 2adi . There is not much difference. > Put differently, it concentrates on finding a square that > differs from N by an amount equal to a different square, > or that N-a^2 = b^2 . Generation of squares is fast, but > there is another reason why this is difficult since [afaik] > no "quick" detection exists, of whether a number is a > square, other than sqrt:ing it. That is why the method has been extended to methods like MPQS where you are guaranteed to find a square in the end. > Clearly N-ki = c^2 [c being complex integer] is a different > kind of relationship. Actually it is not. Finding k and c such that k = 2ad and c = a + di is the same as finding a and d such that N + d^2 = a^2. > Anyway, fast algorithms exist > for finding 'k' so that e.g. N+k*2 is a square of an integer, > so how hard can it be to detect whether N+k*i is a square > of a complex integer [a.k.a. Euler's number?!?] ? About just as hard as for any such number. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: Risto Lankinen on 2 Apr 2008 15:49 On 2 huhti, 15:46, "Dik T. Winter" <Dik.Win...(a)cwi.nl> wrote: > > Clearly N-ki = c^2 [c being complex integer] is a different > > kind of relationship. > > Actually it is not. Finding k and c such that k = 2ad and c = a + di > is the same as finding a and d such that N + d^2 = a^2. Well, this neglects the extra info provided by k = 2ad . Consider binary system. Square integers have a signature which I don't know how to define formally, but examples are shown below: legend: decimal = binary ==> square signature 3 = 11 ==> 121 5 = 101 ==> 10201 7 = 111 ==> 12321 9 = 1001 ==> 1002001 11 = 1101 ==> 1212201 13 = 1011 ==> 1022121 15 = 1111 ==> 1234321 Index the bits of a square signature from right to left, starting from zero and ending to 2n . Some of the characteristics of square signature are then: - First and last digit is always '1' [in the interesting cases] - Only digits with even index can ever be odd - Digit having index b depends on the parities of the digits having even index in the range 0..2b . Consequently, the parity of digit having index 2b depends on the prior digits that have an even index, and the digit having index b (this is an important point for an algorithm that transfers a square binary number into a square signature) This algorithm... http://groups.google.fi/group/sci.math/msg/2366da90e8cbbb00 ... is easily modified to convert a binary number into a square signature in the manner just described. Ha, but that's just binary. Let's use number base i-1 instead! Base i-1 has exponents {1,-1+i,-2i,2+2i,-4,4-4i,8i,-8-8i,16, ...}. A "binary" selection of exponents can address any Gaussian integer in the complex plane. Yet, squares of base i-1 values still obey the square signature concept just outlined. The carry/borrow rule is quite interesting, though. The borrow rule in decimal is {-1,+10}, and in binary it is {-1,+2}, whereas in base i-1 it is {+1,+2,+2} (because b^2+2b+2 = 0 ). So anyway, because there is a relatively easy way to... 1. convert a [gaussian] integer to "binary" i-1 representation, ... 2. either convert it to square signature (if possible), or... 3. inject -2i by adding 1 to digit having index 2 (value=-i) and redo from step 2. ... it looks to me like a straightforward scan for N-ki = c^2 can be programmed - what's more, without a single multiplication! - Risto -
From: titech_shu on 4 Apr 2008 09:18
Risto Lankinen wrote: > On 2 huhti, 15:46, "Dik T. Winter" <Dik.Win...(a)cwi.nl> wrote: > > > �> Clearly N-ki = c^2 [c being complex integer] is a different > > �> kind of relationship. > > > > Actually it is not. �Finding k and c such that k = 2ad and c = a + di > > is the same as finding a and d such that N + d^2 = a^2. > > Well, this neglects the extra info provided by k = 2ad . > > Consider binary system. Square integers have a signature > which I don't know how to define formally, but examples are > shown below: > > legend: decimal = binary ==> square signature > > 3 = 11 ==> 121 > 5 = 101 ==> 10201 > 7 = 111 ==> 12321 > 9 = 1001 ==> 1002001 > 11 = 1101 ==> 1212201 > 13 = 1011 ==> 1022121 > 15 = 1111 ==> 1234321 > > Index the bits of a square signature from right to left, starting > from zero and ending to 2n . Some of the characteristics of > square signature are then: > > - First and last digit is always '1' [in the interesting cases] > - Only digits with even index can ever be odd > - Digit having index b depends on the parities of the digits > having even index in the range 0..2b . Consequently, the > parity of digit having index 2b depends on the prior digits > that have an even index, and the digit having index b > (this is an important point for an algorithm that transfers > a square binary number into a square signature) > > This algorithm... > > http://groups.google.fi/group/sci.math/msg/2366da90e8cbbb00 > > ... is easily modified to convert a binary number into a square > signature in the manner just described. > > Ha, but that's just binary. Let's use number base i-1 instead! > > Base i-1 has exponents {1,-1+i,-2i,2+2i,-4,4-4i,8i,-8-8i,16, ...}. > A "binary" selection of exponents can address any Gaussian > integer in the complex plane. Yet, squares of base i-1 values > still obey the square signature concept just outlined. > > The carry/borrow rule is quite interesting, though. The borrow > rule in decimal is {-1,+10}, and in binary it is {-1,+2}, whereas > in base i-1 it is {+1,+2,+2} (because b^2+2b+2 = 0 ). > > So anyway, because there is a relatively easy way to... > 1. convert a [gaussian] integer to "binary" i-1 representation, ... > 2. either convert it to square signature (if possible), or... > 3. inject -2i by adding 1 to digit having index 2 (value=-i) and > redo from step 2. > > ... it looks to me like a straightforward scan for N-ki = c^2 can > be programmed - what's more, without a single multiplication! > > - Risto - |