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.

  • 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