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

1. ### arfa branecall me arfValued 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?

3. ### DinosaurRational SkepticValued 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.

5. ### arfa branecall me arfValued 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.

7. ### DinosaurRational SkepticValued 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 branecall me arfValued 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. ### DinosaurRational SkepticValued 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. ### eramSciengineerValued Senior Member

Messages:
1,877

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

Sorry, just being very nerdy.

11. ### phytiRegistered 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. ### NehushtanRegistered 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. ### RJBeeryNatural PhilosopherValued 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 branecall me arfValued 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 branecall me arfValued 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. ### RJBeeryNatural PhilosopherValued 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 branecall me arfValued 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. ### RJBeeryNatural PhilosopherValued 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. ### leopoldValued 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. ### RJBeeryNatural PhilosopherValued 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 branecall me arfValued 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. ### RJBeeryNatural PhilosopherValued 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 branecall me arfValued Senior Member

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