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.