Distinguish pq Prime Cases: Algorithm for ppt

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Primes Product
Click For Summary

Discussion Overview

The discussion revolves around the properties of prime numbers, specifically focusing on the conditions under which two primes, p and q, can be distinguished based on their congruences modulo 4 and the existence of a probabilistic polynomial-time (ppt) algorithm for this purpose. The conversation touches on various aspects of prime number theory and potential applications in cryptography.

Discussion Character

  • Exploratory
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant inquires whether there exists a ppt algorithm that can distinguish between two cases of primes p and q based on their congruences modulo 4.
  • Another participant questions the number of primes that are congruent to 1 modulo 3, suggesting the possibility of an infinite quantity but expressing uncertainty about proving it.
  • There is a repeated emphasis on the divisibility of primes by 3, with one participant humorously noting that only the prime number 3 fits this criterion.
  • A participant expresses confusion regarding the original post's conditions and clarifies that the congruences were initially stated incorrectly.
  • One participant suggests that if the problem is indeed difficult, it could lead to a simple bit-commitment scheme.
  • Another participant expresses frustration with what they perceive as irrelevant replies in the thread.

Areas of Agreement / Disagreement

Participants express differing views on the relevance of certain points, particularly regarding the number of primes congruent to 1 modulo 3 and the divisibility of primes by 3. The discussion does not reach a consensus on the existence of a ppt algorithm for distinguishing the prime cases.

Contextual Notes

The discussion includes assumptions about the properties of primes and their congruences, but these assumptions are not universally accepted or proven within the thread. The initial confusion regarding the modulo conditions indicates a potential limitation in clarity.

Dragonfall
Messages
1,023
Reaction score
5
Given [itex]pq[/itex] where [itex]p < q[/itex] are prime, but either ([itex]p \equiv 1 \mod 4[/itex] and [itex]q \equiv 3 \mod 4[/itex]) or ([itex]p \equiv 3 \mod 4[/itex] and [itex]q \equiv 1 \mod 4[/itex]).

Is there a ppt algorithm that will distinguish the two possibilities?
 
Last edited:
Mathematics news on Phys.org
How many primes are [itex]\equiv 1 \mod 3[/itex]
 
More importantly, for how many primes [itex]q[/itex] is it true that [itex]q[/itex] is divisible by 3?
 
pasmith said:
More importantly, for how many primes [itex]q[/itex] is it true that [itex]q[/itex] is divisible by 3?

At least there's one of those!
 
pasmith said:
More importantly, for how many primes [itex]q[/itex] is it true that [itex]q[/itex] 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 [itex]pq[/itex] where [itex]p < q[/itex] are prime, but either ([itex]p \equiv 1 \mod 4[/itex] and [itex]q \equiv 3 \mod 4[/itex]) or ([itex]p \equiv 3 \mod 4[/itex] and [itex]q \equiv 1 \mod 4[/itex]).

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 [itex]\equiv 1 \mod 3[/itex]

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 [itex]\equiv 1 \mod 3[/itex]

pasmith said:
More importantly, for how many primes [itex]q[/itex] is it true that [itex]q[/itex] 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 [itex]pq[/itex] where [itex]p < q[/itex] are prime, but either ([itex]p \equiv 1 \mod 3[/itex] and [itex]q \equiv 3 \mod 3[/itex]) or ([itex]p \equiv 3 \mod 3[/itex] and [itex]q \equiv 1 \mod 3[/itex]).

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

For n>3, show that the integers n, n+2, n+4 cannot all be prime
  • · Replies 27 ·
Replies
27
Views
4K
Undergrad Question on Primitive Roots and GCDs
  • · Replies 2 ·
Replies
2
Views
2K
If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that....
  • · Replies 16 ·
Replies
16
Views
3K
Show that the sum of twin primes ## p ## and ## p+2 ## is divisible?
  • · Replies 17 ·
Replies
17
Views
3K
Graduate What is the history of quadratic reciprocity and its symbols?
  • · Replies 1 ·
Replies
1
Views
2K
If ## p\geq q\geq 5 ## and ## p ## and ## q ## are both primes ....
  • · Replies 30 ·
2
Replies
30
Views
3K
MHB Test whether the integer is a prime
  • · Replies 96 ·
4
Replies
96
Views
12K
MHB Why do we get like that the message?
  • · Replies 2 ·
Replies
2
Views
1K
MHB Proving the Congruence of Primes of the Form x² + 5y² (mod 20)
  • · Replies 7 ·
Replies
7
Views
3K
Determine the set of odd primes ## p ##?
  • · Replies 14 ·
Replies
14
Views
3K