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

RE: [PrimeNumbers] Re: Algebraic factoring

Expand Messages
  • Chris Caldwell
    ... Jane ... Looks like you missed the point (purposely?). You are to find the algebraic factors by hand, from there one could seek prime factors. This is
    Message 1 of 45 , Feb 1, 2011
      David:
      > > Hints for the exercise:
      > > The 6 non-unit /algebraic/ factors of
      > > 16^137-1 = f1*f2*f3*f4*f5*f6
      > > may be found in one's head; no need for a computer.

      Jane
      > There are twelve prime factors of 16^137-1 (=2^548-1), which are
      > 3 5 1097 15619 189061 168434085820849 32127963626435681
      > 105498212027592977 32032215596496435569 5439042183600204290159
      > 206875670104957744917147613 921525707911840587390617330886362701

      Looks like you missed the point (purposely?). You are to find the
      algebraic factors by hand, from there one could seek prime factors.
      This is great problem from David as it uses some fun identities.

      CC
    • djbroadhurst
      ... It seems that no-one spotted the Aurifeuillian method for ... As previously remarked, the trivial Ansatz (a,b) = (x^2,y^2) cannot solve Exercise 4.
      Message 45 of 45 , Feb 7, 2011
        --- In primenumbers@yahoogroups.com,
        "mikeoakes2" <mikeoakes2@...> wrote:

        > > ABC2 if($a>$b,($a^137+$b^137)/($a+$b),0) & ($a^137-$b^137)/($a-$b)
        > > a: from 216 to 262
        > > b: from 216 to 262
        > > does not give a double hit, as Mike has probably checked.
        > Your intuition is spot on, as per usual, good Sir:
        > they were pfgw jobs of precisely this form that I ran.

        It seems that no-one spotted the Aurifeuillian method for

        > Exercise 4: Find integers (a,b) with min(a,b) > 46225 and
        > N(a,b) = (a^137 - b^137)/(a - b) equal to the product of
        > two primes, each with less than 330 decimal digits.

        > Comment: This may solved, systematically, in less than
        > 30 seconds, including the time for primality proofs.

        As previously remarked, the trivial Ansatz
        (a,b) = (x^2,y^2) cannot solve Exercise 4.

        Solution: Aurifeuillian algebraic factorization results from
        (a,b) = (x^2,137*y^2), with min(x,sqrt(137)*y) > 215. Since
        max(x,sqrt(137)*y) < 10^(329/136) < 263, we have x in the
        range [216,262] and y in the range [19,22], yielding a pair
        of PRPs in 0.27 seconds and a proof in 26 seconds:

        {g=factor((z^274-137^137)/(z^2-137))[,1]~;
        for(x=216,262,for(y=19,22,if(gcd(x,y)==1,
        f=abs(y^136*subst(g,z,x/y));
        if(ispseudoprime(f[1])&&ispseudoprime(f[2]),F=f;
        print1([[x,y],[#Str(F[1]),#Str(F[2])]]" in "gettime" ms. ")))));
        if(isprime(F)==[1,1],print("Proof in "round(gettime/10^3)" sec."));}

        [[220, 21], [323, 329]] in 270 ms. Proof in 26 sec.

        Hence we have the solution N(a,b) = P323*P329,
        with (a,b) = (220^2,137*21^2) = (48400,60417).

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.