Timeline for p-adic logarithms with fixed precision
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 11, 2021 at 3:48 | comment | added | MAS | @reuns, what do you mean by "the discrete logarithm in $(1+p \mathbb{Z})/(1+p^D \mathbb{Z})$ is a bit trivial" ? Do you mean its image under $p$-adic logarithm is $0$ ? | |
| May 27, 2021 at 14:00 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 27, 2021 at 12:40 | answer | added | joro | timeline score: 1 | |
| Apr 27, 2021 at 7:57 | history | edited | joro | CC BY-SA 4.0 |
added experimental support
|
| Apr 26, 2021 at 17:52 | comment | added | reuns | You get $n \bmod p^{D-r}$ not $n\bmod p^{D-1}$. Taking $g=1+p$ for $p$ odd then $r=1$. | |
| Apr 26, 2021 at 17:43 | comment | added | joro | @reuns I am asking about finding n mod p^(D-1), no matter about the p-adic algorithm. Is your answer solution to this too? | |
| Apr 26, 2021 at 16:58 | comment | added | reuns | No, the $p$-adic logarithm is defined only for $g\equiv 1\bmod p$, even if you can set $\log(g) = \frac1{p-1}\log(g^{p-1})$ for other $g\ne 0\bmod p$, which is the same as assuming $g\equiv 1\bmod p$. | |
| Apr 26, 2021 at 16:51 | comment | added | joro | @reuns You are misunderstanding. There are no constraints on $g$ and we checked hundreds of random g's. Added pari/gp code, which you can run online. Please check the code before claiming further constraints. | |
| Apr 26, 2021 at 16:48 | history | edited | joro | CC BY-SA 4.0 |
adding code due to comments
|
| Apr 26, 2021 at 15:59 | comment | added | reuns | A lot of misunderstandings in your question. $g$ must be $\equiv 1\bmod p$. $\log(g+O(p^D)) = \log(g)+O(P^D)$, $\log(g^n)=n\log(g)$ and for $D>r=v_p(\log g)$, $\frac{\log(g^n+O(p^D))}{\log( g+O(p^D))}=n+O(p^{D-r})$ where $r=v_p(g-1)$ if $p$ is odd, $r=\max(2,v_p(g-1))$ if $p=2$. It is not the most efficient algorithm to find $n$. The discrete logarithm in $(1+p\Bbb{Z})/(1+p^D\Bbb{Z})$ is a bit trivial. | |
| Apr 26, 2021 at 12:57 | history | asked | joro | CC BY-SA 4.0 |