20051111, 23:00  #1  
Nov 2005
France
2·3 Posts 
Playing with different radix
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) : Quote:
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 RSA704 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 = ((PQ)/2)² in base X the third is the last digit RSA704 in base X Here are some interesting solutions. Quote:
Note : i didn't choose the Base randomly, they need to contain a lot smalls factors and need to be the less possible 'squareAble' 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: Quote:
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. Last fiddled with by LoveCraft on 20051111 at 23:11 

20051111, 23:28  #2 
Aug 2002
2^{6}×5 Posts 
Code:
we often work with Base 256 
20051111, 23:31  #3  
Nov 2005
France
2×3 Posts 
I saw some errors in my firsts equations, but the edit time had expired, so this is the new one :
Quote:


20051111, 23:38  #4  
Nov 2005
France
6_{16} Posts 
Quote:


20051112, 13:53  #5  
Nov 2005
France
2·3 Posts 
Source
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) Quote:
Last fiddled with by LoveCraft on 20051112 at 13:58 

20051112, 15:24  #6  
Sep 2002
296_{16} Posts 
Quote:
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). Quote:
Quote:
the sum of the positive odd numbers, ie 9 = 1+3+5, and RSA704 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 RSA704. RR2 = ((RSA704 + 1)/2)^2 RR1 = ((RSA704  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 ? 

20051113, 20:35  #7  
Nov 2005
France
2×3 Posts 
Quote:
Quote:
Quote:
My algorithm find a factor of a number by racing through what i call "Square root field" or "Square rootlike" 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 erathosthenelike 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/ 

20051114, 07:59  #8 
Nov 2005
France
6_{16} Posts 
The link betwen the first algo and the radix
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= (QP)/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 rootlike,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/FieldSqrt(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=(P1*P+1*Q1*Q+1)/4 instead of P*Q. If NS is smooth then almost every field in the sector of NS, (N+1/2)² and (N1/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. Last fiddled with by LoveCraft on 20051114 at 08:11 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
strange problem: efficient 'radix sums'  jasonp  Programming  13  20130516 19:11 
Playing with decimal representation  Nick  Puzzles  9  20130213 17:17 
Playing with WolframAlpha and musing.  Flatlander  Miscellaneous Math  12  20121129 09:56 
Searching for m. primes is like playing lottery  joblack  Lounge  20  20090105 15:18 
playing with numbers  michael  Puzzles  14  20040117 00:15 