An idea for a better factorisation algorithm
- View SourceA beautiful day for all,
i tested for small values a factorisation algorithm in the adjoined field with sqrt (2)
( The advantage of the adjoined field with sqrt (2) is
that you could divide every even number s by two and
every odd number s by (f-s)/2 ) ;-)
I suppose that the algorithm could be very effectiv because you only need every time an exponentation with two, instead of increasing primes, and a gcd
Unfortunately i did not understand the mathematical background
and it would be very helpfull if someone could explain to me and the other why the algorithm is usefull.
Beside there is an open problem what to do with the numbers
which do not give a result.
I am looking for the best strategy.
let be f=p*q; p and q should be primes
1. Choose a+bA with a, b element N>0 and A=sqrt (2)
so that (a+bA)^2 = a^2+2b^2 + 2abA
2. Make an exponentation with 2 with a1+b1A=(a+bA)^2 mod f
3. There are 3 special cases which could be eliminated at first.
a) if gcd (a1, f)>1 or gcd (b1, f)>1 finish
b) if a1=0 a^2+2b^2=0
=> a^2=-2b^2 | /2 and sqrt finish ???
c) if b1=0 2ab = 0 mod f
=> gcd (a, f) > 1 or gcd (b, f)> 1 finish
4. gcd (a+2b^2, f)>1 and gcd (a-2b^2, f)>1
will give a lot of results, this is the basic idea.
5. if no factorisation is succeeded you can replace (a1, b1) by the opposite (a1*, b1*)
a) if a1 and b1 even a1*=a1/2 and b1*=b1/2
b) if a1 even and b1 odd a1*=a1/2 and b1*=(f-b1)/2
c) if a1 odd and b1 even the opposite
d) if a1 and b1 odd a1*=(f-a1)/2 and b1*=(f-b1*)
There might be an optimized stragey in which order you choose
a) - d)
i am looking for a heuristic :-)
6. Make an exponentation with 2 with a2+b2A=(a*+b*A)^2 mod f and go to 4.
This test only use exponentation with 2, no calculation of primes is needed and 4. is a very strong criteria for finding the factor of f.
Besides i am only a humble and not a proper mathematician
and hope that i could give a small part for a bigger solution.
Sorry that the explication is not so clear formulated as it should be,
but i hope the main idea will reach someone.
Nice Greetings from the primes,
which are beautifull flowers in the universe