Given a composite or prime number N, can we make a polynomial time test to check whether any number below a number W divides N?
Hi Peter,
If W is of the order O(N) then the total ops you suggest are in the order O(N log(N)).
If indeed we can device a test which can test whether W or any number below divides N in the order O(log(N)^k then we can use it to binary search for factors, which means we can prime factorize in polynomial ( log(N)). I conjecture that a test like AKS primality test can be made but I am not yet able to make it. Any ideas?
Actually W need not be larger that Sqrt(N) because unless a number at or below Sqrt(N) divides N, nothing bigger can. It is still O(N).
The case W=N is primality testing which is in P by AKS. Now being in P does not mean O(log(N)) but O(poly(log(N)) . So you are asking for an improvement of AKS. Sorry if I am missing something basic.
- Badges
- Science topic
- Similar topics
- Physical Sciences
- Materials Science
- Materials
- Composites