20121113, 03:35  #12 
Jun 2003
2^{2}×5×239 Posts 

20121113, 06:05  #13 
Nov 2012
5 Posts 
I wrote program on visual c++. used mpir library.
Code:
typedef unsigned __int32 word32; typedef unsigned __int64 word64; typedef unsigned __int16 word16; typedef unsigned __int8 byte; #include <stdio.h> #include <mpir.h> #include <time.h> typedef unsigned __int32 word32; typedef unsigned __int64 word64; typedef unsigned __int16 word16; typedef unsigned __int8 byte; void main() { FILE *f1; f1=fopen("out.txt","w"); //Ввод char* N="2FaF0800"; char* MaxY="FFFF"; int shift=12; //char* N="AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";//256 //char* MaxY="FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF";//128 //int shift=1024750; int end=0; //int count=0; mpz_t X, Y, Result, CMP, mpz_maxy, mpz_N; mpz_init(X); mpz_init(Y); mpz_init(Result); mpz_init(CMP); mpz_init_set_str(mpz_maxy, MaxY,16); mpz_init_set_str(mpz_N, N, 16); mpz_fdiv_q_2exp(CMP, mpz_N, shift); mpz_sqrt(X, mpz_N); mpz_set(Y, X); do { //printf("."); mpz_mul(Result, X, Y); mpz_fdiv_q_2exp(Result, Result, shift); if (0==mpz_Y(Result, CMP)) { fprintf(f1,"\nA = "); mpz_out_str(f1,10,X); fprintf(f1,"\nB = "); mpz_out_str(f1,10,Y); fprintf(f1,"\nResult = "); mpz_mul(Result, X, Y); mpz_out_str(f1,10,Result); //mpz_sub_ui(X, X, 1); mpz_add_ui(Y,Y,1); //printf("%d ",count++); } else if (mpz_Y(Result, CMP)>0) mpz_sub_ui(X, X, 1); else mpz_add_ui(Y, Y, 1); if(0==mpz_Y(Y,mpz_maxy)) end++; }while (end<1); fclose(f1); printf("done"); } 1take 1024 bit integer N find sqrt(n)=x=y y++ x*y shift right compare with 1024 bit shifted right if compare is true y++ else if compare is less then 1024 bit y++ else x output digit pairs when find.... end when y > maxy p.s. it works great for small integers (<150 bit) but it works too long for 1024bit. Maybe use some "sieve" for x and y? or something else? I generated x and y and compare first 750 bits, but it's "awfull". Last fiddled with by Ogonia on 20121113 at 06:43 
20121113, 06:12  #14 
Nov 2012
5 Posts 

20121113, 06:43  #15 
Jun 2003
2^{2}·5·239 Posts 
Is there any restriction on the 512bit factors (like they be prime or odd or something)? If not, see aplertron's post (#10). It gives a simple constructive way to get what you want.
EDIT: You can start from sqrt(N) and go upwards to search for even better matches. Last fiddled with by axn on 20121113 at 07:06 
20121113, 07:28  #16 
Nov 2012
5_{16} Posts 
there are errors in program.
right verison Code:
typedef unsigned __int32 word32; typedef unsigned __int64 word64; typedef unsigned __int16 word16; typedef unsigned __int8 byte; #include <stdio.h> #include <mpir.h> #include <time.h> typedef unsigned __int32 word32; typedef unsigned __int64 word64; typedef unsigned __int16 word16; typedef unsigned __int8 byte; void main() { FILE *f1; f1=fopen("out.txt","w"); //Ввод char* N="AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";//256 char* MaxY="FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF";//128 int shift=1024750; int end=0; //int count=0; mpz_t X, Y, Result, CMPR, mpz_maxy, mpz_N; mpz_init(X); mpz_init(Y); mpz_init(Result); mpz_init(CMPR); mpz_init_set_str(mpz_maxy, MaxY,16); mpz_init_set_str(mpz_N, N, 16); mpz_fdiv_q_2exp(CMPR, mpz_N, shift); mpz_sqrt(X, mpz_N); mpz_set(Y, X); do { //printf("."); mpz_mul(Result, X, Y); mpz_fdiv_q_2exp(Result, Result, shift); if (0==mpz_cmp(Result, CMPR)) { fprintf(f1,"\nA = "); mpz_out_str(f1,10,X); fprintf(f1,"\nB = "); mpz_out_str(f1,10,Y); fprintf(f1,"\nResult = "); mpz_mul(Result, X, Y); mpz_out_str(f1,10,Result); //mpz_sub_ui(X, X, 1); mpz_add_ui(Y,Y,1); //printf("%d ",count++); } else if (mpz_cmp(Result, CMPR)>0) mpz_sub_ui(X, X, 1); else mpz_add_ui(Y, Y, 1); if(0==mpz_cmp(Y,mpz_maxy)) end++; }while (end<1); fclose(f1); printf("done"); } Last fiddled with by Ogonia on 20121113 at 07:29 
20121113, 12:29  #17 
Aug 2002
Buenos Aires, Argentina
3·5·89 Posts 
I do not know MPIR programming, but square roots should be executed immediately for arguments less than 10000 digits in any modern computer by computing the inverse of the square root using Newton's method with multiplications only, duplicating the precision in each step. In this way, the cost of the inverse square root is about the same than three multiplications, except if you are using FFT for extremely long numbers, in this case the time would be less than 6 multiplications. A small optimization can be realized if the square can be computed faster than a standard multiplication.
The Newton algorithm for approximating the inverse square root of x is: After the inverse square root is found with the correct number of digits, you have to perform a multiplication to find the square root: So the square root is found in the same time needed for a few multiplications. The algorithm I showed in post #10 has only two square roots and a square. Last fiddled with by alpertron on 20121113 at 13:03 
20121113, 18:34  #18 
Sep 2005
127 Posts 
I guess what I'm suggesting is moreorless the exact inverse of long multiplication, using recursion to consider all the possibilities at each digitlevel.
Don't know how feasible it would be, might end up putting too much on the stack. Though note that the divisibility rules for, eg, 2,3,5 would fall out as easy special cases. [in base10] There's also that consideration  what base best to operate in... J 
20121113, 21:34  #19  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5750_{10} Posts 
Quote:


20121114, 08:16  #20 
Sep 2005
127 Posts 
Thanks for your post, henryzz. I would tend to agree with you
J Last fiddled with by bearnol on 20121114 at 08:18 Reason: Or should that be: thx for your post, Henry :) 
20121114, 14:10  #21 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×5^{3}×23 Posts 

20121114, 14:43  #22 
Sep 2005
127 Posts 
Maybe in binary?

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
factoring special form of 1024bit RSA key  Johnatan  YAFU  20  20160422 04:33 
Factoring a 1024bit RSA with GNFS?  BotXXX  Factoring  25  20150902 08:27 
Factoring 1024bit number using Yafu  Anyone  YAFU  30  20150901 13:25 
Riesel and Sierp numbers bases <= 1024  R. Gerbicz  Conjectures 'R Us  22  20091229 20:21 
[finished] prime field ECC curves up to 1024 bits  retina  Math  0  20071209 03:30 