I am working on an approach to prime factorization in polynomial time using a modified AKS primality test. Do you think that the following approach will work?
-----
If a test similar to AKS for divisibility can be created, which given any w,n with w
There is no known way to turn primality testing (or composite testing) to prime factorization effectively (in poly time), so this will be really surprising. Any polynomial time prime factorization algorithm will be most surprising results (there is no lower bound that indicates this is impossible, but the mathematical knowledge nowadays leads to sub exponential algorithms far worse than polynomial time). Side comment: The only polynomial time technique for prime factorization is a "Quantum polynomial time" method of Peter Shor (Shor's algorithm) BUT: quantum computers cannot yet be built of reasonable size to be a meaningful candidate to factor numbers that have large factors in them!!! Note that an efficient prime factorization algorithm will have extremely significant effect on modern cryptography as it is practiced!!!
AKS primality is a primality test by Agrawal–Kayal–Saxena : http://en.wikipedia.org/wiki/AKS_primality_test which is proven to be find whether a number is prime or not in polynomial time. The question is not: "If a polynomial-time test for divisibility implies a polynomial-time test for primality.". AKS is such a big discovery in prime number testing that a person competent enough to answer this question will know it.
In fact polynomial time test of divisibility DOES NOT imply polynomial-time test for primality. When we refer to polynomial time test for primality for a number N the convention is to look at the size of the prime number in binary not the magnitude of the number. A prime number test for a number N in polynomial time means ability to test it in Polynomial (Log(N)).
I apologize for missing 'time' in the 'polynomial time' but "Prime factorization" is conventionally used to refer to the factorization of a composite number into prime factors. In fact there is not existing deterministic algorithm to find prime factors of a number in Polynomial time. The question for you is this:
Can the AKS algorithm for primality testing be modified to find prime factors of a composite number in Polynomial time?
Peter> Thanks for a detailed response and I agree that the question should have been more descriptive.
Actually critical part is not xn-1 = (x-1)n mod n, test but the test xn-a = ((x-a)n mod (xr – 1) )mod n, where r is of the order O(log(n)k). Using squaring and modulo multiplication ((x-a)n mod (xr – 1) )mod n can be found in O(log(n)k) time. But as the condition becomes weaker the xn-a = ((x-a)n mod (xr – 1) )mod n has to be tested for all a: 1
Hi,
The original primalty paper is attached with this message. As per my analysis it is impossible to make xn-an=(x-a)n mod q for a composite n. What I have been trying to do instead is first make a modified Fermat's little theorem of the type: b1ak1+... divisible by a number derived as K = F(w, n). The polynomial above should have terms of the order O(log(n)k). If this can be achieved we can make big discovery/invention and break RSA algorithm from pure mathematics.
The AKS paper and test is itself proven to be correct by many derivative papers. I think it is highly unlikely they will be able to modify their algo for prime factorization. A person with a fresher perspective has a better chance to do it. I think your direction may be good.
There is no known way to turn primality testing (or composite testing) to prime factorization effectively (in poly time), so this will be really surprising. Any polynomial time prime factorization algorithm will be most surprising results (there is no lower bound that indicates this is impossible, but the mathematical knowledge nowadays leads to sub exponential algorithms far worse than polynomial time). Side comment: The only polynomial time technique for prime factorization is a "Quantum polynomial time" method of Peter Shor (Shor's algorithm) BUT: quantum computers cannot yet be built of reasonable size to be a meaningful candidate to factor numbers that have large factors in them!!! Note that an efficient prime factorization algorithm will have extremely significant effect on modern cryptography as it is practiced!!!
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms