🔢 mathematics

Notes on the LVP and CVP in $p$ -adic Fields

Questo articolo propone un algoritmo in tempo polinomiale per risolvere i problemi del vettore più lungo e del vettore più vicino nei campi $p$ -adici, sfruttando le proprietà non archimedee e la struttura degli ordini massimali per costruire basi ortogonali efficienti.

Autori originali: Chi Zhang, Mingqian Yao

Pubblicato 2026-04-13

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Chi Zhang, Mingqian Yao

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

🌌 Il Mistero dei Numeri "P-adici": Una Caccia al Tesoro Matematica

Immagina di vivere in un mondo dove le regole della distanza sono completamente diverse da quelle a cui sei abituato. Nel nostro mondo normale (quello dei numeri reali), se cammini verso casa, ti avvicini gradualmente. Ma in questo mondo speciale, chiamato mondo p-adico, la distanza funziona come un albero genealogico o come una mappa di una città con strade a spirale: due punti possono sembrare lontani, ma se appartengono allo stesso "ramo" della storia, sono in realtà vicinissimi.

Gli autori di questo articolo, Chi Zhang e Mingqian Yao, hanno scoperto un modo per navigare in questo mondo strano e risolvere due grandi enigmi matematici: il Problema del Vettore più Lungo (LVP) e il Problema del Vettore più Vicino (CVP).

🏰 La Città Segreta: I Campi p-adici

Pensa ai numeri p-adici come a una città segreta costruita su un sistema di livelli.

I "p-adici": Sono come un modo di contare che usa un numero primo (chiamato p, come 2, 3, 5...) come base. Invece di contare 1, 2, 3, qui si contano in base a quanto un numero è divisibile per p.
La Geometria Strana: In questa città, la regola d'oro è: "Se due cose sono diverse, la loro somma è grande quanto la più grande delle due". È come se un elefante e un topo si unissero: il risultato è grande quanto l'elefante. Il topo non aggiunge nulla di significativo.

🕵️‍♂️ I Due Enigmi: LVP e CVP

In questa città, i matematici e i crittografi (quelli che inventano codici segreti) giocano a due giochi:

LVP (Il Vettore più Lungo): Immagina di avere un mucchio di bastoni (vettori) lanciati a caso. Devi trovare il bastone più lungo possibile. Nel mondo normale, questo è difficile. In questo mondo p-adico, sembra facile, ma solo se sai come guardare.
CVP (Il Vettore più Vicino): Immagina di essere perso in una foresta di alberi (i punti della rete). Hai un punto di riferimento (un bersaglio) e devi trovare l'albero della foresta che ti sta più vicino. Anche questo è difficile.

Per anni, si è pensato che questi giochi fossero così difficili da essere usati per creare codici di sicurezza inviolabili per internet (crittografia post-quantistica). Ma Zhang e Yao hanno detto: "Aspetta un attimo, abbiamo trovato la chiave per aprire la porta".

🔑 La Chiave Magica: Le Basi Ortogonali

Il segreto che gli autori hanno svelato è come costruire una mappa perfetta, chiamata "Base Ortogonale".

Immagina di entrare in una stanza piena di mobili disordinati (i vettori). È difficile capire quanto sono distanti tra loro. Ma se riesci a riorganizzare i mobili in modo che siano tutti perfettamente allineati lungo gli assi X, Y e Z (come gli angoli di una stanza), tutto diventa semplice.

In questo mondo p-adico, gli autori hanno trovato un metodo veloce (in tempo polinomiale, cioè molto rapido per un computer) per raddrizzare questi mobili.
Una volta che hai la "stanza dritta" (la base ortogonale), trovare il bastone più lungo o l'albero più vicino diventa un gioco da ragazzi. È come avere una bussola perfetta in una foresta nebbiosa.

🛠️ Come l'hanno fatto? (La Ricetta)

Hanno usato una ricetta matematica in tre passi:

Costruire la Fondazione: Hanno usato un algoritmo per trovare la struttura più solida del mondo (chiamata "ordine massimale"). È come trovare le fondamenta perfette di un edificio.
Trovare il "Seme" (Uniformizzatore): Hanno individuato un numero speciale che funge da "seme" per generare tutto il resto della città.
Disegnare la Mappa: Usando questo seme e una parte della città chiamata "campo residuo" (come un'immagine in miniatura della città), hanno costruito la loro mappa ortogonale.

💥 Il Colpo di Scena: I Codici Segreti sono a Rischio

Fino a poco tempo fa, si pensava che i sistemi di sicurezza basati su questi numeri p-adici fossero sicuri. Ma questo articolo dice: "Non lo sono più".
Se un hacker conosce la "ricetta" (il polinomio minimo che definisce la città), può usare questo nuovo metodo per risolvere gli enigmi LVP e CVP in pochi secondi. Questo significa che i sistemi di crittografia proposti recentemente per proteggere i dati nel futuro (anche contro i computer quantistici) potrebbero essere violati facilmente.

🚀 Cosa significa per il futuro?

Gli autori non si fermano qui. Dicono: "Ok, abbiamo rotto il lucchetto, ma come possiamo costruire una cassaforte che resista?"
La loro idea è cambiare le regole del gioco: invece di dare la mappa completa della città, dare solo un "oracolo" (un assistente che ti dice quanto è lontano un punto, ma senza dirti come è fatta la mappa). Se non si può vedere la struttura ortogonale, il problema rimane difficile.

In Sintesi

Zhang e Yao hanno scoperto che in un mondo matematico strano e affascinante (i campi p-adici), i problemi che sembravano essere i "cavalli di battaglia" per la sicurezza futura sono in realtà risolvibili molto velocemente, se si sa come costruire la mappa giusta. Hanno dimostrato che la sicurezza attuale è fragile, ma hanno anche indicato la strada per costruire sistemi più robusti in futuro.

È come se avessero scoperto che il muro di cinta di una fortezza aveva una porta nascosta, l'avessero aperta per mostrarlo a tutti, e ora stanno suggerendo come costruire un muro nuovo, senza porte nascoste, per il futuro.

Titolo: Note sul Problema del Vettore più Lungo (LVP) e sul Problema del Vettore più Vicino (CVP) nei Campi p-adici

1. Il Problema e il Contesto

Il lavoro si inserisce nell'intersezione tra la teoria dei numeri algebrica e la crittografia teorica, focalizzandosi sui problemi computazionali in geometria non archimedea, specificamente sui campi p-adici ( $\mathbb{Q}_p$ ).

Contesto: I problemi SVP (Shortest Vector Problem) e CVP (Closest Vector Problem), fondamentali per la sicurezza dei reticoli euclidei, sono stati generalizzati ai campi p-adici come LVP (Longest Vector Problem) e CVP.
Stato dell'arte: Questi problemi sono stati introdotti da Deng et al. (2018) come potenziali basi per schemi di crittografia a chiave pubblica e firme digitali resistenti al quantum. Tuttavia, la sicurezza di questi schemi è stata recentemente messa in discussione. Zhang (2025) ha dimostrato che algoritmi deterministici a tempo polinomiale possono risolvere l'LVP in campi totalmente ramificati, compromettendo la sicurezza degli schemi basati su reticoli p-adici con piccole estensioni residue.
Obiettivo: Questo studio mira a colmare il divario algoritmico fornendo un metodo generale a tempo polinomiale per risolvere LVP e CVP in qualsiasi campo p-adico specificato da un polinomio minimo, sfruttando la struttura degli ordini massimali e delle basi ortogonali.

2. Metodologia

Gli autori propongono un approccio algoritmico che combina l'algebra computazionale dei campi locali con la geometria dei reticoli p-adici. La metodologia si articola in tre fasi principali:

A. Calcolo dell'Ordine Massimale ( $O_K$ )
Dato un campo estensione $K = \mathbb{Q}_p(\theta)$ definito da un polinomio minimo, il primo passo è calcolare l'ordine massimale $O_K$ (l'anello degli interi algebrici di $K$ ).

Si parte da un ordine noto (es. $\mathbb{Z}_p[\theta]$ ).
Si utilizza l'algoritmo basato sul p-radicale ( $I_p$ ), definito come l'insieme degli elementi $x \in O$ tali che $x^m \in pO$ per qualche $m$ .
Attraverso iterazioni che coinvolgono il calcolo del nucleo di mappe di Frobenius e endomorfismi su $O/pO$, si espande l'ordine fino a raggiungere l'ordine massimale $O_K$ . Questo processo è garantito essere a tempo polinomiale (basato sugli algoritmi Round 2 e Round 4).

B. Costruzione della Base Ortogonale
Una volta ottenuto $O_K$ , si sfruttano le proprietà strutturali dei campi locali per costruire una base ortogonale:

Uniformizzante ( $\pi$ ): Si identifica un elemento di valore assoluto p-adico massimo nell'ideale radicale, che funge da uniformizzante del campo.
Base del Campo Residuo: Si calcola una base $s_1, \dots, s_f$ del campo residuo $k = O_K/\pi O_K$ (dove $f$ è il grado residuo).
Teorema di Decomposizione: Utilizzando il grado di ramificazione $e$ $e$ e il grado residuo $f$ $f$ (con $n=ef$), si dimostra che l'insieme $\{s_i \pi^j \mid 1 \le i \le f, 0 \le j \le e-1\}$ ${s_{i} π^{j} ∣ 1 \leq i \leq f, 0 \leq j \leq e - 1}$ forma una base ortogonale per $K$ $K$ su $\mathbb{Q}_p$ $Q_{p}$ .
- Proprietà chiave: In una base ortogonale, la norma di una somma è il massimo delle norme dei termini ( $|v+w| = \max(|v|, |w|)$ se le norme sono diverse), semplificando drasticamente i calcoli.

C. Risoluzione di LVP e CVP
Con una base ortogonale a disposizione, i problemi LVP e CVP diventano trivialisabili in tempo polinomiale:

LVP: Si cerca il vettore nel reticolo con la seconda norma massima. La struttura ortogonale permette di ordinare e ridurre i vettori di base in modo deterministico per isolare il vettore target.
CVP: Data una vettore target $t$ , si proietta $t$ sulla base ortogonale e si arrotonda i coefficienti per trovare il vettore del reticolo più vicino.
Gli algoritmi proposti (Algoritmi 1 e 2 nel testo) sono varianti efficienti di procedure di riduzione che sfruttano la disuguaglianza ultrametrica.

3. Contributi Chiave

Innovazione Algoritmica: Integrazione della ortogonalizzazione Gram-Schmidt p-adica con calcoli sui campi residui. Gli autori dimostrano che LVP e CVP sono risolvibili in tempo polinomiale (in $n$ e $\log p$ ) quando il campo è dato esplicitamente.
Validazione Pratica: Forniscono un esempio concreto su $K = \mathbb{Q}_2(\sqrt[3]{5})$ (definito da $X^3 - 3X^2 + 3X - 5$ ), mostrando passo dopo passo il calcolo dell'ordine massimale, dell'uniformizzante e della base ortogonale.
Caratterizzazione delle Norme: Nel Capitolo 7, gli autori caratterizzano matematicamente tutte le norme su spazi vettoriali su $\mathbb{Q}_p$ , dimostrando che ogni norma è determinata da una matrice invertibile e numeri reali positivi. Questo evidenzia che se la matrice di trasformazione è nota, la base ortogonale è facilmente recuperabile, rendendo la norma "insecure" in contesti crittografici se non protetta.

4. Risultati

Complessità: L'algoritmo completo per risolvere LVP e CVP ha complessità polinomiale rispetto alla dimensione del campo e al logaritmo del primo $p$ .
Impatto sulla Sicurezza: Il risultato dimostra che gli schemi crittografici basati su reticoli p-adici (come quelli proposti da Deng et al. nel 2021) sono insicuri se il campo p-adico è completamente specificato (tramite polinomio minimo). L'attacco è generale e non richiede condizioni speciali di ramificazione, a differenza di attacchi precedenti.
Vulnerabilità Fondamentale: Anche le contromisure che suggerivano l'uso di campi con grande grado residuo non sono sufficienti se l'ordine massimale e la struttura del campo sono noti.

5. Significato e Conclusioni

Questo lavoro ha implicazioni significative per la crittografia post-quantum:

Sfatare la sicurezza: Dimostra che la semplice generalizzazione dei problemi dei reticoli ai campi p-adici non garantisce la sicurezza se si utilizza la norma standard p-adica su un campo noto.
Nuove Direzioni di Ricerca: Suggerisce che per costruire schemi sicuri, è necessario:
1. Non fornire l'intero campo tramite un polinomio minimo, ma solo un oracolo per il calcolo della norma.
2. Garantire che la base ortogonale non sia deducibile dalla descrizione della norma (problema di caratterizzazione delle norme).
3. Investigare se esistono algoritmi polinomiali per trovare i parametri della norma (matrice $A$ e coefficienti $c_i$ ) quando la norma è data solo come oracolo.

In sintesi, il paper chiude il capitolo sulla sicurezza degli schemi basati su reticoli p-adici "nudi" e sposta la ricerca verso la definizione di nuove strutture di norma che nascondano efficacemente la geometria ortogonale sottostante.