Loading ...
Sorry, an error occurred while loading the content.
 

Re: [PrimeNumbers] RE:[Factoring large numbers

Expand Messages
  • Paul Leyland
    ... In that case, it is almost certainly too hard to factor with present-day hardware and software. The values of a and b ma just be such that a
    Message 1 of 8 , Jul 13, 2004
      On Tue, 2004-07-13 at 09:20, cino hilliard wrote:

      > The pari program below produces primes. I produced primes for
      > digitsqrpr(2000,m,150) and digitsqrpr(2000,m,200) and randomly selected a
      > prime from each a,b
      > output and multiplied them. I forgot what m I used or if it was the same for
      > both or different as
      > I did p = a*b and a prime() and then factor(p) and had to abort the
      > session. I had copied p earlier
      > to text to test for primality with another program which worked faster tham
      > Pari. all I know is
      > a is <= 150 digits and b is <=200 digits.

      In that case, it is almost certainly too hard to factor with present-day
      hardware and software. The values of a and b ma just be such that a
      special-purpose algorithm such as P-1 may find them but the odds are
      very much against it.

      Almost certainly the easiest way to find the factors would be to
      reverse-engineer the pseudorandom procedure used to generate the primes
      in the first place.


      Paul
    • cino hilliard
      ... I did this and found the org number was copied and pasted wrong and was easy to factor as was pointed out by other posters. I did not set the limit in
      Message 2 of 8 , Jul 13, 2004
        >From: Paul Leyland <pcl@...>
        >Reply-To: pcl@...
        >To: cino hilliard <hillcino368@...>
        >CC: primenumbers@yahoogroups.com
        >Subject: Re: [PrimeNumbers] RE:[Factoring large numbers
        >Date: 13 Jul 2004 10:38:32 +0100
        >
        >On Tue, 2004-07-13 at 09:20, cino hilliard wrote:
        >
        > > Pari. all I know is
        > > a is <= 150 digits and b is <=200 digits.
        >
        >In that case, it is almost certainly too hard to factor with present-day
        >hardware and software. The values of a and b ma just be such that a
        >special-purpose algorithm such as P-1 may find them but the odds are
        >very much against it.
        >
        >Almost certainly the easiest way to find the factors would be to
        >reverse-engineer the pseudorandom procedure used to generate the primes
        >in the first place.
        >
        I did this and found the org number was copied and pasted wrong and was easy
        to factor as was
        pointed out by other posters. I did not set the limit in factor(n,{lim}) in
        pari. Doing this
        (14:56) gp > factor(p,1000)
        time = 0 ms.
        %25 =
        [13 1]

        [199 1]

        [263 1]

        [379 1]

        [678026493414538148553665596445813830734630833053024846216579340872093413327647
        4762803097949211213281819670661292330131124527435326156088028931580262368994401
        6643351267973947046046313935094275418438526691021308861240797797863806746646690
        8508141216855178178499487049221885287729920843955819202763969676507087051775192
        055290647644770812521271 1]

        So this mistake finds yet another large factor! I will play the lotto from
        this list. :-)


        The correct number I should have posted is

        1220516103632118734239552093546852845556567859549464947942804246975191952318939
        5382087627014892247240874902346477975756822244476470920475366468143120795553304
        9000712508365396500993156592586695125254256067267320061792206044621345381741861
        7266932089747110235311534348244823636951507811274424010127339017948672442184669
        1782447097625239591063539221131129

        One poster claims to factor 150,000 digit numbers. Here is a 350 digit
        number. I do not see it any
        different than the RSA challenges in this category. We will see.

        So far, I and only I know the two factors. Gee, I don't know if I can handle
        that much power :-)

        Have fun,
        CLH
      • julienbenney
        I have been curious about trying to factor large numbers and on public computers (my home computer is FAR too old!) I have not been able to factor any number
        Message 3 of 8 , Jul 14, 2004
          I have been curious about trying to factor large numbers and on public
          computers (my home computer is FAR too old!) I have not been able to
          factor any number with more than 50 digits, whilst modern software can
          usually find factors up to 40 or 45 digits (I found this when I saw how
          dismal the prospects for fully factoring F12 [2^4096+1] in the near
          future really are).

          What sort of number would this new factoring method work upon? If it
          could only work on a 150 digit number, it would be of little use for
          factoring such numbers as Cunningham numbers.
        • Jay Berg
          ... digit ... Try running a few ECM curves on F20 (20th Fermat Number) and you ll be attempting to factor a 315,653 digit number. Factoring of 150k digit
          Message 4 of 8 , Jul 14, 2004
            --- In primenumbers@yahoogroups.com, "cino hilliard"
            <hillcino368@h...> wrote:
            >
            > One poster claims to factor 150,000 digit numbers. Here is a 350
            digit
            > number. I do not see it any
            > different than the RSA challenges in this category. We will see.


            Try running a few ECM curves on F20 (20th Fermat Number) and you'll
            be attempting to factor a 315,653 digit number. Factoring of 150k
            digit numbers is nothing new in the 21st Century. :)

            As to the RSA comparison... When you're willing to put up $20k in
            prize money, I suspect you'll get people trying to factor your
            number. But if you do, make certain to post a reasonable challenge
            and/or a reasonable reward. The next RSA challenge (RSA-640, $20k
            prize) is only 193 digits with factors estimated at 85-88 digits.
            While the RSA-1024 challenge is 309-digits with a $100k prize. So I
            figure you'll need about $250k as a prize to get anyone to take your
            challenge very seriously.
          Your message has been successfully submitted and would be delivered to recipients shortly.