Integer factoring again
Are there any algorithms which factor integers purely algebraically - no trial and error, no guessing, no probability?
You can't just "write" a fast algorithm that factors an integer...that's why it's been an open problem for so long.
there is no algorithm to do this robustly if you find one, I'm sure many number theoriests would be happy to hear it. there is one trick you should look at numbers that are less then the square root, it is impossible for prime factors of an integer to be greater then the square root of itunless it itself is prime
Quote:Original post by dtrainor
Are there any algorithms which factor integers purely algebraically - no trial and error, no guessing, no probability?
Quote:Original post by eleusive
You can't just "write" a fast algorithm that factors an integer...that's why it's been an open problem for so long.
Quote:Original post by timwObserve that there is nothing in my original post which talks about speed - only about being algebraically deterministic. Writing an algorithm does not alter the intrinsic characteristics of the problem, it only helps to expose them.
there is no algorithm to do this robustly if you find one, I'm sure many number theoriests would be happy to hear it.
[Edited by - dtrainor on July 27, 2005 8:20:26 AM]
Quote:Original post by dtrainor
Observe that there is nothing in my original post which talks about speed - only about being algebraically deterministic.
Define "algebraically deterministic".
Quote:Original post by alvaroIn this case: Set up and solve a well defined system of equations. At the end of that process either: no solution exists, in which case the number is prime. You obtain a solution, in which case it is a non-trivial factor of a composite number. At no time do you ever "test" a value to see if works or to find the remainder.
Define "algebraically deterministic".
[Edited by - dtrainor on July 27, 2005 4:14:11 PM]
Try to factor using algebra?? What would be your unknown or X and Y? Anyways, what kind of equation can you get that doesn't turn up null or in other words 0=0??
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement