Re: (new?) factorization technique

From: Keith A. Lewis (klewis_at_OMEGA.MITRE.ORG)
Date: 05/31/05 

Date: Tue, 31 May 2005 20:19:12 +0000 (UTC)

"Dik T. Winter" <Dik.Winter@cwi.nl> writes in article <IHCtIz.LD0@cwi.nl> dated Tue, 31 May 2005 12:32:59 GMT:
>In article <tKGdnXTaJK-ebAbfRVn-oA@comcast.com> "vector" <root@localhost> writes:
> > I've written an article discussing an approach I found to finding prime
> > factorizations. I don't know if the technique is original, but I've never
> > seen it described anywhere else before. There's well-documented Java code
> > available for download that demonstrates the algorithm. I hope someone will
> > find it useful, or at least interesting.
>
>See the thread with subject "factoring integers on a classical computer in
>polynomial-time" in these newsgroups. There it is shown that such
>algorithms are not better than trial division.

But Vector's algorithm is well-suited to distributed processing, as he
points out in the blog. The total work may be the same, but it could be
farmed out to an exponentially-increasing number of computers and completed
in polynomial time.

(No, I don't have 2^100 computers.)

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.

Relevant Pages

  • Re: (new?) factorization technique
    ... > I've written an article discussing an approach I found to finding prime ... > factorizations. ... I don't know if the technique is original, ... > available for download that demonstrates the algorithm. ...
    (sci.crypt)
  • Re: (new?) factorization technique
    ... > I've written an article discussing an approach I found to finding prime ... > factorizations. ... I don't know if the technique is original, ... > available for download that demonstrates the algorithm. ...
    (sci.crypt)
  • Re: your assistance is requested
    ... I take this proof that chicks don't know shit about computers? ... Park-Miller PRNG has an even smaller range of internal states, ... and the RC5 algorithm is far more involved ... should try to publish in a crypto conference or journal. ...
    (comp.compression)
  • Re: Consciousness: whats the problem?
    ... will know all you really need to know about digital computers. ... unknown algorithm is being run. ... the idealized and actual instruction sets are well known. ...
    (comp.ai.philosophy)
  • Re: Suggestions for double-hashing scheme
    ... i.e. the multiplicative group might be of size /2 if p is ... That's what my algorithm is for. ... > factorizations of N-1, which may or may not be fast. ... mathematical proof of primeness that it constructs is understandable. ...
    (comp.programming)