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...