Applications des nombres

11

Existe-t-il des exemples concrets (ou une riche source) d'application des nombres -adiques en informatique? $p$

survey T ....
la source

p -adic number / Wikipedia. utilisé dans la théorie des nombres. quelque peu indirect, par exemple il y a une certaine analyse de la conjecture de Collatz via lathéorie p -adique et Collatz est considéré par certains comme profondément lié à la recherche sur l'indécidabilité du TCS.

vzn

13

De, Kurur, Saha et Saptharishi ont donné une version modulaire de l'algorithme de multiplication des nombres entiers de Fürer dans leur article Multiplication des nombres entiers rapides en utilisant l'arithmétique modulaire , dans laquelle les nombres p-adiques remplacent les nombres complexes utilisés par Fürer. Les deux algorithmes donnent la meilleure complexité en bits pour la multiplication d'entiers.

Yuval Filmus
la source

C'est un bon exemple.

T ....

10

Le levage de Hensel est très étroitement lié aux -adiques: il obtient essentiellement une meilleure et meilleure approximation d'un nombre -adique, "meilleur" dans le sens de "plus proche dans l' évaluation -adique. Le levage de Hensel est utilisé dans de nombreux algorithmes comme factoriser des polynômes ou faire de l'algèbre linéaire sur (si je me souviens bien, Dixon a un papier sur ce dernier). $p$ $p$ $p$ $\mathbb{Z}$

Joshua Grochow
la source

A partir des polynômes de , nous ne pouvons rien dire sur la représentation dans . Droite?

Z_{p} [x]

$\Bbb Z_p[x]$

R [x]

$\Bbb R[x]$

T ....

1

@JA: Peu probable (je suppose ici par vous voulez dire les entiers -adiques). Peut-être une relation entre et (surtout si l'on considère les questions sur tout ) ou entre et ... Voir le principe de Hasse: 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]$

Joshua Grochow

oui les entiers -adiques.

p

$p$

T ....

La relation entre et elle déjà été utilisée? disons dans la taille des circuits et des polynômes et des fonctions rationnelles ou rang dans la complexité de la communication?

Q_{p} [x]

$\Bbb Q_p[x]$

R [x]

$\Bbb R[x]$

T ....

@JA: Je ne sais pas - si vous trouvez une utilisation ou une référence à une utilisation, faites-le nous savoir!

Joshua Grochow

6

Il existe également des modèles de calcul:

Voici le premier article: Rusins Freivalds: automates ultramétriques et machines de Turing. Turing-100 2012: 98-112

Abuzer Yakaryilmaz
la source

4

voici une belle étude générale avec un bref aperçu des diverses applications (récentes) de CS pour la théorie p -adique, p3

Que sont les nombres p-adiques? Pour quoi sont-ils utilisés? / Rozikov

Voici des domaines où la dynamique p-adique s'est avérée efficace: informatique (programmes en ligne droite), analyse numérique et simulations (nombres pseudo-aléatoires), distribution uniforme des séquences, cryptographie (chiffrement de flux, fonctions T), combinatoire (carrés latins) , théorie des automates et langages formels, génétique. La monographie [9] contient l'enquête correspondante. Pour des résultats plus récents, voir les articles et références récents: [10, 14, 15, 28, 36, 37, 38, 48, 51]. De plus, il existe des études en informatique et en cryptographie qui, avec la physique mathématique, ont stimulé dans les années 1990 des recherches intensives en dynamique p-adique car il a été observé que les principales instructions informatiques (et donc les programmes composés de ces instructions) peuvent être considérées comme des transformations continues dans le respect à la métrique 2-adique, voir [11, 12].

vzn
la source

Intéressant. où dans les programmes en ligne droite est-il utilisé?

T ....

1

Ces travaux ne semblent pas non plus courants.

T ....

Applications des nombres

Réponses: