Distinguish pq Prime Cases: Algorithm for ppt

In summary, the conversation discussed a mathematical problem involving primes and their congruencies, specifically focusing on cases where p < q and either (p \equiv 1 \mod 4 and q \equiv 3 \mod 4) or (p \equiv 3 \mod 4 and q \equiv 1 \mod 4). There was also a mention of a possible cryptographic application and the question of how many primes are congruent to 1 mod 3. However, the relevance of this question was later clarified.
  • #1
Dragonfall
1,030
4
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
  • #2
How many primes are [itex]\equiv 1 \mod 3[/itex]
 
  • #3
More importantly, for how many primes [itex]q[/itex] is it true that [itex]q[/itex] is divisible by 3?
 
  • #4
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!
 
  • #5
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
 
  • #6
You people must be some kind of super geniuses.
 
  • #7
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?
 
  • #8
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
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.
 

FAQ: Distinguish pq Prime Cases: Algorithm for ppt

1. What is the purpose of the Distinguish pq Prime Cases Algorithm for ppt?

The Distinguish pq Prime Cases Algorithm is used to determine whether a given number, p, is prime or not. This is important in many mathematical and scientific applications, such as cryptography and number theory.

2. How does the Distinguish pq Prime Cases Algorithm work?

The algorithm works by checking whether p is divisible by any number between 2 and the square root of p. If it is not divisible by any of these numbers, then p is considered a prime number. If it is divisible by any of these numbers, then p is not prime.

3. What is the time complexity of the Distinguish pq Prime Cases Algorithm?

The time complexity of this algorithm is O(sqrt(p)), which means that its running time increases proportionally to the square root of the input number, p. This makes it a relatively efficient algorithm for determining primality.

4. Can the Distinguish pq Prime Cases Algorithm be used for numbers other than integers?

No, the algorithm is specifically designed for integers and is not applicable to other types of numbers, such as decimals or fractions.

5. Are there any limitations to the Distinguish pq Prime Cases Algorithm?

While the algorithm is efficient for determining primality, it can become cumbersome for extremely large numbers. Additionally, it may produce inaccurate results for numbers that are too large for computing devices to handle. In these cases, more advanced algorithms may be needed.

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
2K
MHB Show Equivalence: $a^d \equiv 1 \pmod n$
Replies
3
Views
2K
MHB Solving Kaliprasad's Challenge: Finding x Mod p
Replies
1
Views
1K
MHB Proving Prime Numbers in Quadratic Imaginary Fields
Replies
1
Views
2K
I Question on Primitive Roots and GCDs
Replies
2
Views
1K
MHB Computation of discrete logarithm
Replies
1
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
2K
What is the history of quadratic reciprocity and its symbols?
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top