## Re: Algebraic factoring

Expand Messages
• ... There are two types of algebraic factorization for x^n-1: 1) cyclotomic algebraic factorization 2) Aurifeuillian algebraic factorization For (1), we use
Message 1 of 45 , Feb 1, 2011
Kermit Rose <kermit@...> wrote:

> I would like to program the missing algebra.

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

For (1), we use the cyclotomic polynomials,
which are obtained by Moebius transformation

Phi(n,x)=local(P=1);fordiv(n,d,P*=(x^d-1)^moebius(n/d));P;

For (2), we must have x = m*s^2 where m is odd divisor of n.
Then for odd k, we may factorize
Phi(m*k,m*s^2), if m = 1 mod 4, and
Phi(2*m*k,m*s^2), if m = 3 mod 4.

Explicit formulas for these cases may be obtained from consulting
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0812&L=NMBRTHRY&P=446
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0812&L=NMBRTHRY&P=218
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0812&L=NMBRTHRY&P=567
with some code from Phil in the third link.

If you don't mind the time that you spend on computer algebra,
simply use GP's "factor", with /algebraic/ s.

F=factor(Phi(17*3,17*s^2))[,1];print(vector(#F,k,poldegree(F[k])));

[32, 32]

F=factor(Phi(2*15*3,15*s^2))[,1];print(vector(#F,k,poldegree(F[k])));

[24, 24]

with polynomial factors that are too ornate to print here.

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