Factoring integers on a classical computer

From: Craig Feinstein (cafeinst_at_msn.com)
Date: 03/11/05 

Date: 11 Mar 2005 09:26:52 -0800

Is there any known algorithm which factors integers that has a better
worst-case running-time than the brute force method (of testing all
integers between 1 and sqrt(n) to see if one of them divides n)?

Note: It is known that there are methods out there which are more
practical than brute force, but these methods don't always work so well
and when they do not work so well, they run slower than the brute force
method.

Craig

Relevant Pages

  • Re: ratio approximation algorithm
    ... I'm looking for an algorithm other than brute force that ... >> will speed up the searching process. ... I'd be surprised if Monte Carlo failed to suit your needs. ... a pure brute force approach took 0.37 seconds on my laptop (1.8GHz ...
    (comp.programming)
  • Re: Bonehead basic crypto question
    ... Even if 256-bit is broken by brute force using quantum computers ... as is secure should be used. ... People might like to say "even if an algorithm is ... be conservative) and focus on eliminating shortcut attacks. ...
    (sci.crypt)
  • Re: Searching substrings in records.
    ...     for each text field in the record ... but I just can't tell the difference between the algorithm ... you introduced above and the brute force approach I described on the ... every record and perform a substring search on any of them. ...
    (comp.programming)
  • Re: Meganets "unbreakable" cryptography? Im skeptical.
    ... >been thought of and shot down endless times over the past ... There is only one algorithm that is unbreakable which is the one time ... be able to brute force almost anything. ...
    (sci.crypt)
  • Re: code to do a brute force algorithm?
    ... Howard has shown admirable restraint, but I suspect he hasn't made ... "a brute force algorithm to do *what*?" ... "brute force" means "the slow, stupid way" as opposed to "the fast, ... sorting a list of items. ...
    (microsoft.public.word.vba.general)