Georgi Guninski on Sat, 11 Feb 2023 14:31:35 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

n-adic logarithms for composite n using Euler quotient.

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?