<p>De, Kurur, Saha and Saptharishi gave a modular version of Fürer's integer multiplication algorithm in their paper <a href="http://arxiv.org/pdf/0801.1416.pdf">Fast integer multiplication using modular arithmetic</a>, in which the p-adic numbers replace the complex numbers used by Fürer. Both algorithms give the best bit-complexity for integer multiplication.</p>

CC BY-SA 3.0
2014-10-26T04:51:27.703Z
This is Good example.
Turbo
CC BY-SA 3.0
2014-10-24T01:08:39.843Z
2014-10-24T01:08:39.843Z
Yuval Filmus
<p><a href="http://en.wikipedia.org/wiki/Hensel%27s_lemma">Hensel lifting</a> is very closely related to the $p$-adics: it's basically getting a better and better approximation to a $p$-adic number, "better" in the sense of "closer in the $p$-adic valuation. Hensel lifting is used in many algorithms such as factoring polynomials or doing linear algebra over $\mathbb{Z}$ (if I recall correctly Dixon has a paper on the latter).</p>

CC BY-SA 3.0
2014-10-26T04:52:15.180Z
From polynomials in $\Bbb Z_p[x]$, we cannot say anything about representation in $\Bbb R[x]$. Right?
Turbo
CC BY-SA 3.0
2014-10-26T13:52:34.640Z
@J.A: Unlikely (I assume here by $\mathbb{Z}_p$ you mean the $p$-adic integers). Perhaps some relationship between $\mathbb{Q}_p[x]$ and $\mathbb{R}[x]$ (especially if one considers questions over all $p$) or between $\mathbb{Z}_p[x]$ and $\mathbb{Z}[x]$... See the Hasse principle: http://en.wikipedia.org/wiki/Hasse_principle
Joshua Grochow
CC BY-SA 3.0
2014-10-26T17:14:48.310Z
yes the $p$-adic integers.
Turbo
CC BY-SA 3.0
2014-10-26T17:16:53.583Z
Has the relation between $\Bbb Q_p[x]$ and $\Bbb R[x]$ been ever used? say in size of circuits and polynomials and rational functions or rank in communication complexity?
Turbo
CC BY-SA 3.0
2014-10-26T20:31:37.963Z
@J.A: I don't know - if you find a use or a reference to a use, please let us know!
Joshua Grochow
CC BY-SA 3.0
2014-10-24T00:59:43.160Z
2014-10-24T00:59:43.160Z
Joshua Grochow
<p>There are also some computational models:</p>

<p><a href="http://www.easychair.org/publications/?page=1530293881">Here is the first paper:</a> Rusins Freivalds: Ultrametric automata and Turing machines. Turing-100 2012: 98-112</p>

CC BY-SA 3.0
2014-10-26T09:54:19.727Z
2014-10-26T09:54:19.727Z
Abuzer Yakaryilmaz
<p>here is a nice general survey with a brief overview of diverse (recent) CS applications for <em>p</em>-adic theory, p3</p>

<p><a href="http://www.asiapacific-mathnews.com/03/0304/0001_0006.pdf" rel="noreferrer">What are p-Adic Numbers? What are They Used for?</a> / Rozikov</p>

<blockquote>
  <p>Here are areas where p-adic dynamics proved to be effective: computer science (straight line programs), numerical analysis and simulations (pseudorandom numbers), uniform distribution of sequences, cryptography (stream ciphers, T- functions), combinatorics (Latin squares), automata theory and formal languages, genetics. The monograph [9] contains the corresponding survey. For a newer results see recent papers and references therein: [10, 14, 15, 28, 36, 37, 38, 48, 51]. Moreover, there are studies in computer science and cryptography which along with mathematical physics stimulated in 1990th intensive research in p-adic dynamics since it was observed that major computer instructions (and therefore programs composed of these instructions) can be considered as continuous transformations with respect to the 2-adic metric, see [11, 12].</p>
</blockquote>

CC BY-SA 3.0
2014-10-26T04:53:42.130Z
Interesting. where in straight line programs is it used?
Turbo
CC BY-SA 3.0
2014-10-26T04:56:01.347Z
Also these dont seem mainstream work.
Turbo
CC BY-SA 3.0
2014-10-25T17:33:20.287Z
2014-10-25T17:33:20.287Z
vzn
<p>Are there any concrete (or a rich source of) examples of application of $p$-adic numbers in computer science?</p>

CC BY-SA 3.0
2014-10-25T17:19:31.440Z
[_p_-adic number](http://www.wikipedia.org/wiki/P-adic_number) / Wikipedia. used in number theory. somewhat indirect, eg there is some analysis of the Collatz conjecture via _p_-adic theory & Collatz is considered by some to be deeply connected to TCS undecidability research.
vzn
<survey>
Applications of $p$-adic numbers in CS
Turbo
# Applications of $p$-adic numbers in CS

(Asked by: username_0 on 2014-10-23)

Are there any concrete (or a rich source of) examples of application of $p$-adic numbers in computer science?

**Tags:** survey
> **Comments:**
> **username_1**: [_p_-adic number](http://www.wikipedia.org/wiki/P-adic_number) / Wikipedia. used in number theory. somewhat indirect, eg there is some analysis of the Collatz conjecture via _p_-adic theory & Collatz is considered by some to be deeply connected to TCS undecidability research.  

---

## 4 answers

### Answer by username_2 on 2014-10-24. Score: 16

De, Kurur, Saha and Saptharishi gave a modular version of Fürer's integer multiplication algorithm in their paper [Fast integer multiplication using modular arithmetic](http://arxiv.org/pdf/0801.1416.pdf), in which the p-adic numbers replace the complex numbers used by Fürer. Both algorithms give the best bit-complexity for integer multiplication.

> **Comments:**
> **username_0**: This is Good example.  

---

### Answer by username_3 on 2014-10-24. Score: 10

[Hensel lifting](http://en.wikipedia.org/wiki/Hensel%27s_lemma) is very closely related to the $p$-adics: it's basically getting a better and better approximation to a $p$-adic number, "better" in the sense of "closer in the $p$-adic valuation. Hensel lifting is used in many algorithms such as factoring polynomials or doing linear algebra over $\mathbb{Z}$ (if I recall correctly Dixon has a paper on the latter).

> **Comments:**
> **username_0**: From polynomials in $\Bbb Z_p[x]$, we cannot say anything about representation in $\Bbb R[x]$. Right?  
> **username_3**: @J.A: Unlikely (I assume here by $\mathbb{Z}_p$ you mean the $p$-adic integers). Perhaps some relationship between $\mathbb{Q}_p[x]$ and $\mathbb{R}[x]$ (especially if one considers questions over all $p$) or between $\mathbb{Z}_p[x]$ and $\mathbb{Z}[x]$... See the Hasse principle: http://en.wikipedia.org/wiki/Hasse_principle  
> **username_0**: yes the $p$-adic integers.  
> **username_0**: Has the relation between $\Bbb Q_p[x]$ and $\Bbb R[x]$ been ever used? say in size of circuits and polynomials and rational functions or rank in communication complexity?  
> **username_3**: @J.A: I don't know - if you find a use or a reference to a use, please let us know!  

---

### Answer by username_4 on 2014-10-26. Score: 7

There are also some computational models:

[Here is the first paper:](http://www.easychair.org/publications/?page=1530293881) Rusins Freivalds: Ultrametric automata and Turing machines. Turing-100 2012: 98-112


---

### Answer by username_1 on 2014-10-25. Score: 6

here is a nice general survey with a brief overview of diverse (recent) CS applications for *p*-adic theory, p3

[What are p-Adic Numbers? What are They Used for?](http://www.asiapacific-mathnews.com/03/0304/0001_0006.pdf) / Rozikov

> Here are areas where p-adic dynamics proved to be effective: computer science (straight line programs), numerical analysis and simulations (pseudorandom numbers), uniform distribution of sequences, cryptography (stream ciphers, T- functions), combinatorics (Latin squares), automata theory and formal languages, genetics. The monograph [9] contains the corresponding survey. For a newer results see recent papers and references therein: [10, 14, 15, 28, 36, 37, 38, 48, 51]. Moreover, there are studies in computer science and cryptography which along with mathematical physics stimulated in 1990th intensive research in p-adic dynamics since it was observed that major computer instructions (and therefore programs composed of these instructions) can be considered as continuous transformations with respect to the 2-adic metric, see [11, 12].

> **Comments:**
> **username_0**: Interesting. where in straight line programs is it used?  
> **username_0**: Also these dont seem mainstream work.  

---

