mersenneforum.org > YAFU Factor 1024-bit on 2x512 bit (help)
 Register FAQ Search Today's Posts Mark Forums Read

2012-11-13, 03:35   #12
axn

Jun 2003

2·34·29 Posts

Quote:
 Originally Posted by alpertron Let N be a non-square 1024-bit number. Let $x \,=\, ceil(sqrt{N})$ From: $x^2-y^2 \,=\, N$ (1) We find: $y \,=\, round(sqrt{x^2-N})$ The factors are in this case x+y and x-y. Error calculation: $x < 2^{512}$ $x^2-N\,<\,x^2-(x-1)^2\. <\, 2x+1\, <\, 2^{513}$ $y < 2^{257}$ From (1) the error is less than $(y+1)^2-y^2\, = \,2y+1 \,< \,2^{258}$ So the first 1024-258 = 766 bits do not change.
Nice!

 2012-11-13, 06:05 #13 Ogonia   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 #include #include 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=1024-750; 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"); } it's make ----- 1-take 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 1024-bit. 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 2012-11-13 at 06:43
2012-11-13, 06:12   #14
Ogonia

Nov 2012

5 Posts

Quote:
 Originally Posted by axn Let me see if I understood you correctly. You have a target number that is 1024 bits in length. You want to find another 1024 bit number that is a product of 2 512 bit numbers, and which also matches the target number in the first 750 MSB? Did I get that right?
Yes.

2012-11-13, 06:43   #15
axn

Jun 2003

2×34×29 Posts

Quote:
 Originally Posted by Ogonia Yes.
Is there any restriction on the 512-bit 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 2012-11-13 at 07:06

 2012-11-13, 07:28 #16 Ogonia   Nov 2012 58 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 #include #include 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=1024-750; 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 2012-11-13 at 07:29
 2012-11-13, 12:29 #17 alpertron     Aug 2002 Buenos Aires, Argentina 24558 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: $y_{n+1} = \frac{y_{n}(3-xy_n^2)}{2}$ After the inverse square root is found with the correct number of digits, you have to perform a multiplication to find the square root: $\sqrt{x} = x\;\frac{1}{\sqrt{x}}$ 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 2012-11-13 at 13:03
 2012-11-13, 18:34 #18 bearnol     Sep 2005 7F16 Posts I guess what I'm suggesting is more-or-less the exact inverse of long multiplication, using recursion to consider all the possibilities at each digit-level. 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 base-10] There's also that consideration - what base best to operate in... J
2012-11-13, 21:34   #19
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

131328 Posts

Quote:
 Originally Posted by bearnol I guess what I'm suggesting is more-or-less the exact inverse of long multiplication, using recursion to consider all the possibilities at each digit-level. 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 base-10] There's also that consideration - what base best to operate in... J
I think you would end up with too many cases. Each possiblity at level n would split into >=1 possiblity at level n+1. It wouldn't surprise me if you added 2-3 each level which for a number 100 digits(base 10) long is 2.5^100=6.22e39 if the average increase is a factor of 2.5. Even if the average increase is 1.5, 1.5^100=4.07e17 which is still high.

 2012-11-14, 08:16 #20 bearnol     Sep 2005 12710 Posts Thanks for your post, henryzz. I would tend to agree with you J Last fiddled with by bearnol on 2012-11-14 at 08:18 Reason: Or should that be: thx for your post, Henry :)
2012-11-14, 14:10   #21
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2×2,861 Posts

Quote:
 Originally Posted by bearnol Thanks for your post, henryzz. I would tend to agree with you J
My dad tried a factorization algorithm along the same lines. It failed for the reasons mentioned.

 2012-11-14, 14:43 #22 bearnol     Sep 2005 127 Posts Maybe in binary?

 Similar Threads Thread Thread Starter Forum Replies Last Post Johnatan YAFU 20 2016-04-22 04:33 BotXXX Factoring 25 2015-09-02 08:27 Anyone YAFU 30 2015-09-01 13:25 R. Gerbicz Conjectures 'R Us 22 2009-12-29 20:21 retina Math 0 2007-12-09 03:30

All times are UTC. The time now is 09:12.

Mon Sep 28 09:12:10 UTC 2020 up 18 days, 6:23, 0 users, load averages: 1.47, 1.35, 1.44