Product of primes

  • Thread starter Dragonfall
  • Start date
  • #1
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:

Answers and Replies

  • #2
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,247
10,746
How many primes are [itex]\equiv 1 \mod 3[/itex]
 
  • #3
pasmith
Homework Helper
2,110
734
More importantly, for how many primes [itex]q[/itex] is it true that [itex]q[/itex] is divisible by 3?
 
  • #4
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,247
10,746
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
224
10
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
1,030
4
You people must be some kind of super geniuses.
 
  • #7
529
28
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.

How many primes are [itex]\equiv 1 \mod 3[/itex]

Infinite? I can't prove it. But why?
 
  • #8
1,030
4
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
pasmith
Homework Helper
2,110
734
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?

I should clarify, for the benefit of future readers, that these were in response to the unedited original post which read

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
529
28
Ahh, I was quite confused.
 
  • #11
1,030
4
Somebody clean up all the useless replies here please.
 

Related Threads on Product of primes

  • Last Post
Replies
15
Views
4K
Replies
9
Views
7K
  • Last Post
Replies
8
Views
7K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
8
Views
3K
  • Last Post
2
Replies
26
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
17
Views
4K
Top