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