Finding (p-1)(q-1) with Good Precision - Number Theory Doubt

[jobsism]

Given a number pq that is the product of two positive integers p and q, is there any way of finding with good precision, (p-1)(q-1)? Or any approximation at the least?

Thanks in advance! :D

 

[Number Nine]

I assume that p and q are prime.
The answer is almost certainly no, given that prime factorization is a very difficult problem and that being able to compute (p-1)(q-1) would give you a great deal of information about p an q.

 

[jobsism]

I assume that p and q are prime.
The answer is almost certainly no, given that prime factorization is a very difficult problem and that being able to compute (p-1)(q-1) would give you a great deal of information about p an q.

But you see, for large values of p & q, (p-1)(q-1) is approximately 0.9999...times pq. I was just hoping maybe this approximation could be pinpointed.

What if p and q aren't prime?Is it possible to obtain anything?

 

[mtayab1994]

But you see, for large values of p & q, (p-1)(q-1) is approximately 0.9999...times pq. I was just hoping maybe this approximation could be pinpointed.

What if p and q aren't prime?Is it possible to obtain anything?

Even if p and q aren't primes you would still get .999...times pq for high values of p and q.

 

[mtayab1994]

This is probably a way you could think of it. If you look at it as a limit as p and q approach inf. what would you get?

 

[AlephZero]

But you see, for large values of p & q, (p-1)(q-1) is approximately 0.9999...times pq. I was just hoping maybe this approximation could be pinpointed.

On the other hand if p = 2, (p-1)(q-1) is approximately 0.5 times pq.

I don't see this is going anywhere, unless you rethink what your question really is.

 

[dodo]

Maybe some rough approximation could be done. Ignore for the moment the primality of p or q, to concentrate only on their magnitudes. As (p-1)(q-1) = pq - (p + q - 1), you can have an idea of the difference (p + q - 1) depending on how far the factors differ from sqrt(pq).

Here is a graph of (p + q - 1) for pq = one million, for p varying from 100 to 1000, where you see how the curve flattens to the right.

http://img684.imageshack.us/img684/6084/pq1.png

When p = q = sqrt(pq) (as in the value 1000 on the X-axis of the graph), the difference (p + q - 1) becomes 2 sqrt(pq) - 1 (1999, in our example); when the smaller factor is half the geometric mean, or sqrt(pq) / 2 (as when the value in the X-axis is 500), the difference is (5/2) sqrt(pq) - 1 (2499 in this example).

So, if the smaller factor does not go farther than half the geometric mean sqrt(pq), the difference between pq and (p-1)(q-1) is roughly between 2 and 2.5 times the geometric mean. This kind of (or lack of) precision is likely useless for cryptography, but at least you can get a rough idea.

 

[jobsism]

Thanks, Dodo! :D

I was hoping for better precision, but I guess your's is the best there probably can be. Thanks anyway! :D

 

[dodo]

You're welcome! Please keep in mind that there is a big "if" here.

... if the smaller factor does not go farther than half the geometric mean sqrt(pq) ...

In some contexts, p and q are constructed in such a way that you have some guarantee that they will not be small factors. But what "not small" means... may not be very well defined.

The idea above can be applied if you have some constraint on exactly how small the smallest factor can be. In general, if you call "p" the smallest factor, and if the ratio p/sqrt(pq) is, say, "x", then the difference between pq and (p-1)(q-1) will be (x + 1/x) sqrt(pq) - 1. What I wrote in the previous post was that, when "x" is 1, the coefficient (1 + 1/x) is 2, and when "x" is 0.5, then (1 + 1/x) is 2.5. The graph of (1+1/x) between x=0.1 and x=1 looks much like the one above; and, obviously, (1+1/x) can grow very quickly as "x" approaches 0 (when one of the factors is very small).