Re: The factoring problem

From: Tom St Denis (tomstdenis_at_gmail.com)
Date: 07/12/05 

Date: 12 Jul 2005 10:17:42 -0700

ToddSmith wrote:
> I think it is basically because our number system can be derived from
> set theory, which means it's all based on counting elements,
>
> {}, #=0
> {{}}, #=1
> { {{}}, {} } #=2
> ...
>
> and that's why addition and subtract are so easy and two-way. But
> multiplication is an algorithm invented by man. Even though it has
> natural and common sense interpretation in the real world, it's just an
> algorithm mathematically and so basically you're trying to reverse
> engineer that algorithm.

I wouldn't say that's why it's hard. All known solutions for factoring
reduce it to another [equivalent] problem. Rho is cycle finding, QS
and NFS are square root finders.

The problem really isn't that we don't know how to factor, we do. It's
that we don't know what else factoring is equivalent to [that may be
faster to solve]. That may sound like saying "we don't know how to
factor" but that's not true.

For example, the goal of QS is not to factor pq. The goal is to find
square roots modulo pq. In turn, that information can be used to
factor.

If you gave me the square roots of "x" modulo pq I could trivially
factor. Similarly if you gave me phi(pq) [iirc] you can factor easily.
 etc, etc, etc. The trick now becomes of any subset of information
required to factor what is that equivalent to on its own.

While I'm no authority on the subject I suspect future factoring
algorithms will follow this trend and just be "more puzzles" that lead
to finding information we can use to factor.

For example [just random idea] there may be a way to accelerate Rho
factoring so instead of starting at x1 = 1, x2 = 1 and then doing the
step/double step you actually start at x1 = a, x2 = b where <a,b> are
generated by some other algorithm based on pq. The resulting vector
would lead you closer to the cycle and make factoring possible.

That's just a random example but certainly within the realm of
possible.

Tom

Relevant Pages

  • beta version of Victor Shoups book, "A Computational Introduction to Number Theory and Algebra&
    ... Computing with Large Integers ... The Basic Euclidean Algorithm ... Factoring and Computing Euler's phi-Function are Equivalent ... The Existence of Finite Fields ...
    (sci.crypt)
  • Re: Ultimate check, new way to factor or not?
    ... It's commonly known as a the "factoring sieve" and Fermat showed that ... It is listed as "algorithm ... "factoring with sieves" on pp.389. ... > when it defies the mathematics. ...
    (sci.crypt)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.crypt)
  • Re: More math stuff, truth and social reality
    ... > out that I use brainstorming, where you generate lots of ideas during ... fast as other efficient factoring algorithms. ... I don't see evidence of lying, ... algorithm) is in fact the truth. ...
    (sci.math)