Re: Special factorization method sought

From: Pubkeybreaker (Robert_silverman_at_raytheon.com)
Date: 06/29/05 

Date: 29 Jun 2005 07:23:29 -0700

> It is called the General Number Field Sieve.

> This is the best that is known.

Even for integers having "nearly equal size" factors?

*Especially* for numbers having nearly equal size factors.
For other numbers, ECM is available.

Unless of course, the numbers are *so* extremely close that difference
of
squares can be used. However, for even moderately large N, if N =
A*B
and the size of A and B differs by only 1 bit, then this method is
useless.
Its run time will be O( (A+B)/2 - SQRT(N)). But you specified x >
y > x/2
and this is not close enough in general.

For example. Suppose N is only 100 digits. A and B are both 50
digits.
A and B match to their first 5 significant digits. Say A ~ 5.43217 x
10^45 and
B ~ 5.43211 x 10^45. Then the work to split them by difference of
squares
is about 10^39. i.e. hopeless. And these are very close together.
Even if
A and B match to (say) the first 9 or 10 digits, the work will be
prohibitive.

Relevant Pages

  • Re: linalg[leastsqrs] in Maple V R4
    ... I have decided to write my own leastsqrs routine using linalg ... which seems to be a bit more consistent. ... the least squares solution is ... close, at least in the first few digits, to the linalg ...
    (sci.math.symbolic)
  • Re: SMSU Problem Corner (oops!)
    ... The only 4-digit squares with the same first and last digits ... and 5-digits triangular numbers with the same first and last digits ... None of the second squares with the second-highest digit matching ...
    (sci.math)
  • Re: Sudoku
    ... this variation seems to be relatively new. ... in each of the squares. ... sets of possible digits per box in partial solutions. ... The preferred oriental way of solving is to use a 3 by 3 dot array in ...
    (alt.lang.asm)
  • Re: what is the best method to check if a number is a perfect square or not??
    ... digits)/(number of digits that squares end in) tends towards ... Your conjecture is correct, if the base tends towards infinity along ... Walter D. Stangl, Counting squares in Z_n, Math. ...
    (comp.theory)
  • Re: Special factorization method sought
    ... with 250 unknown digits for p and q, ... which means sqrtdiffers from x by no ... But the previous poster (daniel bleichenbacher) noted that since ... There's no published algorithm which can quickly factor every N ...
    (sci.crypt)