Wednesday, 12 March 2008

YAFA (c) JGW 2008

YAFA=Yet another factorization algorithm :)
I don't know whether this is any good (I _think_ it's new) - comments welcome...
Suppose we wish to factor N.
Write N=x^(2^n)-1, s.t. x=(N+1)^(2^-n)
Then N=(x-1)(x+1)(x^2+1)(x^4+1)...(x^2^(n-1)+1)
Start w/ n=1, and evaluate all the 2^n combinations of products of brackets above, testing for exact division into N as you go.
After all unsuccessful 2^n attempts, increment n, and repeat.


infamousinnocence said...

Dear James,
Does YAFA method guaranty the factorization? Would you give me an example of factoring 93?

Thank you very much.

James Wanless said...

Thanks for your comment, infamousinnocence
I don't really know = I haven't tried it (yet?).
I was hoping someone would save me the trouble of writing the code myself! :)
It's kindof only a suggestion - _might_ be a fun little experiment for someone to investigate...

Anonymous said...
This comment has been removed by a blog administrator.
Unknown said...

I've just come across your post. Any new thoughts about YAFA in the meanwhile?

Just a simple thought to the question of

If I correctly understand, x is a real number in general case.

So you can get a factor of N only if at least one of x^(2^k), 0 <= k < n, is an integer.

Since x is chosen like you proposed,

Let suppose N>3 and N+1 is a prime. Than N definitly has a non-trivial factor. That means that one of x^(2^k) with n < k is an integer.
Since p:=N+1 = x^(2^n) is prime, the only factors of p are p itself and 1. That contradicts with x^(2^k), 0 <= k< n, is an integer, since otherwise p would have a non-trivial factor.

Unless I made a mistake, YAFA doesn't find a factor in case if N > 3 and N+1 is prime.

Do you have any successful non-trivial examples?

James Wanless said...

I've posted some code (C++, needs the GMP, and GMP++, libs) over at:
I _think_ it's a correct implementation of my idea - though, as I said, I don't know how good the actual _algorithm_ is (yet?)...

Unknown said...

Thank you for your comment!

I have some remarks to your code. First of all you start your algorithm with x = N+1 although in the description of your method if n=1 x should be equal to (N+1)^(1/2) rather than N+1. As consequence, on some steps you multiply the variable term by N+2. In some cases that helps but I consider this as irregularity.
Also, you build up the variable term as product of some x^(2^j+1) but you forget x-1. As I said instead you multiple term by N+2. And the number of permutations seems to be 2^(n+1).

I slightly modified your code. I hope you don't mind. Now it performs faster apart from cases where your program gains multiplying by N+2. Is it a mistake or there is some reason why do you multiple by N+2?

But anyway it is very slow if the given number is product of two big primes. If n becomes big (perhaps more than 25), we need a quite large precision.

For me it is still unclear if the algorithm really works.
For example, if N=93 than your algorithm outputs factors 3 which is of course correct. This factor was found by n=3 and term = (x-1)*(x^2+1) where x=N^(1/2^3).
Actually, I expected that the value of (x-1)*(x^2+1) is very close to 3. But it is something like 3.145275. Looks suspicious.
If we try to factor N=1000001970000133 which is divisible by 10000019 then the program finds a factor after 22 steps. That means we tried about 2^24 numbers. If we try so many random numbers then it is likely to find a factor as well.


Unknown said...

Here is the code: