From: "Max Moroz" To: Date: Tue, 24 Mar 1998 00:28:20 -0800 Subject: [none] Replying to your article in sci.math: >Re: The Phi-Function >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 [...] I think you use in your reasoning the ability to obtain phi(n) for any n, as you go. In fact, it is known that if you just have n and phi(n), or indeed n and any multiple of phi(n), you can factor n in poly-log time. That is, you don't have to ask for phi(other numbers) to do that. Unfortunately, I don't yet know how to do that. It is a problem from my take-home final exam, so I'll either solve it by Wednesday, or learn its solution on Thursday. Max ============================================================================== Date: Thu, 26 Mar 1998 14:38:29 -0600 (CST) From: Dave Rusin To: mmoroz@ucla.edu Subject: Factoring n using phi(n) >In fact, it is known that if you just have n and phi(n), or indeed n and any multiple of phi(n), you can factor n in poly-log time. I don't see how. I can do it if n has multiple factors, or just two distinct factors, but not in general. Here's a sample: n= 195963158926121889084852047815010778224750146972369194591416813639035861263284\ 560062708210856359004507152655300823993 has phi(n)= 195963158926121889084852047815010778222849304330785812267293748775230256716510\ 076425631981187536743092298647854219600 Factor n. I'd be delighted to know if that's possible. (It may well be, I just don't see the trick.) dave ============================================================================== From: "Max Moroz" To: "Dave Rusin" Subject: Re: Factoring n using phi(n) Date: Mon, 30 Mar 1998 10:53:40 -0800 n = 123456790123456790123456790123456790279 * 1111111111111111111111111111111111111117 * 1428571428571428571428571428571428571451. Could you send me some more examples so I can check if the algorithm works? (I didn't guess it :-( -- my professor told me, and it's been known before). You write phi(n) = f * 2^k, where f is odd. Then you pick several random g, until you find that g^f != +-1, and g^(2*f) = 1. This gives you a non-trivial root of 1, which immediately gives at least one factor of n. Of course, g^(2*f)!=+-1, g^(4*f) = 1 would work just as well, etc. Also, actually g^(2*f)=-1 is ok, too, as long as we can find a root of -1 (which I think is possible with a randomized algorithm). Finally, if we're unlucky to always get g^f=+-1, we instead can do this: pick a random h, let g=h^2. Now if g^f=1 for simplicity, we can find a root of g: it is g^((f+1)/2). Sometimes it should happen that this g^((f+1)/2) != h, so we then get two roots for g, and hence a factor of n. Max ============================================================================== Date: Mon, 30 Mar 1998 13:06:04 -0600 (CST) From: Dave Rusin To: mmoroz@ucla.edu Subject: Re: Factoring n using phi(n) Right. I remembered the trick after I wrote to you. It's probabilistic, but it succeds with probability greater than 1-1/2^n after n trials, so O(log(n)) trials ought to be sufficient. You can easily make more examples for yourself. In maple, for example, use n:=nextprime(k1)*nextprime(k2)*nextprime(k3)*... where the ki's are are favorite big numbers. Here's one which you'll easily factor; then the question is to divine how I chose the k_i's ! 103433928298454545218307846612446177645097208748232879972465183370035861202363\ 301172220958878949383387428675100240603 Anyway, this is all fun but I don't think anyone's suggesting there will ever be a way to compute phi(n) which does not essentially rely on factorization in the first place. You know, for example, that phi(n) for the n above is a multiple of the smallest m with 2^m=1 mod n, but you have no real clue as to how to find m. (Certainly you don't want to loop over m=1..phi(n), since in this example phi(n) is 103433928298454545175793210110757397773543460967485795527802842468253566382193\ 607051130751643045438279861927943123200 and it would take about 10^90 Pentium-speed machines to loop through all the values of m in less than the age of the universe...) dave ============================================================================== From: "Max Moroz" To: "Dave Rusin" Subject: Re: Factoring n using phi(n) Date: Mon, 30 Mar 1998 11:31:10 -0800 -----Original Message----- From: Dave Rusin To: mmoroz@ucla.edu Cc: rusin@clinch.math.niu.edu Date: Monday, 30 March, 1998 11:06 AM Subject: Re: Factoring n using phi(n) >>Anyway, this is all fun but I don't think anyone's suggesting there will >ever be a way to compute phi(n) which does not essentially rely on >factorization in the first place. Yes, sure.. It's just a problem from a class. (Actually it also said to find factorization if n and some MULTIPLE of phi(n) are known). But it's nice that it has so simple a solution. Max