## Re: Algebraic factoring

Expand Messages
• ... The problem was that Jane saw Aurifeullian and algebraic as being mutually exclusive adjectives. They are not. The Cunningham project uses this vocabulary:
Message 1 of 45 , Feb 2, 2011
• 0 Attachment
Paul Leyland <paul@...> wrote:

> I think you're using different vocabularies.
> In the Cunningham project, and 16^137-1 == 2,548-
> in their nomenclature, algebraic factors are
> distinguished from Aurifeuillian factors.

The problem was that Jane saw Aurifeullian and algebraic
as being mutually exclusive adjectives. They are not.

The Cunningham project uses this vocabulary:

http://www.ams.org/publications/online-books/conm22-conm22-chVII.pdf
> L,M Aurifeuillian algebraic factorization (see III C)

precisely as I did here:

> There are two types of algebraic factorization for x^n-1:
> 1) cyclotomic algebraic factorization
> 2) Aurifeuillian algebraic factorization

So at least John Brillhart, D. H. Lehmer, J. L. Selfridge,
Bryant Tuckerman, and S. S. Wagstaff, Jr agree with me,
even if Jane or Paul may not :-)

David
• ... 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
"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.