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.

## Wednesday 12 March 2008

Subscribe to:
Post Comments (Atom)

## 7 comments:

Dear James,

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

Thank you very much.

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

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

Just a simple thought to the question of

infamousinnocence.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,

N+1=x^(2^n)

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?

I've posted some code (C++, needs the GMP, and GMP++, libs) over at:

http://bearnol.googlepages.com/yafa1.cpp

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?)...

J

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.

wils0n

Here is the code:

http://rapidshare.com/files/

172171402/yafa2.cpp.html

Post a Comment