1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Product of primes

  1. Mar 13, 2014 #1
    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: Mar 13, 2014
  2. jcsd
  3. Mar 13, 2014 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    How many primes are [itex]\equiv 1 \mod 3[/itex]
     
  4. Mar 13, 2014 #3

    pasmith

    User Avatar
    Homework Helper

    More importantly, for how many primes [itex]q[/itex] is it true that [itex]q[/itex] is divisible by 3?
     
  5. Mar 13, 2014 #4

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    At least there's one of those!
     
  6. Mar 13, 2014 #5
    The definition of prime says a prime is divisible only by itself and 1, hence only 3 fits for the occasion :P
     
  7. Mar 13, 2014 #6
    You people must be some kind of super geniuses.
     
  8. Mar 13, 2014 #7
    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.

    Infinite? I can't prove it. But why?
     
  9. Mar 13, 2014 #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.
     
  10. Mar 14, 2014 #9

    pasmith

    User Avatar
    Homework Helper

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

     
  11. Mar 14, 2014 #10
    Ahh, I was quite confused.
     
  12. Mar 17, 2014 #11
    Somebody clean up all the useless replies here please.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Product of primes
  1. Germain primes (Replies: 1)

  2. Prime numbers (Replies: 8)

Loading...