Re: Special factorization method sought

From: daniel bleichenbacher (daniel_bleichenbacher_at_yahoo.com)
Date: 06/30/05 

Date: 30 Jun 2005 10:41:23 -0700

Dave Rusin wrote:
> 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

Nope. That's too much information. You can use Fermat's method to
factor this.
I.e. look for x,y with x^2-y^2 = N=pq and use the fact that 0=p-q mod
(10^125)
to constraint the possible residue classes for x.

This gives N =
690813211106932703436330736974742561435635584587189767467538305380320622220857\
229741217686043056139217455800374092598119526558724880795485531802023255050614\
524952922474293642065329619154912668026856069438450681407641506962917791070874\
166946435905950292905549552888716084125842236067060541266621757734462223575905\
687273574099511410424381304659501247275887974857856234450269798369732813148622\
894541007452377690344100570807031112996051271145945529212099288915152425156203\
24828055912854227507525717981351 *
690813211106932703436330736974742561435635584587189767467538305380320622220857\
229741217686043056139217455800374092598119526559632269852681585809504709739738\
485231104248045693804710098188302655538010818866476054310788175542136407374106\
205605523687223946800025812242019121022573901665288968349097396414947780422731\
613987785640265674198272844134050365811754869582636140810857171369732813148622\
894541007452377690344100570807031112996051271145945529212099288915152425156203\
24828055912854227507525717981351

in basically no time.