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