Playing with different radix

[LoveCraft]

Hi,

Working on a Factoring program, wich i finally use to help me to better understand in number theorical instead of really factoring, because i implemented a lot of types of sieving matrix, plotting tools, and factoring algorithm of my own, to see what really happen with factors when numbers goes larger.
I saw a lot of interesting properties, (there's 2 years i work on it ) and i have no clues if they are all already well know.
Just one found by my program (i have a LOT like these) :

N=P*Q
P and Q are primes.

XX1=-((N-1)/2)²
XX2=((N+1)/2)²
XX2-XX1=N (that's not a scoop i know)

NS = XX2-((P+Q)/2)² = XX1-((Q-P)/2)² (not a scoop i guess...)

NS =((P-1 * P+1 * Q-1 * Q+1) / 4 ) = 0 mod 144 (i hope that's more interesting)

Field144=[sqrt(XX1)/sqrt(144)]
(XX1 % Field144 ) = (a square) = Square

XX1- Square = Field144*144
Field144 % NS = (an other square very near to ( (P+Q)/2/144)² )
thats work with any divisor of NS and also with XX2, so if P-1*P+1*Q-1*Q+1 is smooth, it's 'relatively' easy to find NS2

I already got an algo tha's use this principle (and some others), it is not really fast, but it work, and on some special numbers it is fast, even very big ones. to be continued......



Well that's was not the thing i wanted to talk, i want talk about radix.

I noticed some curious behaviors using different radix.
I'm not sure how to explain this in correct Math English, so, i will begin by the begining.
I call the last digit in Radix X the last digit of base X.
Sample : 51261071 = 0x030E2E8F
The last digit in base 100 = 71
The last digit in base 256 = 0x8F or = 143 (because 0x8F=143)
It is important to notice the 'or = 143', because i will work in large base, and althought my program work in base 32bit (0x100000000), i write the base in radix 10 for easier reading and i separate the digits radix with a '.'
Sample in base 100: 51261071 = 51.26.10.71

Now the behaviors :
this is some of the result for RSA-704
the first number is a possible solution for the last digit RR2 = ((P+Q)/2)² in base X
the second is a possible solution for the last digit RR1 = ((P-Q)/2)² in base X
the third is the last digit RSA-704 in base X

Here are some interesting solutions.

RR2 = ((P+Q)/2)²
RR1 = ((P-Q)/2)²

Base X : RR2 - RR1 = RSA-704

Base 48 : 01.16 - 09 = 01.07
Only 1 possible solution in base 48

Base 144 : 001.064 - 009 = 001.055
Only 1 possible solution in base 144

Base 1008 : 0001.0064 - 0441 = 0631
Base 1008 : 0001.0352 - 0729 = 0631
Only 2 possibles solutions in base 144

Base 5040 : 0001.0064 - 3465 = 1639
Base 5040 : 0001.1360 - 4761 = 1639
Base 5040 : 0001.2080 - 0441 = 0001.1639
Base 5040 : 0001.4384 - 2745 = 0001.1639
Only 4 possibles solutions in base 5040

In Computer programming, we often work with Base 256, wich is a Byte, then comparing the last byte can help, but my program told me that there's 4 possible solutions in base 256, AND 4 possible solution in base 5040, so looking for digit in base 5040 instead of the last Byte can help a LOT in some Factoring Algos, and surpass the computing time used to get the last digit in radix 5040.

Note : i didn't choose the Base randomly, they need to contain a lot smalls factors and need to be the less possible 'square-Able' with quadratic residues, i wont explain what i mean now by 'squareable', because i'm not sure it is the good term.
Other sample with a not so good candidate for base (5417) to show why it could be good to work with some radix instead of other:

0001.0001 - 4679 = 0739 Facto= [1] - [4679] = [739]
0001.0004 - 4682 = 0739 Facto= [(2^2) 1] - [(2^1) 2341] = [739]
0001.0008 - 4686 = 0739 Facto= [(2^3) 1] - [(2^1) (3^1) (11^1) 71] = [739]
0001.0009 - 4687 = 0739 Facto= [(3^2) 1] - [(43^1) 109] = [739]
0001.0015 - 4693 = 0739 Facto= [(3^1) 5] - [(13^1) (19^2) 1] = [739]
0001.0016 - 4694 = 0739 Facto= [(2^4) 1] - [(2^1) 2347] = [739]
0001.0021 - 4699 = 0739 Facto= [(3^1) 7] - [(37^1) 127] = [739]
0001.0022 - 4700 = 0739 Facto= [(2^1) 11] - [(2^2) (5^2) 47] = [739]

(.............up to 1354.................)
1354 possibles solutions in base 5417

Now my Question :

Is some Math expert can tell me if it worth to 'investigate' this way to optimise some algorithm (or even to make a new algo based only with theses properties) , or i am working on something already well know ???
In the case it is already well know, can you link me on some papers or web site where this behavior is explained ?

Thank.

[ColdFury]

we often work with Base 256

No, you work in whatever base you want to use. It all goes to binary regardless of the input anyways.

[LoveCraft]

I saw some errors in my firsts equations, but the edit time had expired, so this is the new one :

N=P*Q
P and Q are primes.

XX1=-((N-1)/2)²
XX2=((N+1)/2)²
XX2-XX1=N (that's not a scoop i know)

NS = XX2-((P+Q)/2)² = XX1-((Q-P)/2)² (not a scoop i guess...)

NS =((P-1 * P+1 * Q-1 * Q+1) / 4 ) = 0 mod 144 (i hope that's more interesting)

Field144=[sqrt(XX1)/sqrt(144)]
SquareField=(Field144*144 +- Field144*y) (with y<144 for ANY N)
(XX1 % SquareField ) = (a_root)² = Square
XX1- Square = SquareField

SquareField2=(Field144*144 +- Field144*y) (with y<144 for ANY N)
(XX2 % SquareField2) = (a_root+1)² = Square2


SquareField% NS = a square-like very near to ( (P+Q)/2/144)²/144 )
I hope it is the good formule, but i did this algo a long time ago and i dont remember the details...
Thats work with ANY divisor of NS and also with XX2, so if P-1*P+1*Q-1*Q+1 is smooth, it's 'relatively' easy to find NS2.

I wrote it from memory, so it could have some error but the principle is here.

[LoveCraft]

Originally Posted by ColdFury

we often work with Base 256

No, you work in whatever base you want to use. It all goes to binary regardless of the input anyways.

Yes, sorry, i meant: I worked often in base 256.

[LoveCraft]

Well i noticed that's my First algo showed a principle, but passed much od the details, so, i put some of my source code.
(sorry, the forum trimed the indentation spaces)

(.......)

CS->Add("Factorisation Methode PowerCONVERG : ");

(.......)
ZZ X1= SqrRoot(N2);
ZZ X2=X1+1;
ZZ D2=sqr(X2)-N2;
ZZ D1=N2-sqr(X1);
ZZ C=abs(X2-D2);
ZZ DD2=D2-SqrRoot(D2)*SqrRoot(D2);
ZZ DD1=(SqrRoot(D2)+1)*(SqrRoot(D2)+1)-D2;
(.......)
base=1;
// while(base<scale)
while(base<1000000)
{
Sqrbase=sqr(base);
ZZ N2=N;
ZZ Q=to_ZZ(0);
ZZ Field;
CalcSqrt2InZZ(Field, X1,&SqrBase);
trouv=CalcDistInSqrtS(P,Q,N2,Field,(Field*Field*SqrBase),SqrBase,1000,10);

(.......)
if(trouv>0)
{
Find++;

CR->Strings[5]=("Trouve= "+AnsiString(trouv)+" scale= "+CZNU->ZZToAnsiString(scale)+" base= "+AnsiString(SqrBase));
CR->Strings[6]=("P= "+CZNU->ZZToAnsiString(P));
CR->Strings[7]=("Q= "+CZNU->ZZToAnsiString(Q));
CR->Strings[8]=("Res= "+CZNU->ZZToAnsiString((Q-P)/2));
}

}

FI CFacto::CalcSqrt2InZZ(ZZ& Field, const ZZ a,const ZZ& Base )
{
ZZ RScaleA,RScaleR;
long longa=NumBytes(a);
power(RScaleA,0x100,longa);
power(RScaleR,0x100,longa*2);
ZZ RACScaled=SqrRoot(RScaleR*Base);
Field= ((a*RScaleA)/RACScaled);
return 0;
}


FI CFacto::CalcDistInSqrtS(ZZ& Pp,ZZ& Qq,const ZZ& NC,const ZZ& R,const ZZ& PosR,const long base,long Maxit,long NumCheck)
{
ZZ Res,Mod,ModDist,DistR,Pos,RR,SqMod;
Pos=PosR;
RR=R;
bool CheckMidMid=true;
long it=1,SubIt=0,D;

ZZ X1= SqrRoot(NC);
ZZ X2=X1+1;

// Checking Square Field part 4/4
while(it<=Maxit)
{
if(Pos!=base*RR*RR) CS->Add("Erreur decalage !!!");

// Pos+=RR;
SubIt=0;
if(Pos>=NC)
{
DistR=Pos-NC;
Res=SqrRoot(DistR/base);
rem(ModDist,NC,Res+RR);
if(ModDist==0)
{
Pp=RR-Res;
Qq=RR+Res;
AfficheDiffMod(Pos,X2);
NumCheck--;
if(NumCheck<1) return it;
}
}

if(!CheckMidMid)
{
for(D=1;D<base;D++)
{
Pos+=RR;
SubIt++;
}
}
else
{
// Checking Square Field part 4/3
for(D=1;D<base;D++)
{
Pos+=RR;
SubIt++;
if(Pos>=NC)
{
DistR=Pos-NC;
Res=SqrRoot(DistR/base);
rem(ModDist,NC,RR+Res);
if(ModDist!=0) rem(ModDist,NC,RR-Res);
if(ModDist!=0) rem(ModDist,NC,RR+(Res+1));
if(ModDist!=0) rem(ModDist,NC,RR-(Res+1));
if(ModDist==0)
{
Pp=RR-Res;
Qq=RR+Res+1;

AfficheDiffMod(Pos,X2);
NumCheck--;
if(NumCheck<1)return it;
}
}
}
}

// Checking Square Field part 4/2 MID-SQUARE
Pos+=RR;
SubIt++;
if(Pos>=NC)
{
DistR=(Pos-NC);
Res=SqrRoot(DistR/base);
rem(ModDist,NC,RR-Res);
//if(ModDist!=0)rem(ModDist,RR+Res+1,NC); // No need for Mid Square Field
if(ModDist==0)
{
Pp=RR-Res;
Qq=RR+Res+1;
AfficheDiffMod(Pos,X2);
NumCheck--;
if(NumCheck<1) return it;
}
}

RR+=1;
if(!CheckMidMid)
{
for(D=1;D<base;D++)
{
Pos+=RR;
SubIt++;
}
}
else
{
// Checking Square Field part 4/4
for(D=1;D<base;D++)
{
Pos+=RR;
SubIt++;
if(Pos>=NC)
{
DistR=Pos-NC;
Res=SqrRoot(DistR/base);

rem(ModDist,NC,RR+Res);

if(ModDist!=0) rem(ModDist,NC,RR-Res);
if(ModDist!=0) rem(ModDist,NC,RR+(Res+1));
if(ModDist!=0) rem(ModDist,NC,RR-(Res+1));
if(ModDist==0)
{
Pp=RR-(Res+1);
Qq=RR+Res;
CS->Add("--------------------------");
CS->Add("Field= "+CZNU->ZZToAnsiString(RR));
CS->Add("Base= "+AnsiString(base));
CS->Add("It= "+AnsiString(it));
CS->Add("SubIt= "+AnsiString(SubIt)+" (MidMidSup)");
CS->Add("PosSubIt= "+CZNU->ZZToAnsiString(Pos));
CS->Add("Res= "+CZNU->ZZToAnsiString(Res));
AfficheDiffMod(Pos,X2);
NumCheck--;
if(NumCheck<1)
return it;
}
}
}
}

// Checking Square Field part 1/1 (Loop to start)
Pos+=RR;

it++;
// if(rem(to_ZZ(it),1)==0)CR->Text=("MinPp="+CZNU->ZZToAnsiString(RR-(Res+1))+" MaxPp="+CZNU->ZZToAnsiString(RR+Res+1));
if(rem(to_ZZ(it),1000)==0)
{
// CS->Add("MinPp= "+CZNU->ZZToAnsiString(RR-(Res+1)));
// CS->Add("MaxPp= "+CZNU->ZZToAnsiString(RR+Res+1));
}
}
// if(Maxit>0)return CalcDistInSqrtS(Pp,Qq,NC,RR,Pos,base,Maxit);
// CS->Add("MinPp= "+CZNU->ZZToAnsiString(RR-(Res+1)));
// CS->Add("MaxPp= "+CZNU->ZZToAnsiString(RR+Res+1));
Pp=RR-(Res+1);
Qq=RR+Res+1;
return 0;
}

[dsouza123]

NS=((P-1 * P+1 * Q-1 * Q+1) / 4 ) = 0 mod 144 (i hope that's more interesting)

As long as both primes P,Q are equal to or greater than 5,
it fails if either prime is 2 or 3.

Factorization of 144 is 2^4*3^2.

NS is a multiple of 144 because primes except 2 and 3
are multiples 6 +- 1 ie 5,7 11,13
so for each prime (P,Q) either it's +1 or -1 will equal a multiple of 6
which it's factorization has at least 2*3 as factors so we already have 2^2*3^2,
the other two numbers offset by 1, from both P and Q,
are even, so both have 2 as a factor a further 2^2 for the factorization,
combined gives 2^4*3^2*(rest of the factorization).

it's 'relatively' easy to find NS2.

What is NS2 ?

RR2 = ((P+Q)/2)²
RR1 = ((P-Q)/2)²

Base X : RR2 - RR1 = RSA-704

Fermat's difference of two squares, positive integer squares are
the sum of the positive odd numbers, ie 9 = 1+3+5, and RSA-704
is an odd number so it will appear in the series of positive odd
numbers, where it does the sum that first includes it is a square
and also the last sum that doesn't, the difference is RSA-704.
RR2 = ((RSA-704 + 1)/2)^2
RR1 = ((RSA-704 - 2 + 1)/2)^2

Hope this helps.

What is the purpose of your algorithm(s) ?
Is it to find the last base x digit of P, Q, RR2, RR1 ?
Does it help factor N ?

Are you using one of the big number math libraries or one of your own ?
What language is it in, C++ or maybe Java or something else ?

[LoveCraft]

Originally Posted by dsouza123

As long as both primes P,Q are equal to or greater than 5,
it fails if either prime is 2 or 3.

Factorization of 144 is 2^4*3^2.

NS is a multiple of 144 because primes except 2 and 3
are multiples 6 +- 1 ie 5,7 11,13
so for each prime (P,Q) either it's +1 or -1 will equal a multiple of 6
which it's factorization has at least 2*3 as factors so we already have 2^2*3^2,
the other two numbers offset by 1, from both P and Q,
are even, so both have 2 as a factor a further 2^2 for the factorization,
combined gives 2^4*3^2*(rest of the factorization).

Yes, i know, i used this sample because it's always right if P and Q are Prime.

What is NS2 ?

I mean't NS

What is the purpose of your algorithm(s) ?
Is it to find the last base x digit of P, Q, RR2, RR1 ?
Does it help factor N ?

Are you using one of the big number math libraries or one of your own ?
What language is it in, C++ or maybe Java or something else ?

I use C++ and the Victor shoup NTL libraries, based, i think on Lips, but it can be linked to gmp, but i wrapped some implementations for speed or convenience.

My algorithm find a factor of a number by racing through what i call "Square root field" or "Square root-like" in the sense that it is not a common root but mostly a root of some sort of polynominal, to see what i mean, look at this picture : http://projetsweb.free.fr/img/Matrice.jpg

To see the an other solution but in bigger scale :
http://projetsweb.free.fr/img/factorImage5.jpg
and
http://projetsweb.free.fr/img/Image10.jpg



And in a very very very big scale (streched and zoomed) : http://projetsweb.free.fr/img/Image7.jpg


an other scaled view : http://projetsweb.free.fr/img/Image8.jpg


An amazing Picture of the same matrix, but INVERSED: proof in image thats Fields converge in circle !!! :
http://projetsweb.free.fr/img/Image6.jpg

For this last picture, i find it hardly to find some explications, but i didn't invented it, it come from the nature of math, and maybe, from the nature of the physics, so the nature of the world. I just revealed it from a simple '2D erathosthene-like sieve'. I elapsed HOURS on it (and other similar) to finaly come to the conclusion that's finding a factor is far to be simple, but nonetheless, possible.


If you want to see other view :

http://projetsweb.free.fr/img/

[LoveCraft]

The link betwen the X radix digit properties and the first algo can, i think, be made like this:

Consider a simple algo using a Fermat algorith :
we try to look for B²-N = D² , D= (Q-P)/2 and B=(P+Q)/2
so one can start by R=Sqrt(N) and looking for (R+x)²-N
So the problem is to find x.
if one look at the possible finishing digit in base 256, he well discover that for P and Q Prime (and probably >256), there's only 4 possibles solutions for the COUPLE Sol1=(R+x)² and Sol2=(R+x)²-N. (Sometime, 8 possibles solutions, but no more).
If one go throug the x and eliminate the candidates that are not in solution (by mean that (R+x)² and (R+x)²-N don't finish by a couple solution), he realise that the x follow a 'pattern' that look like a wheeling sieve algorithm.

I did it a long time ago, and improved the thing with what i showed above, it is square root-like,It use some Polynominals in the form:
Field=some number;
SquareField=( [Sqrt(N)/Sqrt(Field)]+1 )^2 * Field
Dist=SquareField- N
Dist= x^2 * Field +y (For the first polynominal y=0)


A sample of a square field is 722 on this picture with one root of first polynominal= 19 and the field is 2
we could find in the case of the first polynominal:
Sqrt(Dist/Field)+Field and Sqrt(Dist/Field)-Field are factors of N
but the first polynominal work only if N got a least 4 factors.
So, we could go on the next polys (for this field) this way :

Start :
it=1
while(it<Field){ Dist=Dist+Field ; it++; Check dist} // First Part
Field++; it=1 ; Check Dist // Midle part
while(it<Field){ Dist=Dist+Field ; it++; Check dist} // Last Part
Go to Start.

Check dist :
look if Sqrt(Dist/Field)+SquareField/Field and SquareField/Field-Sqrt(Dist/Field) are factors of N
(we can get rid of the y because it is always<than Field)

this method is far fastest than the fermat one, especially if we know that "P is around X time Q" (in RSA, i know that Q is around 2P at max and around P at min, because P and Q have the same number of bits (base 2))
I took RSA for expample, but this algo is too slow for RSA, but not with a modified version that look for NS=(P-1*P+1*Q-1*Q+1)/4 instead of P*Q.
If NS is smooth then almost every field in the sector of NS, (N+1/2)² and (N-1/2)² will converge on NS.

Now, the link with the radix
As in the fermat Poly atop, the possibles solutions follows a pattern.
But i just realised that using a different radix for checking solution of finishing square conduce to different pattern.(i was primary thought that the patterns were the same, that's explain why i didnt checked it first)
So, with a good cycle finding algorithm, maybe one could exclude most of the solutions and reducing the set of possible candidats.