Factor 1024-bit on 2x512 bit (help)

[axn]

Originally Posted by alpertron

Let N be a non-square 1024-bit number.

Let

From: (1)

We find:

The factors are in this case x+y and x-y.

Error calculation:




From (1) the error is less than

So the first 1024-258 = 766 bits do not change.

Nice!

[Ogonia]

I wrote program on visual c++. used mpir library.

 
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".

[Ogonia]

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.

[axn]

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.

[Ogonia]

there are errors in program.
right verison

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");
}

[alpertron]

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.

[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

[henryzz]

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.

[bearnol]

Thanks for your post, henryzz. I would tend to agree with you
J

[henryzz]

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.

[bearnol]

Maybe in binary?