Let $n$ be a large positive integer. Suppose I want to know if all the prime factors of $n$ are congruent to, say, 3 mod 8. Is this any easier than just factoring $n$?

  • 1
    $\begingroup$ Its worth mentioning that computing other relatively simple functions of the prime factors of a number (say, the mobius function, which is essentially equivalent to the parity of the number of factors) is not known to be easier than factoring. This of course says nothing about the particular question you have though. $\endgroup$
    – Mark
    Nov 10 '19 at 1:24

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.