Skip to main content
Bumped by Community user
added experimental support
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

Probably this is easy, but we would like to see it on paper.

Let $p$ be prime and $D,g,n$ positive integers.

Let $A=g^n \bmod p^D$.

Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$. In pari/gp notation: $\log(p,a,D)=$log(a+O(p^D)). $\log(p,a,D)$ is efficiently computable.

Define $dlog(p,g,A,D)=\frac{\log(p,A,D)}{\log(p,g,D)}$.

Is is true that $dlog(p,g,A,D) \bmod{p^{D-1}} = n \bmod{p^{D-1}}$?

We tested hundreds of large tuples for experimental support.

This might have some cryptography application for discrete logarithms modulo prime powers.

We are interested in the discrete logarithm of $A$ in base $g$.

For this reason we generated hundreds of tuples $p,g,D,n$ and the code below correctly computed $n \mod{p^{D-1}}$.

Comments suggest constraints on $g$ but the implementation works for arbitrary $g$.

Adding pari/gp code due to comments

You can run in it in a browser: https://pari.math.u-bordeaux.fr/gp.html

    /* discrete logarith modulo p^(D-1) 
    https://pari.math.u-bordeaux.fr/gp.html
    */
{
dlog1(p,g,a,D=2)=lift(log(lift(a)+O(p^D))/log(lift(g)+O(p^D)));
}

{
tt()=
D=2;
setrand(1);
p=nextprime(10^8);X0=random(p^D);g=Mod(2,p^D);a=g^X0;
X1=dlog1(p,g,a,D);
print([(X1-X0)%p^(D-1)]);
}
tt()

Probably this is easy, but we would like to see it on paper.

Let $p$ be prime and $D,g,n$ positive integers.

Let $A=g^n \bmod p^D$.

Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$. In pari/gp notation: $\log(p,a,D)=$log(a+O(p^D)). $\log(p,a,D)$ is efficiently computable.

Define $dlog(p,g,A,D)=\frac{\log(p,A,D)}{\log(p,g,D)}$.

Is is true that $dlog(p,g,A,D) \bmod{p^{D-1}} = n \bmod{p^{D-1}}$?

We tested hundreds of large tuples for experimental support.

This might have some cryptography application for discrete logarithms modulo prime powers.

Adding pari/gp code due to comments

You can run in it in a browser: https://pari.math.u-bordeaux.fr/gp.html

    /* discrete logarith modulo p^(D-1) 
    https://pari.math.u-bordeaux.fr/gp.html
    */
{
dlog1(p,g,a,D=2)=lift(log(lift(a)+O(p^D))/log(lift(g)+O(p^D)));
}

{
tt()=
D=2;
setrand(1);
p=nextprime(10^8);X0=random(p^D);g=Mod(2,p^D);a=g^X0;
X1=dlog1(p,g,a,D);
print([(X1-X0)%p^(D-1)]);
}
tt()

Probably this is easy, but we would like to see it on paper.

Let $p$ be prime and $D,g,n$ positive integers.

Let $A=g^n \bmod p^D$.

Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$. In pari/gp notation: $\log(p,a,D)=$log(a+O(p^D)). $\log(p,a,D)$ is efficiently computable.

Define $dlog(p,g,A,D)=\frac{\log(p,A,D)}{\log(p,g,D)}$.

Is is true that $dlog(p,g,A,D) \bmod{p^{D-1}} = n \bmod{p^{D-1}}$?

We tested hundreds of large tuples for experimental support.

This might have some cryptography application for discrete logarithms modulo prime powers.

We are interested in the discrete logarithm of $A$ in base $g$.

For this reason we generated hundreds of tuples $p,g,D,n$ and the code below correctly computed $n \mod{p^{D-1}}$.

Comments suggest constraints on $g$ but the implementation works for arbitrary $g$.

Adding pari/gp code due to comments

You can run in it in a browser: https://pari.math.u-bordeaux.fr/gp.html

    /* discrete logarith modulo p^(D-1) 
    https://pari.math.u-bordeaux.fr/gp.html
    */
{
dlog1(p,g,a,D=2)=lift(log(lift(a)+O(p^D))/log(lift(g)+O(p^D)));
}

{
tt()=
D=2;
setrand(1);
p=nextprime(10^8);X0=random(p^D);g=Mod(2,p^D);a=g^X0;
X1=dlog1(p,g,a,D);
print([(X1-X0)%p^(D-1)]);
}
tt()
adding code due to comments
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

Probably this is easy, but we would like to see it on paper.

Let $p$ be prime and $D,g,n$ positive integers.

Let $A=g^n \bmod p^D$.

Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$. In pari/gp notation: $\log(p,a,D)=$log(a+O(p^D)). $\log(p,a,D)$ is efficiently computable.

Define $dlog(p,g,A,D)=\frac{\log(p,A,D)}{\log(p,g,D)}$.

Is is true that $dlog(p,g,A,D) \bmod{p^{D-1}} = n \bmod{p^{D-1}}$?

We tested hundreds of large tuples for experimental support.

This might have some cryptography application for discrete logarithms modulo prime powers.

Adding pari/gp code due to comments

You can run in it in a browser: https://pari.math.u-bordeaux.fr/gp.html

    /* discrete logarith modulo p^(D-1) 
    https://pari.math.u-bordeaux.fr/gp.html
    */
{
dlog1(p,g,a,D=2)=lift(log(lift(a)+O(p^D))/log(lift(g)+O(p^D)));
}

{
tt()=
D=2;
setrand(1);
p=nextprime(10^8);X0=random(p^D);g=Mod(2,p^D);a=g^X0;
X1=dlog1(p,g,a,D);
print([(X1-X0)%p^(D-1)]);
}
tt()

Probably this is easy, but we would like to see it on paper.

Let $p$ be prime and $D,g,n$ positive integers.

Let $A=g^n \bmod p^D$.

Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$. In pari/gp notation: $\log(p,a,D)=$log(a+O(p^D)). $\log(p,a,D)$ is efficiently computable.

Define $dlog(p,g,A,D)=\frac{\log(p,A,D)}{\log(p,g,D)}$.

Is is true that $dlog(p,g,A,D) \bmod{p^{D-1}} = n \bmod{p^{D-1}}$?

We tested hundreds of large tuples for experimental support.

This might have some cryptography application for discrete logarithms modulo prime powers.

Probably this is easy, but we would like to see it on paper.

Let $p$ be prime and $D,g,n$ positive integers.

Let $A=g^n \bmod p^D$.

Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$. In pari/gp notation: $\log(p,a,D)=$log(a+O(p^D)). $\log(p,a,D)$ is efficiently computable.

Define $dlog(p,g,A,D)=\frac{\log(p,A,D)}{\log(p,g,D)}$.

Is is true that $dlog(p,g,A,D) \bmod{p^{D-1}} = n \bmod{p^{D-1}}$?

We tested hundreds of large tuples for experimental support.

This might have some cryptography application for discrete logarithms modulo prime powers.

Adding pari/gp code due to comments

You can run in it in a browser: https://pari.math.u-bordeaux.fr/gp.html

    /* discrete logarith modulo p^(D-1) 
    https://pari.math.u-bordeaux.fr/gp.html
    */
{
dlog1(p,g,a,D=2)=lift(log(lift(a)+O(p^D))/log(lift(g)+O(p^D)));
}

{
tt()=
D=2;
setrand(1);
p=nextprime(10^8);X0=random(p^D);g=Mod(2,p^D);a=g^X0;
X1=dlog1(p,g,a,D);
print([(X1-X0)%p^(D-1)]);
}
tt()
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

p-adic logarithms with fixed precision

Probably this is easy, but we would like to see it on paper.

Let $p$ be prime and $D,g,n$ positive integers.

Let $A=g^n \bmod p^D$.

Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$. In pari/gp notation: $\log(p,a,D)=$log(a+O(p^D)). $\log(p,a,D)$ is efficiently computable.

Define $dlog(p,g,A,D)=\frac{\log(p,A,D)}{\log(p,g,D)}$.

Is is true that $dlog(p,g,A,D) \bmod{p^{D-1}} = n \bmod{p^{D-1}}$?

We tested hundreds of large tuples for experimental support.

This might have some cryptography application for discrete logarithms modulo prime powers.