Simple problem about primes

Discussion in 'Physics & Math' started by arfa brane, Apr 7, 2013.

  1. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    If a number n is known to be a product of exactly two primes, show how they can be determined if n is known.

    Well, if n is known, so is φ(n), and if n = pq where p and q are prime, then φ(n) = φ(pq) = φ(p)φ(q) = (p-1)(q-1).

    So (p-1) divides φ(n), and (q-1) divides φ(n). In fact dividing φ(n) by either factor will find the other.

    Or is there something I've skipped over?
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. Dinosaur Rational Skeptic Valued Senior Member

    Messages:
    4,885
    How do you define the function φ(n)?

    Your post seems to define it as (p-1)*(q-1). However, p, q, (p-1), & (q-1) are unknown providing no useful information.
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    φ(n) is defined as the number of positive integers less than n and coprime to n. That is, all k such that gcd(k,n) = 1, where k,n are integers.
    If n is prime, there are n-1 numbers coprime to it. φ(n) is called Euler's function.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. Dinosaur Rational Skeptic Valued Senior Member

    Messages:
    4,885
    From your post, the following defines φ (n) as equal to (p-1)(q-1)
    I suppose that was not your intent & the above requires some punctuation.

    Could you use some simple example using say 15 (3*5) or 49 (7*7) to explain?
     
  8. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    To calculate how many numbers less than 15 are coprime to 15, you could use trial and error. For instance gcd(1,15) = 1, gcd(2,15) = 1, but gcd(3,15) = 3. Of the 14 numbers less than 15, it turns out that 8 of them are coprime. Or, {3,5,6,9,10,12} are not coprime since they have factors common with 15.

    But there's an easier way, since 15 = 3x5, So φ(15) = φ(3)φ(5) = (3-1)(5-1) = 8. The φ function doesn't give you a list of numbers, but a single number.

    Since any integer is a product of primes, there you have it . . .
     
  9. Dinosaur Rational Skeptic Valued Senior Member

    Messages:
    4,885
    Arfa Brane: I do not call myself Dinosaur because I am a multi-ton creature: It is because I once used a slide rule & a mechanical calculator.

    One learns something every day. φ(n) is my lesson for today: I never heard of it.

    At first I thought it might aid in factoring primes, but for that task it does not seem to be much, if any, hlep.
     
  10. eram Sciengineer Valued Senior Member

    Messages:
    1,877

    "The Thing" might be a good nickname, because it can adapt to anything on the fly.

    Please Register or Log in to view the hidden image!



    Sorry, just being very nerdy.
     
  11. phyti Registered Senior Member

    Messages:
    678
    A simple method for odd numbers, you try each prime from 3 to p (= or <) sqrt(n), which for 15 gives {3}.

    If n is a prime, it has no factors, and one is not a prime.

    Wiki has finally stated 'the fundamental theorem of arithmetic' equivalently as:
    all composite numbers are a product of primes.
     
  12. Nehushtan Registered Member

    Messages:
    29
    Note: p and q must be distinct for the formula to work. If p = q then \(\phi(n)=\phi(p^2)=p(p-1)\). For example, \(\phi(9)=6\) and \(9=3^2;\ 6=3(3-1)\).

    So if p and q are distinct primes we have \(\phi(n)\) \(=\ (p-1)(q-1)\) \(=\ pq-p-q+1\) \(=\ n+1-(p+q)\). So you have \(-(p+q)=\phi(n)-n-1\) and \(pq=n\) – in other words p and q are the roots of the quadratic equation \(x^2-[n+1-\phi(n)]x+n=0\). Since \(n\) and \(\phi(n)\) are known, p and q can be found by solving the quadratic equation for its roots.
     
  13. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    The bold part is your problem. If it was this simple then security through number theory would fall apart. φ(n) is only trivially known when n is a prime.
     
  14. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    No, if n is a prime, it has the form p[sup]k[/sup], where k = 1.
    1 isn't prime but it is the product of zero primes.
     
  15. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    ?? The part you've bolded is part of the "simple" problem: you have a number which is known to be the product of two primes (I would assume that means two distinct primes).
    Incorrect. φ(n) is a function with domain and range the natural numbers.
     
  16. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    I'm sorry but what the hell are you talking about?? Perhaps you would like to factor RSA-210. I mean, you have n, so apparently you also believe that you have φ(n)...

    RSA-210 = 245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549103626827191679864079776723243005600592035631246561218465817904100131859299619933817012149335034875870551067

    Perhaps using this info you could put your algorithm to use?
     
  17. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    You seem to have little idea what the hell I'm talking about.
    To restate: you have a number n which is known to be the product of two primes. What does that have to do with RSA?
     
  18. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    Because RSA-210 is a number n which is KNOWN to be the product of two primes.
    I thought you were suggesting that the algorithm in the OP could be used to calculate the primes p and q. If this is what you contend then it is you who is talking out of your ass.
     
  19. leopold Valued Senior Member

    Messages:
    17,455
    the only way i know of to do this is by "brute force".
    0. set n1=n.
    1. take the square root of n and add 1. set n equal to this number
    2. set x to 2.
    3. increment x. divide n1 by x.
    4. if the result is an integer then subtract from n1. the number you get and x are the 2 primes.
    5. if the result of the division is not an integer then go back to step 3.

    the above can easily be implemented into a computer program.
    i left out the test for "out of range" value for x. if x becomes greater than the sqr(n)+1 then the program has finished by exhausting all possibilities.

    edit:
    if you decide on the computer program route then you need to be aware of rounding errors.
    you might need to add a very tiny number such as 0.0005 at certain places in the program (i'll leave it to you to figure out where).
     
  20. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    There are many more efficient ways to do this, but alas the OP is not one of them.
     
  21. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    I assume you read the first post, which says:
    The algorithm will of course, apply to all those n which are the product of two distinct primes (the problem doesn't explicitly state the primes are distinct, so I guess that means you're supposed to account for either case).
    How or why did you get the idea the problem is about RSA encryption? It's about factoring numbers which are the product of two primes, that's it.
     
  22. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,222
    We can check whether p and q are distinct by taking the square root of n. Otherwise, I'm telling you and you seem not to want to hear that the algorithm does not work because you cannot "magically" know what φ(n) is without basically doing the same amount of work as calculating p and q directly.
     
  23. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    If you know n, you can calculate φ(n). No magic required.
     

Share This Page