Distinguish pq Prime Cases: Algorithm for ppt

[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?

 

[PeroK]

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

 

[pasmith]

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

 

[PeroK]

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

At least there's one of those!

 

[lendav_rott]

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

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

 

[Dragonfall]

You people must be some kind of super geniuses.

 

[DrewD]

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?

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.

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

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

 

[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.

 

[pasmith]

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

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

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

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

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

 

[DrewD]

Ahh, I was quite confused.

 

[Dragonfall]

Somebody clean up all the useless replies here please.