Re: Special factorization method sought

From: clem (clem_at_numeral.com)
Date: 06/29/05 

Date: Wed, 29 Jun 2005 10:16:01 -0700

On 29 Jun 2005 15:29:17 GMT, rusin@vesuvius.math.niu.edu (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

First 125 digits identical and last 125 digits identical and both
numbers are 500 digits on a 1000 digit number.

What an example. That's cool.

Relevant Pages

  • Prime Factorization and Digit Congruence
    ... of three digits as a decimal number. ... summation congruence for base b can be used as a test for the factor ... similar method for "a base that is a power of two". ... as I develop some factorization software. ...
    (sci.math)
  • Re: Elementary group theory: Proof of Fermat-Maas primality-test (was: correcting Dik ...)
    ... the known factorization of p-1 that you got when you directly ... Let n0 = random number with 80 digits, ...
    (sci.math)
  • Re: Proof 0.999... is not equal to one.
    ... Second-Now add one to the previous number,, you will get another number with COMPLETELY deferent prime factorization ... Third repeat the process for digits, and this is the principle of Induction method of the proof, where you would find that always applicable, then ... It is only by CONVENTION, ... is also one, and so on to any system number, which will lead you to many contradiction in your real life system ...
    (sci.math)
  • Re: factorization
    ... Douglas A. Gwyn wrote: ... this fact can possibly lead to a factorization in polynomial time or ... and high-order digits ...
    (sci.crypt)
  • Re: Special factorization method sought
    ... Dave Rusin wrote: ... >>A handful of specialized factorization algorithms exist for ...
    (sci.crypt)
Loading