Product of primes

1. Mar 13, 2014

Dragonfall

Given $pq$ where $p < q$ are prime, but either ($p \equiv 1 \mod 4$ and $q \equiv 3 \mod 4$) or ($p \equiv 3 \mod 4$ and $q \equiv 1 \mod 4$).

Is there a ppt algorithm that will distinguish the two possibilities?

Last edited: Mar 13, 2014
2. Mar 13, 2014

PeroK

How many primes are $\equiv 1 \mod 3$

3. Mar 13, 2014

pasmith

More importantly, for how many primes $q$ is it true that $q$ is divisible by 3?

4. Mar 13, 2014

PeroK

At least there's one of those!

5. Mar 13, 2014

lendav_rott

The definition of prime says a prime is divisible only by itself and 1, hence only 3 fits for the occasion :P

6. Mar 13, 2014

Dragonfall

You people must be some kind of super geniuses.

7. Mar 13, 2014

DrewD

I'm not familiar with one, but I'm not too familiar with these sorts of things. Is this a cryptography problem? I thought that factoring primes was always more than polynomial time.

Infinite? I can't prove it. But why?

8. Mar 13, 2014

Dragonfall

There are indeed infinitely many primes that are 1 mod 3. But that's not relevant.

If this problem is hard then it would make a very simple bit-commitment scheme.

9. Mar 14, 2014

pasmith

I should clarify, for the benefit of future readers, that these were in response to the unedited original post which read

10. Mar 14, 2014

DrewD

Ahh, I was quite confused.

11. Mar 17, 2014

Dragonfall

Somebody clean up all the useless replies here please.