n-adic logarithms for composite n using Euler quotient.

Georgi Guninski <[email protected]>
Newsgroups gmane.comp.mathematics.pari.devel
Message-ID <CAGUWgD-LwkwcWcS_ZVW80=at_9tc8u=0kSCt_WoXHVxre=isJg@mail.gmail.com>
First a question:  p-adic logarithm doesn't appear to work
with composite moduli.  Session:

? p=113;mo=O(p^2);a1=2;b1=3;ll=[log(b1+mo),log(a1+mo),log(a1*b1+mo)];ll[1]+ll[2]-ll[3]
%49 = O(113^2)
? p=13*113;mo=O(p^2);a1=2;b1=3;ll=[log(b1+mo),log(a1+mo),log(a1*b1+mo)];ll[1]+ll[2]-ll[3]
%50 = 405 + 451*1469 + O(1469^2)
Is the result correct?

Here is suggested approach.

Let $n$ be positive integer and $a$ integer coprime to $n$.

Define the Euler quotient $eq(n,a)=(a^phi(n)-1)/n mod n$.

To compute eq(n,a) we can efficiently compute (a^phi(n)-1) mod p^2.

{eq(n,a)=lift(Mod(a,n^2)^eulerphi(n)-1 )/n %n};

We have the following logarithmic identities
eq(n,a*b)=eq(n,a)+eq(n,b) mod n (1)
eq(n,a^r)=r*eq(n,a) mod n (2)

Can generalization of these allow to work with
composite $n$ in $n$-adic integers?
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.