Sorry, an error occurred while loading the content.
Browse Groups

• ... 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
View Source
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
View Source
"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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.