Euler's totient function and factoring
Stefan Katzenbeisser
\phi(n), where \phi is Euler's totient function, the prime factorization
of n can be computed in random polynomial time (i.e. computing \phi(n)
and factoring n are computationally equivalent).
This result is e.g. stated in Motvani&Raghavan's book on randomized
algorithms as exercise 14.3. However, I was unable to find a proof
for this fact (except for the trivial case where n is the product of
two primes, of course). Does anyone know a paper or book where I can
look up the proof and similar results (as far as I know it should be
sufficient to know any multiple of \lamda(n), where \lambda is
Carmichael's function, instead of \phi(n))?
Thanks,
--S
--
--------------------------------------------------------------------
skatzen...@XXXacm.org (remove "XXX" before replying)
http://stud3.tuwien.ac.at/~e9625414
spam...@nil.nil
> It is well-known that given any positive integer n and the value of
> \phi(n), where \phi is Euler's totient function, the prime factorization
> of n can be computed in random polynomial time (i.e. computing \phi(n)
> and factoring n are computationally equivalent).
All one needs is any workable (i.e. not so large that one cannot
work with it) multiple of the (multiplicative) orders of all the
elements in Z'_n, the multiplicative group of the integers
(relatively prime to n) under multiplication.
Suppose one has such, call it k (any multiple of Carmichael's function
such as the Euler Totient, or any multiple of THAT suffices).
Write k=2^a*b were b is odd.
Then x^k=1 mod n for any x relatively prime to n.
Pick an x (random):
Calculate GCD(x,n). If that is not 1 you already have
a factor of n (you just happened to guess a factor of n).
This is NOT likely to occur ([grin]).
So ... GCD(x,n)=1 (or else you already have a factor of n).
Not calculate X=x^b mod n.
Now you have X with X^(2^a)=1 mod n.
If X=+/-1 mod n, pick another x and try again.
Now successively square X.
Consider X mod n.
Replace X with X^2 mod n
Replace X with X^2 mod n
Replace X with X^2 mod n.
etc.
EVENTUALLY you get a result which is 1 mod n
(in at most "a" steps).
Look at the X value (after successive squarings)
RIGHT BEFORE YOU GOT 1 mod n.
That is not 1 mod n (since this is the value before
you get 1 mod n).
If this is -1 mod n, pick another x and try again.
So ... hopefully you find an X (NOT congruent to 1
or -1 mod n) with X^2=1 mod n.
This is:
(X-1)(X+1)=0 mod n
BUT X-1 <>0 mod n and X+1 <>0 mod n.
So (X-1) must have SOME (but not all) the factors
of n and so must X+1.
Thus, GCD(X-1,n) will give a proper factor of n.
What is the probability that you can find an x that
works? High (unless n just happens to be a power of
a prime ... so ... check that n is NOT a power of a
prime first ... that is easy enough ... just check
that n<>2^a, n<>3^a, etc. The largest prime you
have to check is ln(n)/ln(2)).
(one would have to look at the factorization of n
to see the components of the multiplicative group
mod n to determine the actual percentage of x's
which will result in factoring n, but it is large)
Once you have one factor of n, n=AB, just do it again
for the components to factor them, etc. (n has at most
ln(n)/ln(2) factors) to get the final factorization.
The trick here is to find X with X^2=1 mod n
((X-1)(X+1)=0 mod n) but X<>+/-1 mod n.
Then GCD(X-1,n) is a factor of n.
If you have a multiple of all the multiplicative orders
(any multiple of Carmichael's function), splitting that
into an odd part and a power of two (2^a*b), taking any x,
taking X=x^b mod n and successively squaring X will very
often (so you only will have to do this for a few x's
until you have "success") lead to such an X which allows
you to factor n.
Stefan Katzenbeisser
> The trick here is to find X with X^2=1 mod n
> ((X-1)(X+1)=0 mod n) but X<>+/-1 mod n.
> Then GCD(X-1,n) is a factor of n.
>
> If you have a multiple of all the multiplicative orders
> (any multiple of Carmichael's function), splitting that
> into an odd part and a power of two (2^a*b), taking any x,
> taking X=x^b mod n and successively squaring X will very
> often (so you only will have to do this for a few x's
> until you have "success") lead to such an X which allows
> you to factor n.
Ahhh... Thanks for your quick reply. I definitively should have
known that, as it is in essence the proof that computing
the RSA decryption exponent is computationally equivalent to
factoring the modulus (actually this problem is just a
special case).
Thanks again,
--S
Serdar Boztas
I have no idea what the above problem may be called in the literature.
I will describe the problem and ask for pointers to known results,
papers, etc. It seems to me like there are two ways of describing it in
the context of applications but my internet searches have not turned up
anything very useful.
1. a kind of "orthogonal fair broadcast" problem
2. a kind of "decentralized data compression" problem.
Consider a source S and N receivers--R_1, .. R_N-- who can hear the
source, i.e., the one-to-many broadcast scenario. Assume that the
channels S-->R_k are all noiseless for k=1,2,...,N.
The source wants to transmit independent binary quantities X_1,...,X_N,
each of which
I assume to be equiprobably 0 or 1. It transmits a sequence of binary
code symbols--I have no problem assuming that a code sequence
f_1,f_2,..,f_N,... is used instead of a fixed length code--which enables
the receivers to recover the quantities X_1,..,X_N.
Here's the twister. User R_k is ONLY interested in X_k and none of the
other X_k'.
The code designer is interested in a minimax criterion. On average
(averaged over
the distribution of X_1...X_N) when does the LAST receiver to learn its
own X_k learn
it?
EXAMPLE: Let f_1=X_1,...,f_N=X_N. Then T_1=1,...,T_N=N for this code if
we define
T_k=min{ z : X_k is uniquely determined by f_1,...,f_z }
and
max E( T_k ) = N
1<=k<=N
However the arithmetic average of the T_k is (1+2+..+N)/N = (N+1)/2.
How much better can we do? What are schemes that can be used?
In effect, the code in the example, is disadvantaging the Nth component
X_N, it is
always the last one to be by the corresponding receiver.
Many thanks.
--
Serdar Boztas, RMIT Department of Mathematics, Melbourne, Australia
http://minyos.its.rmit.edu.au/~rmasb/index.html <------ My Homepage
All the colours were soiling at the same speed,
White was given the first prize <----------- poetry by Ozdemir Asaf
http://www.cs.rpi.edu/~sibel/poetry <----------- Turkish poetry page