Приложения -адических чисел в CS

11

Существуют ли конкретные (или богатые источники) примеры применения -адических чисел в информатике? $p$

survey Т ....
источник

р -адический номер / Википедия. используется в теории чисел. несколько косвенный, например, есть некоторый анализ гипотезы Коллатца с помощью p- адической теории, и некоторые считают, что Коллатц глубоко связан с исследованием неразрешимости TCS.

ВЗН

13

Де, Курур, Саха и Саптариши дали модульную версию алгоритма умножения целых чисел Фюрера в своей статье Быстрое целочисленное умножение с использованием модульной арифметики , в которой p-адические числа заменяют комплексные числа, используемые Фюрером. Оба алгоритма дают лучшую битовую сложность для целочисленного умножения.

Юваль Фильмус
источник

Это хороший пример.

T ....

10

Hensel лифтинг очень тесно связан с -adics: это в основном становится лучше и лучше приближения к -адического числу, «лучше» в смысле «ближе к -адического оценки Hensel лифтинг используется во многих алгоритмах. такие как факторинг полиномов или выполнение линейной алгебры над (если я правильно помню, у Диксона есть статья о последнем). $p$ $p$ $p$ $\mathbb{Z}$

Джошуа Грохов
источник

Из полиномов в мы ничего не можем сказать о представлении в . Правильно?

Z_{p} [x]

$\Bbb Z_p[x]$

R [x]

$\Bbb R[x]$

T ....

1

@JA: маловероятно (я предполагаю, что здесь вы подразумеваете -адические целые числа). Возможно, существует некоторая связь между и (особенно если рассматривать вопросы по всем ) или между и ... См. принцип Хассе: en.wikipedia.org/wiki/Hasse_principle

Z_{p}

$\mathbb{Z}_p$

p

$p$

Q_{p} [x]

$\mathbb{Q}_p[x]$

R [x]

$\mathbb{R}[x]$

p

$p$

Z_{p} [x]

$\mathbb{Z}_p[x]$

Z [x]

$\mathbb{Z}[x]$

Джошуа Грохов

да -адические целые числа.

p

$p$

Т ....

Была ли когда-нибудь использована связь между и ? скажем, по размеру цепей и полиномов и рациональных функций или ранг по сложности связи?

Q_{p} [x]

$\Bbb Q_p[x]$

R [x]

$\Bbb R[x]$

Т ....

@JA: я не знаю - если вы найдете использование или ссылку на использование, пожалуйста, дайте нам знать!

Джошуа Грохов

6

Есть также несколько вычислительных моделей:

Вот первая статья : Rusins Freivalds: Ультраметрические автоматы и машины Тьюринга. Тьюринг-100 2012: 98-112

Абузер Якарылмаз
источник

4

Вот хороший общий обзор с кратким обзором разнообразных (недавних) приложений CS для p -адической теории, p3

Что такое р-адические числа? Для чего они используются? / Розиков

Вот области, где p-адическая динамика оказалась эффективной: информатика (программы с прямыми линиями), численный анализ и моделирование (псевдослучайные числа), равномерное распределение последовательностей, криптография (потоковые шифры, T-функции), комбинаторика (латинские квадраты) , теория автоматов и формальные языки, генетика. Монография [9] содержит соответствующий обзор. Более новые результаты см. В недавних статьях и ссылках в них: [10, 14, 15, 28, 36, 37, 38, 48, 51]. Кроме того, существуют исследования в области компьютерных наук и криптографии, которые наряду с математической физикой стимулировали в 1990-х годах интенсивные исследования p-адической динамики, поскольку было отмечено, что основные компьютерные инструкции (и, следовательно, программы, составленные из этих инструкций) могут рассматриваться как непрерывные преобразования в отношении 2-адической метрике см. [11, 12].

ВЗН
источник

Интересно. где в программах прямой линии это используется?

T ....

1

Также они не кажутся основной работой.

T ....

Приложения -адических чисел в CS

Ответы: