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

Re: Algebraic factoring

Expand Messages
  • djbroadhurst
    ... There is also an algebraic (composite) factor of 16^137-1 that has 165 (i.e. more than 83) digits, namely (16^137-1)/(2^2-1). In your first posting on this
    Message 1 of 45 , Feb 2, 2011
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "Jane Sullivan" <janesullivan@...> wrote:

      > there is an algebraic (composite) factor of
      > 16^137-1 that has 83 (i.e. more than 42) digits.

      There is also an algebraic (composite) factor of
      16^137-1 that has 165 (i.e. more than 83) digits,
      namely (16^137-1)/(2^2-1).

      In your first posting on this subject
      http://tech.groups.yahoo.com/group/primenumbers/message/22507
      you courteously acknowledged my hints
      (which I had hoped would resolve any ambiguity):

      > 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.
      > The largest, f6, has 42 digits, yet may be written in 7 characters.
      > The next-to-largest, f5, may be written in 12 characters.

      In that sense, the answer is 42.

      In a more general sense, there are 62 non-unit proper
      algebraic divisors ranging from 2^2-1 to (16^137-1)/(2^2-1),
      with the following digit-counts:

      f1 = 2^2-1;
      f2 = 2^2+1;
      f3 = (2^137+2^69+1)/(2^2+1);
      f4 = (2^137+1)/(2+1);
      f5 = 2^137-2^69+1;
      f6 = 2^137-1;
      F = [f1,f2,f3,f4,f5,f6];
      V = vector(165);
      for(k=1,62,V[#Str(prod(j=1,6,F[j]^binary(64+k)[j+1]))]++);
      for(i=1,165,if(V[i],print(i"-digit algebraic divisors: "V[i])));

      1-digit algebraic divisors: 2
      2-digit algebraic divisors: 1
      41-digit algebraic divisors: 2
      42-digit algebraic divisors: 12
      43-digit algebraic divisors: 2
      82-digit algebraic divisors: 4
      83-digit algebraic divisors: 16
      84-digit algebraic divisors: 4
      123-digit algebraic divisors: 2
      124-digit algebraic divisors: 12
      125-digit algebraic divisors: 2
      164-digit algebraic divisors: 1
      165-digit algebraic divisors: 2

      Best regards

      David
    • 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
      • 0 Attachment
        --- 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.