Integer factorization, etc.
in [Math]
|
From: Dik T. Winter on 4 Apr 2008 10:37 In article <fd1ad014-07f8-4adb-9437-c1e51a806887(a)r9g2000prd.googlegroups.com> Risto Lankinen <rlankine(a)gmail.com> writes: > 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] But in the Fermat factorisation also the 'non-interesting' cases are interesting. Consider 91 = 100 - 9, which would factorise 91. In general, if we have N + d^2 = n^2, and N is odd, then at least one of d or n is even. > - 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. I do not know. But that is an algorithm for factorisation with execution time comparable to the technique of division by all odd numbers less than the square root of n. And that is *way* too slow to be of any significance. -- 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 7 Apr 2008 08:44 On 4 huhti, 17:37, "Dik T. Winter" <Dik.Win...(a)cwi.nl> wrote: > > But in the Fermat factorisation also the 'non-interesting' cases are > interesting. Consider 91 = 100 - 9, which would factorise 91. In > general, if we have N + d^2 = n^2, and N is odd, then at least one of > d or n is even. Fermat's factorization suffers a fixation to integers, it's the 'k' in 'N+ki' you really should be interested about. Here's a new [as far as I know] algorithm for complex number square root. It's got lots of things to clean because I just quickly drafted it in order to respond to one poster who emailed directly to me to challenge my previous claim: >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 Anyway, here goes: // ********************************************************************* #include <iostream> using std::cin; using std::cout; using std::endl; struct FactoriComplex { mutable int bit[128]; FactoriComplex( int=0,int=0 ); int Re() const; int Im() const; }; FactoriComplex::FactoriComplex( int re,int im ) { bit[0] = re+im; bit[1] = im; int r; for( r=2;r<128;++r ) { int carry = bit[r-2] & ~1; bit[r-2] -= carry; bit[r-1] -= carry; bit[r] = -(carry>>1); } } int FactoriComplex::Re() const { int re[64]; int im[64]; re[0] = 1; im[0] = 0; int result = re[0]*bit[0]; int r; for( r=1;r<64;++r ) { re[r] = -re[r-1]-im[r-1]; im[r] = -im[r-1]+re[r-1]; result += re[r]*bit[r]; } return result; } int FactoriComplex::Im() const { int re[64]; int im[64]; re[0] = 1; im[0] = 0; int result = im[0]*bit[0]; int r; for( r=1;r<64;++r ) { re[r] = -re[r-1]-im[r-1]; im[r] = -im[r-1]+re[r-1]; result += im[r]*bit[r]; } return result; } bool Squirt( const FactoriComplex &arg,int b=0 ) { int chip; int dale; int r; int s; // arg.Normalize(); if( (arg.bit[0]!=1) || (arg.bit[1]!=0) ) { return false; } for( r=3;r<128;r+=2 ) { if( arg.bit[r] & 1 ) { arg.bit[r]++; arg.bit[r-1] += 2; arg.bit[r-2] += 2; } } if( !(arg.bit[1]&2) != !(arg.bit[2]&1) ) { return false; } if( !(arg.bit[2]&2) != !(arg.bit[4]&1) ) { return false; } for( r=6;r<128;r+=2 ) { chip = 0; for( s=r;s>r-s;--s ) { chip += (arg.bit[s]&arg.bit[r-s]&1); } dale = arg.bit[s]>>1; if( (chip&1) != (dale&1) ) { if( r > 64 ) { return false; } if( arg.bit[r] > 0 && arg.bit[r-1] > 1 && arg.bit[r-2] > 1 ) { arg.bit[r]--; arg.bit[r-1] -= 2; arg.bit[r-2] -= 2; } else { arg.bit[r]++; arg.bit[r-1] += 2; arg.bit[r-2] += 2; } chip = 0; for( s=r;s>r-s;--s ) { chip += (arg.bit[s]&arg.bit[r-s]&1); } } while( chip < dale ) { arg.bit[s+2] -= 2; arg.bit[s+1] -= 4; arg.bit[s] -= 4; dale = arg.bit[s]>>1; } while( chip > dale ) { arg.bit[s+2] += 2; arg.bit[s+1] += 4; arg.bit[s] += 4; dale = arg.bit[s]>>1; } } return true; } int main() { bool b; int n; int r; do { cout << "N = "; cin >> n; if( n & 1 ) { for( r=0;r<(n*n-1)/8+1;++r ) { FactoriComplex f( n,4*r ); b = Squirt( f ); if( b ) { cout << f.Re() << " + " << f.Im() << "i"; cout << " is a SQUARE" << endl; break; } } } else { if( n ) { cout << "N should be odd (or 0 to quit)." << endl; } else { break; } } } while( n ); return 0; } // *********************************************************************
From: Pubkeybreaker on 7 Apr 2008 09:32 On Apr 7, 8:44 am, Risto Lankinen <rlank...(a)gmail.com> wrote: > On 4 huhti, 17:37, "Dik T. Winter" <Dik.Win...(a)cwi.nl> wrote: > > > > > But in the Fermat factorisation also the 'non-interesting' cases are > > interesting. Consider 91 = 100 - 9, which would factorise 91. In > > general, if we have N + d^2 = n^2, and N is odd, then at least one of > > d or n is even. > > Fermat's factorization suffers a fixation to integers, Huh? This last sentence is pure gibberish. > it's the 'k' in 'N+ki' you really should be interested > about. > > Here's a new [as far as I know] algorithm for complex > number square root. It's got lots of things to clean > because I just quickly drafted it in order to respond > to one poster who emailed directly to me to challenge > my previous claim: Noone is going to bother to wade through your code. If you want to be taken seriously, then post a description of the method, ALONG WITH AN ANALYSIS OF ITS COMPLEXITY. Do not post code. Noone has the time or inclination to read it. And I suggest you stop being so argumentative and listen to some of the experts here. Dik Winter is one such. Listen to him. Your "method" is O(sqrt(N)) at best. It is useless for any number bigger than a few digits.
From: Risto Lankinen on 7 Apr 2008 10:54 On 7 huhti, 16:32, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote: > Do not post code. Noone has the time or inclination to read it. My article was posted on multiple fora. Please indicate the particular one that was offended by my article and I'll discontinue posting there. - Risto -
From: Dik T. Winter on 7 Apr 2008 11:02
In article <59f2d3e8-f954-4973-8ab9-0610dc8e8536(a)l28g2000prd.googlegroups.com> Risto Lankinen <rlankine(a)gmail.com> writes: > On 4 huhti, 17:37, "Dik T. Winter" <Dik.Win...(a)cwi.nl> wrote: > > > > But in the Fermat factorisation also the 'non-interesting' cases are > > interesting. Consider 91 = 100 - 9, which would factorise 91. In > > general, if we have N + d^2 = n^2, and N is odd, then at least one of > > d or n is even. > > Fermat's factorization suffers a fixation to integers, > it's the 'k' in 'N+ki' you really should be interested > about. But the 'k' was integer I thought? -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ |