# Product of primes

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:

PeroK
Homework Helper
Gold Member
2020 Award
How many primes are $\equiv 1 \mod 3$

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

PeroK
Homework Helper
Gold Member
2020 Award
More importantly, for how many primes $q$ is it true that $q$ is divisible by 3?

At least there's one of those!

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

You people must be some kind of super geniuses.

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?

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
Homework Helper
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?

Ahh, I was quite confused.

Somebody clean up all the useless replies here please.