Jump to content
  • Advertisement
Sign in to follow this  
dtrainor

Integer factoring again

This topic is 4862 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Are there any algorithms which factor integers purely algebraically - no trial and error, no guessing, no probability?

Share this post


Link to post
Share on other sites
Advertisement
You can't just "write" a fast algorithm that factors an integer...that's why it's been an open problem for so long.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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 timw
there is no algorithm to do this robustly if you find one, I'm sure many number theoriests would be happy to hear it.
Observe 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.

[Edited by - dtrainor on July 27, 2005 8:20:26 AM]

Share this post


Link to post
Share on other sites
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".

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Define "algebraically deterministic".
In 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.

[Edited by - dtrainor on July 27, 2005 4:14:11 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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??

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!