Integer Factorization 2

[mgb]

By Fermat's factorization method we have

X² - Y² = pq = n. Y = (p - q) / 2

Consider the fraction p/q. Since gcd(p, q) = 1 integers x and y exist such that,

py - qx = 1.

If we can find x and y such that

x/y ~ p/q we have, by the theory of linear congruences, (py - qx)/2 = e, a small number.

We can arbitrairly choose e and find x and y.

So, instead of factorizing pq we can more easily factor pqxy.

Example;

pq = 2003 x 4001. y = 999.

but (761 x 2003)(381 x 4001) = 1524383 x 1524381

in this case y = (1524383 - 1524381) / 2 = 1, which is easily found by trial and error.

so a multiple of n can be easier to factor. The problem is obvious, we don't know x and y.

But we can produce P = p₁p₂...p_k where these p's are odd primes.

Let x_jy_j = P. There will be many such factorizations but one will more closely approximate

p/q than the others. Call this pair x_i and y_i such that

x_i/y_i ~ p/q. So, we try to factor Ppq instead.

We now have Y = (qx_i - py_i) / 2.

The larger P is the more choices of x_i and y_i we have.

We can force the issue if we make P immensly large in which case we are guarenteed to find a suitable

x_i and y_i. The only objection to this is that we must work with immense integers, but we are

guarenteed of finding Y very quickly. Any comments?

[R.D. Silverman]

Originally Posted by mgb

By Fermat's factorization method we have

X² - Y² = pq = n. Y = (p - q) / 2

Consider the fraction p/q. Since gcd(p, q) = 1 integers x and y exist such that,

py - qx = 1.

If we can find x and y such that

x/y ~ p/q we have, by the theory of linear congruences, (py - qx)/2 = e, a small number.

We can arbitrairly choose e and find x and y.

So, instead of factorizing pq we can more easily factor pqxy.

Example;

pq = 2003 x 4001. y = 999.

but (761 x 2003)(381 x 4001) = 1524383 x 1524381

in this case y = (1524383 - 1524381) / 2 = 1, which is easily found by trial and error.

so a multiple of n can be easier to factor. The problem is obvious, we don't know x and y.

But we can produce P = p₁p₂...p_k where these p's are odd primes.

Let x_jy_j = P. There will be many such factorizations but one will more closely approximate

p/q than the others. Call this pair x_i and y_i such that

x_i/y_i ~ p/q. So, we try to factor Ppq instead.

We now have Y = (qx_i - py_i) / 2.

The larger P is the more choices of x_i and y_i we have.

We can force the issue if we make P immensly large in which case we are guarenteed to find a suitable

x_i and y_i. The only objection to this is that we must work with immense integers, but we are

guarenteed of finding Y very quickly. Any comments?

Once more, someone reinvents the wheel.

This is well known. Look up Lehman's Algorithm.

[xilman]

Originally Posted by R.D. Silverman

This is well known.

It was known by Fermat.

Exercise: Re-discover which which N was factored by Fermat himself by factoring 8N.


Paul

[fenderbender]

Originally Posted by mgb

The larger P is the more choices of x_i and y_i we have.

We can force the issue if we make P immensly large in which case we are guarenteed to find a suitable
x_i and y_i. The only objection to this is that we must work with immense integers, but we are guarenteed of finding Y very quickly.

The flaw is in these last assumptions. Yes, the large multiplier starts giving you multiple different "splits" and the big product can be factored into a closer-to-a-square set of factors. But the bonus of having the multiple split options is offset much more rapidly by the larger value to factor, so the search will still end up being slower.


Lehman optimized the idea as a "booster" to Fermat. His algorithm starts a Fermat factorization, but then after enough (failed) tests, it adds a multiplier to keep the effective rate as fast as possible. This reduces the factoring complexity of factoring from Fermat's O(n^(1/2)) to O(n^(1/3)).
See R. Lehman, "Factoring Large Integers", Mathematics of Computation, 28:637-646, 1974.

[mgb]

Thanks for your lucid reply fenderbender. My question was which devil is easiest to contend with; Trial and Error or Magnitude? I did not know this had been explored before. Perhaps it could be developed?

[R.D. Silverman]

Originally Posted by mgb

Thanks for your lucid reply fenderbender. My question was which devil is easiest to contend with; Trial and Error or Magnitude? I did not know this had been explored before. Perhaps it could be developed?

Perhaps you might do some reading about the subject???

It has *already* been developed. It is a purely exponential time
method and is not competitive with either ECM or index-calculus
methods.