2
$\begingroup$

Is there any literature/survey/papers/books regarding the factorization of Strong PseudoPrimes (wrt. to a given base).

I am aware of the fact that weak Pseudo Primes can be factorized in Polynomial time. But, I was unable to get anything significant/detailed regarding Strong PseudoPrime factorization (I am aware the general Problem is considered hard), but I am looking for much more detailed analysis of the subsets that are easy (factorizable in polynomial time, sub exponential time etc.) rather than this blanket generalization.

$\endgroup$
  • $\begingroup$ "I am aware the general Problem is hard" -- is it? As far as I know, that's been conjectured but not proven. $\endgroup$ – Raphael Sep 19 '16 at 14:56
  • $\begingroup$ @D.W. There cannot be any universal strong PseudoPrime. Any Number is strong PseudoPrime to at most 3/4 bases. This is the basis of Rabin-Miller Algorithm. Editing. $\endgroup$ – TheoryQuest1 Sep 19 '16 at 15:08
  • $\begingroup$ @Raphael. I meant the same. Otherwise P!=NP will follow. $\endgroup$ – TheoryQuest1 Sep 19 '16 at 15:11
  • 1
    $\begingroup$ What Raphael is hinting at is that your parenthetical and your comment is wrong. I don't know what you mean by "the general problem", but if you mean factorization of an arbitrary number: factorization is not known to be hard, and it is not believed to be NP-complete. $\endgroup$ – D.W. Sep 19 '16 at 15:12
  • $\begingroup$ I meant it in the literal sense. Not NP-Hard or NP-Complete (would have mentioned so). Please feel free to edit the question, so that it is more clearer. $\endgroup$ – TheoryQuest1 Sep 19 '16 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.