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