Re: Special factorization method sought

From: Dave Rusin (rusin_at_vesuvius.math.niu.edu)
Date: 06/29/05 

Date: 29 Jun 2005 15:29:17 GMT

In article <F9uwe.2990$Nb2.55928@news1.nokia.com>,
Risto Lankinen <rlankine@hotmail.com> wrote:

>A handful of specialized factorization algorithms exist for
>integers having a special structure (for instance, Mersenne
>numbers). Are there any special algorithms for factorizing
>integers that are known to have factors of "nearly the same
>size".

None known.

Here's a thousand digit number. It has two factors "nearly the
same size" in a much stronger sense than you meant: each of
the factors is 500 digits, and the first 125 digits of the two
numbers are identical! Not only that, the numbers have the
same final 125 digits! And the two factors are (probably) prime!

So that's about as "easy" a problem as you could have of this
type. Yet I suspect this number couldn't be factored in a year's time.

477222892639871569454959343999238928931199417704911468060568875604587748770367\
938198431059804546895181317383705080264413069948223904883838987760434270858845\
796329568031500759652813772979051153306789703352488768981230111569591650333241\
900270408368466134545266484245197315350854743917913294820010412799000266686088\
979739248046268009674916698665897021886071011290598200142090256189684436066317\
685402780978796555022350537993564230111300766504377369857454444123735589528869\
031865243816116846184698985441216122010428319332189366052914077397369592639805\
131816204686899895768050314519591292012932463209582702933676304738295775921147\
186525315655867693628086180601726912863432697776199095436046503723815426606177\
635529096048396859040780348683336374622027123729956888532774905443591143906549\
044410034120491635231997428695049708471097222674546536377628501781423281284253\
594516269620138993049589864816708012076941374761597672396663155544677699811462\
1626028716379404870811966752323066403164689453839829770383785201

dave