From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: The Phi-Function
Date: 9 Mar 1998 23:01:02 GMT
In article <6duvme$ebg$2@nclient3-gui.server.virgin.net>,
Garner wrote:
>Is it possible to find the Phi-Function of a negative or floating number
>such as -2 or 2.5? I know that there is a method for doing this with
>factorials (for nos. such as 2.5); does the same method apply to the
>Phi-Function?
Others have pointed out that this isn't really reasonable, given the
irregular behaviour of phi(n) for integers n. Let me also suggest that
if you _did_ manage to define phi(x) as, for example, a finite sum of
integrals, then one would expect to be able to compute values numerically;
in particular, since phi(n) is integeral when n is, you would only need
to estimate the value of this floating-point expression to the nearest
integer. Now, I don't see that it is _necessary_ that this be true,
but certainly given the success of numerical analysis it's _plausible_
that this would imply phi(n) could be computed in an amount of time
bounded by, say, a polynomial in log(n) (if not actually being computable
in O(1) time!).
If you could succeed in doing that, you could in like time compute
a) whether or not n is square free (definitive test)
b) the factors p and q of a product n=p*q of two primes
At the present time no such efficient algorithm for either task is
known. It hasn't been proven that none exists, either, but since
popular encryption methods are based on the assumption that task (b)
is hard, I guess I would say that it is expected no such method
exists.
(I don't see how to do so immediately but it may be true as well that
if phi(n) can be computed in polynomial time for all n, then
all numbers can be factored in polynomial time. Does anyone see a
method for doing so?)
In short: stick to the definition of phi(n) given in your number theory text!
dave
Factorization:
index/11Y05.html
==============================================================================
From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: The Phi-Function
Date: 11 Mar 1998 07:52:22 GMT
Yesterday I wrote:
>(I don't see how to do so immediately but it may be true as well that
>if phi(n) can be computed in polynomial time for all n, then
>all numbers can be factored in polynomial time. Does anyone see a
>method for doing so?)
Why, yes, I do -- probabilistically speaking.
If integers n and f = phi(n) are known, write f = 2^k g where g
is odd. Consider the map x: a -> a^g on (Z/N Z)^*. If N = P1*P2*... is
the primary decomposition of N, then (Z/N Z)^* = Prod( (Z/P_i Z)^* ).
On each factor group, the map x is a projection to the Sylow-2-subgroup,
and on that subgroup x is an isomorphism. So if we apply x to
randomly-selected integers in (Z/N Z)^* we will obtain all elements
of the Sylow subgroup S equally often.
Now consider the map y: S -> M(S) (where M(S) is the subgroup of
elements of order 1 or 2) defined by letting y(s) be the last
non-identity term in the sequence s, s^2, s^4, s^8, ... (and letting
y(1)=1). This produces an element y(s) whose square is 1 mod N,
and which is itself +-1 mod N with probability at most 1/2. With at most
log(N) iterations of this sequence we thus find a solution to x^2==1 mod N
other than +-1, with probability about 1- 1/N.
Thus a computation of (x-1,N) will find a factor of N.
Of course if for every composite number we can find a factor, then for
every number we can find a complete factorization. (proof by induction).
So we see that the ability to compute phi(n) quickly would imply the
ability to factor quickly, which is not yet possible and, some would say,
not very likely. Still, this thread was prompted by a person who
wanted an analytic extension of phi, and this line of reasoning
doesn't quite preclude the existence of one.
Indeed, for every prime p we can make an analytic function X_p(t) which
equals 1 when t=0 but vanishes at t=1, t=2, ..., t=p-1, and furthermore
is periodic with period p. Then we could set
phi(t) = t*exp(Sum ln(1-1/p)*X_p(t) ),
the sum taken over all primes. This agrees with the totient function for
positive integral t.
dave
==============================================================================
From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: The Phi-Function
Date: 12 Mar 1998 05:15:20 GMT
Gerry Myerson wrote:
>rusin@vesuvius.math.niu.edu (Dave Rusin) wrote:
>
>=> Indeed, for every prime p we can make an analytic function X_p(t) which
>=> equals 1 when t=0 but vanishes at t=1, t=2, ..., t=p-1, and furthermore
>=> is periodic with period p. Then we could set
>=> phi(t) = t*exp(Sum ln(1-1/p)*X_p(t) ),
>=> the sum taken over all primes. This agrees with the totient function for
>=> positive integral t.
>
>Have you checked to see whether that Sum converges for t not a positive
>integer?
Of course not! This _is_ sci.math, right? We have traditions to uphold here!
(He's right, of course. We have some flexibility in our choice of the X_p,
so we can fix this in several ways. For example, we can define phi(t)=phi(1/t)
when t<1 , using the definition above for t>=1. So we need only check
convergence away from zero. Suppose we choose the X_p to have the
additional property that |X_p(t)| < 1/p for t in an interval [1, N_p].
As long as the N_p tend to infinity with p, then for any t>1,
almost all the terms of Sum are bounded by O(1/p^2), so the sum converges.
We can even make the X_p analytic, I suppose, by taking X_p to be some
Fourier sum which approximates the characteristic function of the
interval [-1/2, 1/2] (and repeated with period [0, p]). The Fourier series
does not converge in the sup-metric (that is, there is the Gibbs phenomenon)
but these sums are known to converge to 0 (in this metric) on [1, p-1],
say.
But this is all silly -- all respondents seem to be in agreement that phi
is fundamentally a number-theoretic function; extensions to R are
going to be artificial and pointless.)
dave