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?
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.
φ(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.
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?
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 . . .
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.
"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.
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.
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.
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.
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.
?? 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.
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?
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?
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.
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).
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.
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.
