1
$\begingroup$

I am trying to compute the number of prime divisors of the order of $E_8(q)$. I am interested in the general solution, but in particular, my problem calls for $q=p^{15}$ (for prime $p$) and $q\equiv 0,1,$ or $ 4 \mod 5$, if this helps at all.

So, the order is $|E_8(q)|=q^{120}(q^{30}-1)(q^{24}-1)(q^{20}-1)(q^{18}-1)(q^{14}-1)(q^{12}-1)(q^{8}-1)(q^{2}-1)$ (ref: Wilson, The Finite Simple Groups). Is there any more efficient algorithm than the standard to factorize integers of this form? I am primarily interested in knowing the number of prime divisors, but the divisors themselves would also be very useful.

1 Answers 1

4

So, among other things, you want to know the (number of) prime factors of $p^{450}-1$ for various primes $p$. Of course the polynomial $x^{450}-1$ factors into lots of smaller pieces, but there's still an irreducible part of degree 120. I can't imagine there would be a general formula for the number of prime factors of $f(p)$ for such a polynomial $p$, nor even much chance of computing them for $p$ with more than 2 digits.

You may find some useful information in the book, Brillhart, Lehmer, Selfridge, Tuckerman, Wagstaff, Factorizations of $b^n\pm1$.

Also, I'm not certain what algorithm you refer to when you write, "the standard." The standard algorithm for factoring that kind of number is probably the Special Number Field Sieve; is that what you had in mind?

  • 0
    Yes, the special number field sieve is what I was talking about. I will look into this book and post if I come up with anything - thank you!2012-06-24