Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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?

share|cite|improve this answer
If I am remembering correctly, then there are no special methods for factorizing numbers of the form $p^n-1$, but such factorizations are frequently needed, so a lot of computing power has been devoted to storing them once they have been computed. The book you mention is probably the best place to look! – Derek Holt Jun 20 '12 at 9:25
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! – Alexander Gruber Jun 24 '12 at 2:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.