mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2012-11-13, 03:35   #12
axn
 
axn's Avatar
 
Jun 2003

22·3·389 Posts
Default

Quote:
Originally Posted by alpertron View Post
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!
axn is offline   Reply With Quote
Old 2012-11-13, 06:05   #13
Ogonia
 
Nov 2012

516 Posts
Default

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=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
Ogonia is offline   Reply With Quote
Old 2012-11-13, 06:12   #14
Ogonia
 
Nov 2012

5 Posts
Default

Quote:
Originally Posted by axn View Post
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.
Ogonia is offline   Reply With Quote
Old 2012-11-13, 06:43   #15
axn
 
axn's Avatar
 
Jun 2003

466810 Posts
Default

Quote:
Originally Posted by Ogonia View Post
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
axn is offline   Reply With Quote
Old 2012-11-13, 07:28   #16
Ogonia
 
Nov 2012

5 Posts
Default

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=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
Ogonia is offline   Reply With Quote
Old 2012-11-13, 12:29   #17
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101001010002 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2012-11-13, 18:34   #18
bearnol
 
bearnol's Avatar
 
Sep 2005

11111112 Posts
Default

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
bearnol is offline   Reply With Quote
Old 2012-11-13, 21:34   #19
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

2·3·13·73 Posts
Default

Quote:
Originally Posted by bearnol View Post
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.
henryzz is online now   Reply With Quote
Old 2012-11-14, 08:16   #20
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

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 :)
bearnol is offline   Reply With Quote
Old 2012-11-14, 14:10   #21
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

2×3×13×73 Posts
Default

Quote:
Originally Posted by bearnol View Post
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.
henryzz is online now   Reply With Quote
Old 2012-11-14, 14:43   #22
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

Maybe in binary?
bearnol is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 11:25.

Sun Aug 9 11:25:28 UTC 2020 up 23 days, 7:12, 2 users, load averages: 1.49, 1.84, 1.86

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.