the "sieve" method comes to mind but i don't see any way to implement it on a computer because of the very large numbers involved. a person shouldn't be too worried about "efficiency" with a computer program. the method i outlined above can easily find ALL primes up to about a million in a matter of seconds. 6 digit primes can be found in less than a minute. with todays cores and the above method implemented in hardware it's hard telling how "fast" you can find primes in the trillions.
No problem. Below is n. It is KNOWN to be a product of TWO DISTINCT PRIMES. Please tell me what φ(n) is without using magic. RSA-210 = 24524664490027821197651766357308801846702678767833 27597434144517150616008300385872169522083993320715 49103626827191679864079776723243005600592035631246 561218465817904100131859299619933817012149335034875870551067
Umm when it comes to using number theory for computer security "efficiency" is all that matters. There is an interesting thing about the OP though; this is something I played around with about 15 years ago. It won't help you in any traditional sense of finding p and q, but you can rearrange things thusly: n = pq Set p = (k+x) q = (k-x) (this step is permissible because we know their difference is even, both being primes) n = k^2 - x^2 Just a fun way to visualize things, plus now your search space can be restricted to the difference between p and q (the difference being 2x) rather than the lesser value of p and q. In some cases this can be a make a dramatic difference in computing time.
maybe. efficiency assumes the problem solvable. when you can easily find primes within the given range of encryption algorithms the only thing that matters is finding the right key. the only way i can think of with an unordered list (encryption must be considered unordered) is by brute force, trying each number in sequence. this is something computers are good at i've read that there is currently hardware that will break a 20 digit key in a few seconds.
How do you calculate \(\varphi(n)\) without knowing the factors of n? In your example of \(\varphi(15)\), you only calculated it by knowing its factors in advance or finding them through brute force.
How do you calculate \(\varphi(n)\) without knowing the factors of n? In your example of \(\varphi(15)\), you only calculated it by knowing its factors in advance, or finding them through brute force. It seems to me that finding \(\varphi(n)\) doesn't help to find the factors of n, because you need the factors of n before you can find \(\varphi(n)\)!
From the Wikipedia page on Euler's totient function: Setting up an RSA system involves choosing large prime numbers p and q, computing n = pq and k = \(\blue\normalsize\varphi(n)\) ... The security of an RSA system would be compromised if the number n could be factored or if \(\blue\normalsize\varphi(n)\) could be computed without factoring n.
Hmm. The definition I have for \( \phi :\; \mathbb {N} \rightarrow \mathbb {N} \) is: \( \phi (m) := | \{ d \in \mathbb {N}:\; \mathrm (1 \leq d \leq m) \wedge (gcd(d,m) = 1)\} | \). So it's defined as the size of the set of numbers less than and coprime to m. This is independent of the size of m, that is, it works the same way for small m as it does for large m. That is how mathematics is, and I'm really sorry about that (no I'm not). But the more perceptive of you may have noticed the OP says nothing about how big the number is, only that it's a product of primes. Since the number of prime factors is even, another thing we know is it's Mobius function value is 1. The problem is about what you can find out about the two prime factors, assuming you know n and φ(n). We know that φ(n) is hard to compute for large n, and that's why large prime factors are used in cryptography. This problem isn't about that.
Yes, there's no disagreement on the definition. The disagreement is whether you can easily calculate \(\varphi(n)\) if you don't know the factors of n. Actually, the OP only says to assume we know n, not \(\varphi(n)\): "If a number n is known to be a product of exactly two primes, show how they can be determined if n is known." It then says that knowing n implies knowing φ(n): "Well, if n is known, so is φ(n)," and it is the truth of that statement that is in dispute. OK, so I think we're done. I think we all agree that if n=pq, with p and q prime, then knowing n and \(\varphi(n)\) makes it easy to calculate p and q. It seems we now also agree that knowing n does not imply knowing \(\varphi(n)\). So I guess we're done, unless anyone wants to engage in a thread post-mortem?
Look, if you know the value of a number n, then it is always mathematically possible to compute φ(n). Recall that physical parameters like the amount of time it could take are irrelevant. The fact that small numbers are "easy" to do this with is also irrelevant.
If you know n, it is always mathematically possible to compute the factors of n. Computing φ(n) is harder than computing the factors of n.
I would imagine computing φ(n) is equivalent to computing the factors of n, at least in the "big-O" sense of complexity. But it certainly isn't easier! Please Register or Log in to view the hidden image!
I don't see how. (Note: the OP is not helpful, since it assumes you can e.g. divide \(\varphi(n)\) by (p-1), which seems tricky without knowing p in advance.)
You may be right; it isn't immediately obvious. At the very least we've reduced the problem to finding the factors for \(\varphi(n)\) (which in this case is considerably smaller than n), adding one, and testing whether it divides n.
Nope: (p-1)(q-1) is not that much smaller, and you now have the added problem that the factorization doesn't tell you which factor contribute to (p-1) and which factors contribute to (q-1).
You're right, Funkstar, it isn't much smaller, I was mistaken on that point. It's only much smaller if n has many prime factors. However, the method for determining p and q once you know φ(n) can be trivially deduced from what I wrote earlier: If you want to figure it out, go for it. If you want me to spoil it for you let me know.
Cute: \(n-\varphi(n)-1=2k\), which then gets us x trivially. (I'll admit that I skipped your posts, initially. I usually stay away from arfa brane's threads, and only posted because I thought Pete was off track.)
Later discussion made the OP understand that this problem only makes sense if the problem was given as: "If a number n is known to be a product of exactly two distinct primes, show how they can be determined if both n and φ(n), with φ() is Euler's Totient function, are known. Lots. It does not solve even the restatement of the problem. It is factoring by the method of assuming we know one of the factors. Only someone who has studied (read up on) number theory would recognize it as Euler's Totient function. http://mathworld.wolfram.com/TotientFunction.html Knowing that a function has a well-defined value for every input is not the same as knowing the value for a particular input. Spoiler \(x = \frac{1 + n - \phi(n) \pm \sqrt{ \left( 1 + n - \phi(n) \right)^2 - 4 n }}{2} \begin{array}{c|c c c| c c} n & \phi(n) & 1 + n - \phi(n) & \sqrt{ \left( 1 + n - \phi(n) \right)^2 - 4 n } & x_{-} & x_{+} \\ \hline \\ 6 & 2 & 5 & \sqrt{25 -24} = 1 & 2 & 3 \\ 10 & 4 & 7 & \sqrt{49-40}=3 & 2 & 5 \\ 14 & 6 & 9 & \sqrt{81 -56}=5 & 2 & 7 \\ 15 & 8 & 8 & \sqrt{64 -60} =2 & 3 & 5 \\ pq & (p-1)(q-1) & p + q & \left| p - q \right| & \textrm{min}(p,q) & \textrm{max}(p,q) \\ \hline \\ 4 & 2 & 3 & \sqrt{9 -16} & \frac{3}{2} - \frac{i\sqrt{7}}{2} & \frac{3}{2} + \frac{i\sqrt{7}}{2} \\ 9 & 6 & 4 & \sqrt{16 - 36} & 2 - i\sqrt{5} & 2 + i\sqrt{5} \\ 25 & 20 & 6 & \sqrt{36 -100} & 3 - 4i & 3 + 4i \\ p^2 & p(p-1) & p+1 & \sqrt{- 3 p^2 + 2 p + 1 } & \frac{p+1}{2} - \frac{i}{2} \sqrt{3 p^2 - 2 p - 1} & \frac{p+1}{2} + \frac{i}{2} \sqrt{3 p^2 - 2 p - 1} \end{array} \) So if \(4n < \left( 1 + n - \phi(n) \right)^2 \) then p and q are distinct and given as the two values of \(\frac{1 + n - \phi(n) \pm \sqrt{ \left( 1 + n - \phi(n) \right)^2 - 4 n }}{2}\). However if \(4n > \left( 1 + n - \phi(n) \right)^2 \) then \(p = q = n - \phi(n) = \left| \frac{1 + n - \phi(n) \pm \sqrt{ \left( 1 + n - \phi(n) \right)^2 - 4 n }}{2} \right| = \frac{1}{2}\sqrt{ 4n } = \sqrt{n}\). So in either case the solution are the values of \(\left| \frac{1 + n - \phi(n) \pm \sqrt{ \left( 1 + n - \phi(n) \right)^2 - 4 n }}{2} \right|\).
rpenner, that's an interesting analysis but if p and q are not distinct then n is a perfect square, yes? Otherwise the answer can be gleaned from the post just prior to yours quite easily.
You'd know better than I, but my fuzzy understanding of algorithm complexity agrees with your assessment. I did wonder a bit about whether the statement I made was strictly true, but didn't want to make the post more complex than it is. I agree that it would have been better to say "not easier", rather than "harder".
