A Totient Function Associated with Variants of Groups

Titolo: Una funzione di Eulero associata alle varianti dei gruppi

Autore: James Renshaw (Università di Southampton)
Data: Marzo 2026
Ambito: Teoria dei Numeri, Crittografia, Teoria dei Gruppi e Semigruppi.

---

1. Il Problema e la Motivazione

Il paper nasce dalla necessità di sviluppare nuovi schemi crittografici basati sul problema del logaritmo discreto (DLP) in gruppi finiti, utilizzando le varianti di semigruppi (introdotte da Hickey e Chase).

• Contesto: In uno schema di crittografia standard, il testo cifrato è spesso definito come $c = g^e$. Un attacco a forza bruta richiede di testare tutti i possibili esponenti $e$ nel gruppo delle unità $U_n$, con complessità $O(\phi(n))$.
• L'approccio proposto: L'autore propone uno schema basato su una variante del gruppo $G_x = (G, *_x)$, dove l'operazione è definita come $a *_x b = a \cdot x \cdot b$. In questo contesto, il testo cifrato diventa $c = (gx)^{e-1}g$.
• La sfida: Un attacco a forza bruta su questo schema richiede di testare coppie $(y, f)$ dove $y \in G$ e $f \in U_n$, portando a una complessità di $O(n \cdot \phi(n)) \approx O(n^2)$, raddoppiando teoricamente la sicurezza.
• Il nodo critico: Esiste il rischio di "falsi positivi". Potrebbero esistere coppie distinte $(y, f) \neq (x, e)$ tali che $(gy)^{f-1} = (gx)^{e-1} = c$. Il numero di tali collisioni determina la sicurezza effettiva del sistema. Se questo numero è troppo alto, l'attacco diventa fattibile.

L'obiettivo principale del paper è definire e analizzare una nuova funzione di Eulero generalizzata, denotata come $T(n)$, che quantifica il numero minimo di tali collisioni (o soluzioni spurie) in un gruppo di ordine $n$.

---

2. Metodologia e Definizioni

Definizione della Funzione $T(n)$

L'autore definisce $T: \mathbb{N} \to \mathbb{N}$ come il numero di unità dispari $m \in \mathbb{Z}_n$ tali che anche $(m-1)/2$ sia un'unità in $\mathbb{Z}_n$. Formalmente:
$$T(n) = |\{1 \le m \le n \mid \gcd(m, n) = 1 \text{ e } \gcd((m-1)/2, n) = 1\}|$$
con la convenzione $T(1) = 0$.

Questa funzione è una generalizzazione di:

1. La funzione di Eulero classica $\phi(n)$.
2. La funzione di Schemmel $S_r(n)$ (introdotta nel 1869), che conta le sequenze di $r$ interi consecutivi coprimi a $n$. In particolare, l'autore utilizza $S(n) = S_2(n)$, che conta le coppie consecutive $(m, m+1)$ copime a $n$.

Strumenti Matematici

• Principio di Inclusione-Esclusione: Utilizzato per calcolare le cardinalità di insiemi definiti da condizioni di divisibilità e parità.
• Serie Binomiali: Impiegate per stimare le somme alternate nelle stime degli errori.
• Teoria dei Numeri Elementare: Analisi delle proprietà di congruenza modulo $p$ e $2p$, e studio delle soluzioni di equazioni diofantee lineari (es. $px = 1 + qy$) per determinare la parità delle soluzioni.
• Struttura dei Gruppi: Analisi delle varianti di gruppo $G_x$ e delle loro proprietà isomorfe rispetto al gruppo originale.

---

3. Risultati Principali e Teoremi

L'autore deriva formule esatte e limiti superiori/inferiori per $T(n)$ in base alla fattorizzazione di $n$.

Caso $n$ Dispari

• Teorema 2 (Caso Primo): Se $p$ è un primo dispari ed $e \ge 1$:
  $$T(p^e) = \frac{p^e - 2p^{e-1} - 1}{2} = \frac{S(p^e) - 1}{2}$$
• Teorema 3 (Caso Generale): Per un intero dispari $n > 1$ con $\omega$ fattori primi distinti, $T(n)$ è strettamente legato a $S(n)$:
  $$\left| T(n) - \frac{S(n) - 1}{2} \right| \le \frac{3^\omega - 2^{\omega+1} + 1}{2}$$
  Questo dimostra che $T(n)$ è approssimativamente la metà di $S(n)$, con un errore limitato che dipende dal numero di fattori primi.

Caso $n$ Pari

• Teorema 7: Per potenze di 2 ($e > 1$): $T(2^e) = 2^{e-2}$.
• Teorema 8: Se $n$ è dispari, $T(4n) = S(n)$.
• Teorema 9: Per $e > 2$, $T(2^e n) = 2^{e-2} S(n)$.
• Teorema 13: Per $n = 2m$ con $m$ dispari, si ottengono limiti simili al caso dispari, con una dipendenza dalla congruenza dei fattori primi di $m$ modulo 4.

Riassunto delle Formule Chiave

Se $n = 2^e m$ con $m$ dispari e $\omega$ fattori primi distinti:

1. Se $e \ge 2$: $T(n) = 2^{e-2} S(m)$.
2. Se $e = 1$: $T(n) \approx \frac{S(m)}{2}$ (con un errore di $\pm 1$ o $\pm 2$ a seconda di $\omega$ e dei valori modulo 4).
3. Se $e = 0$: $T(n) \approx \frac{S(m)}{2}$.

---

4. Applicazione Crittografica e Significato

Il Teorema di Sicurezza (Teorema 1 e 14)

Il risultato fondamentale è che per un gruppo finito $G$ di ordine $n$:

• Se $n$ è dispari, ci sono almeno $S(n)$ coppie $(y, f)$ che soddisfano l'equazione della variante.
• Se $n$ è pari, ci sono almeno $T(n)$ coppie.

Ciò significa che un attaccante che tenta un attacco a forza bruta non trova una sola soluzione corretta $(x, e)$, ma deve filtrare attraverso almeno $T(n)$ "falsi positivi".

Implicazioni per i Primi Sicuri (Safe Primes)

Nel caso specifico in cui $G = U_p$ con $p = 2q + 1$ (primo sicuro):

• Se $q \equiv 1 \pmod 4$, il numero di coppie è almeno $(p-3)/4$.
• Se $q \equiv 3 \pmod 4$, il numero di coppie è almeno $(p-7)/4$.

Significato:

1. Raddoppio della Sicurezza: L'uso delle varianti di gruppo raddoppia lo spazio delle chiavi da $O(n)$ a $O(n^2)$.
2. Gestione dei Falsi Positivi: La funzione $T(n)$ quantifica il "rumore" nel sistema. Per rendere il sistema sicuro, è necessario scegliere $n$ in modo che $T(n)$ sia sufficientemente grande da rendere il filtraggio dei falsi positivi computazionalmente proibitivo, ma non così grande da rendere il sistema inutilizzabile.
3. Nuove Direzioni: L'autore suggerisce che lo studio di funzioni generalizzate $T_r(n)$ (dove $(m-1)/r$ è un'unità) potrebbe portare a ulteriori varianti crittografiche.

5. Conclusione

Il paper introduce una nuova funzione aritmetica, $T(n)$, che collega la teoria dei numeri (generalizzazioni della funzione di Eulero e di Schemmel) alla sicurezza crittografica basata su varianti di gruppi.
I risultati principali includono:

• La definizione rigorosa e il calcolo di $T(n)$ per diverse classi di numeri interi.
• La dimostrazione che $T(n)$ è strettamente correlata alla funzione di Schemmel $S(n)$.
• La prova che l'uso di varianti di gruppo aumenta la complessità dell'attacco a forza bruta al quadrato, ma introduce un numero minimo di collisioni calcolabile tramite $T(n)$.

L'articolo conclude che, scegliendo opportunamente parametri (come primi sicuri), è possibile costruire sistemi crittografici robusti, pur rimanendo consapevoli della necessità di gestire le collisioni multiple intrinseche alla struttura algebrica delle varianti di gruppo.