 mersenneforum.org Playing with different radix
 Register FAQ Search Today's Posts Mark Forums Read 2005-11-11, 23:00   #1
LoveCraft

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:
 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.
Quote:
 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:

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

Last fiddled with by LoveCraft on 2005-11-11 at 23:11   2005-11-11, 23:28 #2 ColdFury   Aug 2002 26×5 Posts Code: 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.   2005-11-11, 23:31   #3
LoveCraft

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:
 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.   2005-11-11, 23:38   #4
LoveCraft

Nov 2005
France

616 Posts Quote:
 Originally Posted by ColdFury Code: 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.   2005-11-12, 13:53   #5
LoveCraft

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 2005-11-12 at 13:58   2005-11-12, 15:24   #6
dsouza123

Sep 2002

29616 Posts Quote:
 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).

Quote:
 it's 'relatively' easy to find NS2.
What is NS2 ?

Quote:
 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 ?   2005-11-13, 20:35   #7
LoveCraft

Nov 2005
France

2×3 Posts Quote:
 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.

Quote:
 What is NS2 ?
I mean't NS

Quote:
 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/   2005-11-14, 07:59 #8 LoveCraft   Nov 2005 France 616 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= (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

 Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post jasonp Programming 13 2013-05-16 19:11 Nick Puzzles 9 2013-02-13 17:17 Flatlander Miscellaneous Math 12 2012-11-29 09:56 joblack Lounge 20 2009-01-05 15:18 michael Puzzles 14 2004-01-17 00:15

All times are UTC. The time now is 02:59.

Tue Feb 7 02:59:08 UTC 2023 up 173 days, 27 mins, 1 user, load averages: 2.14, 1.24, 1.12