5
$\begingroup$

If $N-1$ could be factored easily with several small prime factors, then what is the fastest way to check $N$ for primality?

Updated

I'm aware of Pocklington primility test which is not good for small factors. I'm looking for a reduction in modular exponentitation when $N-1$ has several small factors.

  • 1
    Are you familiar with the Pocklington test, http://en.wikipedia.org/wiki/Pocklington_primality_test ?2012-12-03
  • 0
    It is not fast, since finally it requires modular exponentiation with $N-1$ in exponent, which requires the same time of Fermat Little Theorem PRP test.2012-12-03
  • 1
    The pocklington test relies on the fact that $N-1$ is divisible by some relatively large prime, which doesn't seem to be the case.2012-12-03
  • 0
    @Mohsen: Yes, that is correct (more or less). But it gives you a certain answer, not a probabilistic one. So if you do know the factors of $N−1$ for some reason, this is the test that you should use.2012-12-03
  • 1
    @Arthur: See the section "Generalized Pocklington method" in the [Pocklington Test Wikipedia article](http://en.wikipedia.org/wiki/Pocklington_primality_test). This removes youe restriction.2012-12-03
  • 0
    Anyway, the modular exponentiation shouldn't be too hard since you know the factors of $N-1$. Just raise $a$ to the power of each one in turn, that should drastically lower the calculation time needed.2012-12-03
  • 1
    @Arthur: You should do these exponentiation in parallel, to save even more time. I don't mean using multiple processors, I mean exponentiating them all at once by incorporating the successive square only in those results that have the appropriate bit set. (If you are familiar with square-and-multiply exponentiation, this might make some sense!)2012-12-03
  • 0
    @Arthur, you mean that if $N-1 = A*B$, then $a^(N-1) mod N \equiv (a^A mod N)*(a^B mod N) mod N$2012-12-03
  • 0
    @MohsenAfshin No, I mean that $a^{AB} = (a^A)^B$, modulo or not.2012-12-03
  • 0
    @Arthur, once I calculated $a^A$, can I reduce it $mod N$ then raise to $B$ ?2012-12-03
  • 0
    @TonyK can you please explain more. The modular exponentiation can't be parallelized. How do you mean? I was already working on parallel modular exponentiation http://mathematica.stackexchange.com/questions/15062/parallel-powermod and your note seems very interesting2012-12-03
  • 0
    @MohsenAfshin Yes. That is what you can do.2012-12-03
  • 0
    @Arthur, but the computation time doubled as I splited the exponentiation to factors !!!2012-12-03
  • 0
    @MohsenAfshin in that case, the exponentiation algorithm in your software is quite capable, and I can offer no further help.2012-12-03
  • 0
    Have you compared the different types of tests against their running time? For example, you can see a list of them here with comments of complexity: http://en.wikipedia.org/wiki/Primality_test2012-12-13

0 Answers 0