14
$\begingroup$

Let $N$ be a positive integer. Thanks to the Miller-Rabin test and the work of Agrawal, Kayal and Saxena, these days people have much much faster algorithms for testing whether $N$ is prime or composite than they do for explicitly finding its factorisation.

If you stand at a sufficient distance, the key idea behind both Miller-Rabin and AKS (and every other primality test I've seen) is to work with the ring of residues modulo $N$, and use clever tricks to see whether it has the algebraic properties that it would have if $N$ were prime. Miller-Rabin looks to see if the roots of $1$ behave how Fermat says they should in that ring; AKS tries to verify a certain polynomial identity in it.

Are there any other properties of $N$'s factorisation that can be checked in less time than it takes to actually find that factorisation, using similar ideas? For example, is it reasonable to ask for an algorithm which takes a composite $N$ and says something useful about how many prime factors it has? This question is related to the number of square roots of $1$ in the residue ring, so might conceivably be effectively detectable by some devilishly clever trick. Similarly, the distribution of residue classes of the prime factors modulo small integers is closely related to the number of roots of unity of small orders.

Or is it simply the case that, once you know that the ring is not a field, you just have so little control over it that no good trickery is known?

I read on a webpage about squarefree integers that no such rapid algorithm is known which tests for repeated prime factors, but that doesn't seem to render the general question invalid (though, if nobody can suggest any positive results in this direction, it would lead us to guess that it's hard, perhaps).

$\endgroup$
6
  • 1
    $\begingroup$ It took me one minute and 40 seconds to read your question out loud. I could get faster with practice, but I do not see going below a minute. $\endgroup$
    – Will Jagy
    Aug 5, 2012 at 20:52
  • $\begingroup$ Scott's answer took just 52 seconds. $\endgroup$
    – Will Jagy
    Aug 5, 2012 at 20:59
  • 1
    $\begingroup$ Surely this is to be expected, given that he's educating me about the subject described in the question title? $\endgroup$ Aug 5, 2012 at 21:18
  • 1
    $\begingroup$ One can rapidly decide the parity of the number (counting with multiplicity) of prime factors of $N$ that are 1 less than a multiple of 3. Ditto, 1 less than a multiple of 4. $\endgroup$ Aug 5, 2012 at 22:42
  • 1
    $\begingroup$ Will, the system collapses multiple edits into one if done quickly enough. I bet it took Scott a full 2 minutes and 30 seconds to read and reply. Gerhard "Ask Me About Speed Trials" Paseman, 2012.08.05 $\endgroup$ Aug 6, 2012 at 0:11

2 Answers 2

8
$\begingroup$

An expert on computational number theory will be able to provide much, much more detail than I can, but the short answer is that as far as anyone knows, primality-testing is the rare exception, and almost all of these problems are hard (for a classical computer)! That is, the detailed properties of the prime factorization, like whether there are more than two prime factors, whether there's a repeated factor, etc., are not known to be in P and are generally believed to have the same order of difficulty as factoring itself (even where explicit reductions aren't known, as in most cases they aren't). For more details, you might start with the book Algorithmic Number Theory by Bach and Shallit.

(Note: There are, of course, a few easy ones, like testing whether N is a prime power! But I wonder if there's some general conjecture to the effect that no property of the prime factorization is in P, unless the property is "degenerate" in such-and-such a sense.)

$\endgroup$
2
  • $\begingroup$ I think I've let that brew for long enough to accept it now. $\endgroup$ Aug 14, 2012 at 0:34
  • $\begingroup$ Finding the value of "such-and-such" seems very hard. $\endgroup$
    – Charles
    Feb 1, 2013 at 15:51
10
$\begingroup$

While the method used is not related to the work you mention in the question, there is recent work of Andrew Booker, Ghaith Hiary and Jon Keating where they develop an algorithm for determining a non trival lower bound (assuming GRH) for the square free part of the number $N$, i.e. if
$$ N=\Delta m^2, $$ where $\Delta$ is square free they obtain a lower bound for $\log \Delta$, by using the Weil explicit formula for certain $L$-functions associated to $N$. I do not find the relevant paper (in progress?), but there is a slide on Hiary's homepage http://www.maths.bristol.ac.uk/~maxgh/ from a talk he has given on the topic (that I attended). In particular they manage to show that assuming the Riemann hypothesis for the relevant Dirichlet L-functions, RSA-210 is not square-full (there exists at least one prime factor in the factorization of RSA-210 that occurs just once), a number that has yet to be factored, so for example it can not be of the form $p^2q^3$. Of course it is likely to be a product of just two prime factors, but we do not yet have a proof of that.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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