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

P+1 curios

Expand Messages
  • Andrey Kulsha
    Trying to factor 134^131+131^134, I obtained: GMP-ECM 5.1-beta [powered by GMP 4.1] [P-1] Input number is
    Message 1 of 4 , May 6, 2003
    • 0 Attachment
      Trying to factor 134^131+131^134, I obtained:


      GMP-ECM 5.1-beta [powered by GMP 4.1] [P-1]
      Input number is 25865447487363725783122634349075395812340400623026024679130966646043807574550805573958725860457194408072135499668441003308474484944428943584532115942895847887759143649437935379122607964373488754857613201155063924520774277362143078736973209926360612163137002918023001 (266 digits)
      Using B1=10000000, B2=732940912, polynomial x^24, x0=2101091962
      Step 1 took 102255ms
      Step 2 took 29094ms
      ********** Factor found in step 2: 1713776305533792578182169122961
      Found probable prime factor of 31 digits: 1713776305533792578182169122961
      Composite cofactor 15092662562695062190247830140515451896766513154868853489965873041122539539760189456815505401475408896982253689154264478030985178890080361607674298468006609898425851973638515015599202280707306886386928007775058770877765909292554751405641 has 236 digits



      All is OK, because

      P-1 = 1713776305533792578182169122960 = 2*2*2*2*5*7*17*17*89*401*290827*1497107*681469339

      But then I found the same factorization among my P+1 results:


      GMP-ECM 5.1-beta [powered by GMP 4.1] [P+1]
      Input number is 25865447487363725783122634349075395812340400623026024679130966646043807574550805573958725860457194408072135499668441003308474484944428943584532115942895847887759143649437935379122607964373488754857613201155063924520774277362143078736973209926360612163137002918023001 (266 digits)
      Using B1=10000000, B2=1967819029, polynomial x^1, x0=461132087
      Step 1 took 132377ms
      Step 2 took 62497ms
      Line=1/1 Curves=2/3 B1=10000000 factors=0
      C266 Using B1=10000000, B2=1967819029, polynomial x^1, x0=1494475138
      Step 1 took 132816ms
      Step 2 took 62399ms
      [factor found by P-1]
      ********** Factor found in step 2: 1713776305533792578182169122961
      Found probable prime factor of 31 digits: 1713776305533792578182169122961
      Composite cofactor 15092662562695062190247830140515451896766513154868853489965873041122539539760189456815505401475408896982253689154264478030985178890080361607674298468006609898425851973638515015599202280707306886386928007775058770877765909292554751405641 has 236 digits
      Line=1/1 Curves=3/3 B1=10000000 factors=1
      C236 Using B1=10000000, B2=1967819029, polynomial x^1, x0=3018874033
      Step 1 took 110956ms
      Step 2 took 54854ms



      Is it normal? Using B1 = 10^7, we find the factor P with

      P+1 = 1713776305533792578182169122962 = 2*3*285629384255632096363694853827

      Andrey


      [Non-text portions of this message have been removed]
    • Andrey Kulsha
      ... Understand. I should be more attentive before asking a question, as usual... ... Thanks, Andrey
      Message 2 of 4 , May 6, 2003
      • 0 Attachment
        > The first item is in the ECM-GMP documentation. It states that you
        > need to run P+1 a total of 3 times since it has roughly a 50/50
        > chance of actually executing a P-1 instead of a P+1. I don't know the
        > math behind it, I just know what the document states.
        >
        > The second item is that if you look carefully in the ECM-GMP output,
        > you'll see a line within brackets saying that this factor was found
        > via P-1.

        Understand. I should be more attentive before asking a question, as usual...
        :-)

        Thanks,

        Andrey
      • Paul Leyland
        ... Yes, it is normal. If you don t happen upon a lucky starting number for P+1, you end up doing a (very slow) P-1. Paul
        Message 3 of 4 , May 6, 2003
        • 0 Attachment
          > Trying to factor 134^131+131^134, I obtained:
          ...
          > ********** Factor found in step 2: 1713776305533792578182169122961
          > Found probable prime factor of 31 digits:
          > 1713776305533792578182169122961

          > All is OK, because
          >
          > P-1 = 1713776305533792578182169122960 =
          > 2*2*2*2*5*7*17*17*89*401*290827*1497107*681469339
          >
          > But then I found the same factorization among my P+1 results:
          ...
          > Is it normal? Using B1 = 10^7, we find the factor P with
          >
          > P+1 = 1713776305533792578182169122962 =
          > 2*3*285629384255632096363694853827

          Yes, it is normal. If you don't happen upon a lucky starting number for P+1, you end up doing a (very slow) P-1.


          Paul
        • j_m_berg
          I made the same identical mistake myself. You have to take into account two items of information. The first item is in the ECM-GMP documentation. It states
          Message 4 of 4 , May 6, 2003
          • 0 Attachment
            I made the same identical mistake myself. You have to take into
            account two items of information.

            The first item is in the ECM-GMP documentation. It states that you
            need to run P+1 a total of 3 times since it has roughly a 50/50
            chance of actually executing a P-1 instead of a P+1. I don't know the
            math behind it, I just know what the document states.

            The second item is that if you look carefully in the ECM-GMP output,
            you'll see a line within brackets saying that this factor was found
            via P-1. (Look 4 lines into the clip below). This signifies that
            while you executed a P+1 pass, the factor was found via P-1. To
            determine if there exists a factor via P+1, you must run a total of 3
            passes of P+1 and check for a factor to be found without the P-1
            statement within the output.



            > C266 Using B1=10000000, B2=1967819029, polynomial x^1, x0=1494475138
            > Step 1 took 132816ms
            > Step 2 took 62399ms
            > [factor found by P-1]
            > ********** Factor found in step 2: 1713776305533792578182169122961
            > Found probable prime factor of 31 digits:
            1713776305533792578182169122961
            > Composite cofactor
            1509266256269506219024783014051545189676651315486885348996587304112253
            9539760189456815505401475408896982253689154264478030985178890080361607
            6742984680066098984258519736385150155992022807073068863869280077750587
            70877765909292554751405641 has 236 digits
          Your message has been successfully submitted and would be delivered to recipients shortly.