Distinguish pq Prime Cases: Algorithm for ppt

  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Primes Product
AI Thread Summary
The discussion revolves around distinguishing two cases of prime pairs (p, q) based on their congruences modulo 4. Participants inquire about the existence of a polynomial-time algorithm (ppt) that can differentiate between these cases. The conversation touches on the properties of prime numbers, particularly regarding their divisibility by 3, noting that only the prime number 3 fits this criterion. There is a consensus that there are infinitely many primes congruent to 1 modulo 3, although proving it remains elusive. The complexity of the problem suggests potential applications in cryptography, particularly in creating simple bit-commitment schemes.
Dragonfall
Messages
1,023
Reaction score
5
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:
Mathematics news on Phys.org
How many primes are \equiv 1 \mod 3
 
More importantly, for how many primes q is it true that q is divisible by 3?
 
pasmith said:
More importantly, for how many primes q is it true that q is divisible by 3?

At least there's one of those!
 
pasmith said:
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.
 
Dragonfall said:
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.

PeroK said:
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.
 
PeroK said:
How many primes are \equiv 1 \mod 3

pasmith said:
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

Dragonfall said:
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?
 
  • #10
Ahh, I was quite confused.
 
  • #11
Somebody clean up all the useless replies here please.
 

Similar threads

MHB About a variant of the Chinese Remainder Theorem
Replies
5
Views
2K
For n>3, show that the integers n, n+2, n+4 cannot all be prime
Replies
27
Views
3K
MHB Show Equivalence: $a^d \equiv 1 \pmod n$
Replies
3
Views
2K
I Question on Primitive Roots and GCDs
Replies
2
Views
2K
If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that....
Replies
16
Views
2K
Show that the sum of twin primes ## p ## and ## p+2 ## is divisible?
Replies
17
Views
3K
What is the history of quadratic reciprocity and its symbols?
Replies
1
Views
2K
If ## p\geq q\geq 5 ## and ## p ## and ## q ## are both primes ....
Replies
30
Views
2K
MHB Test whether the integer is a prime
2
Replies
96
Views
11K
MHB Why do we get like that the message?
Replies
2
Views
1K

Hot Threads

Recent Insights

Back
Top