I B vettori nella fattorizzazione di un numero intero

Quando si scompone un numero in fattori primi, spesso è utile rappresentare questa fattorizzazione in modo strutturato, soprattutto se si lavora con algoritmi di fattorizzazione avanzati. Ed è qui che entra in gioco il concetto di B-vettore.

Cos’è un B-vettore?

Il B-vettore di un numero intero $m$ è un vettore che descrive la fattorizzazione di $m$ rispetto a una base di fattorizzazione $B$, cioè un insieme prestabilito di numeri primi. In termini semplici, possiamo scrivere $m$ come un prodotto di primi della base $B$, con gli esponenti corrispondenti: $$m \equiv p_1^{\alpha_1} p_2^{\alpha_2} \cdots  p_N^{\alpha_N} \pmod{n}$$

Dove:

• $p_1, p_2, ..., p_N$ sono i numeri primi nella base $B$
• $\alpha_1, \alpha_2, ..., \alpha_N$ sono gli **esponenti** di ciascun fattore primo nella fattorizzazione di $m$

Il B-vettore di $m$ è quindi la sequenza degli esponenti $(\alpha_1, \alpha_2, ..., \alpha_N)$.

Esempio pratico

In questo esempio prendo la base di fattorizzazione:

$$B = \{2, 3, 5\}$$

Poi scompongo il numero $m = 18$ in fattori primi usando la base di fattorizzazione B.

$$18 = 2^1 \cdot 3^2 \cdot 5^0$$

Il B-vettore del numero $m$ nella base di fattorizzazione $B = \{2, 3, 5\}$ sarà quindi:

$$v(m) = (1, 2, 0)$$

Dove ogni posizione nel vettore corrisponde all'esponente del numero primo corrispondente nella base $B$.

La riduzione modulo 2

Per semplificare ulteriormente un B-vettore e ottenere informazioni utili sulla natura del numero, è utile ridurre ridurre gli esponenti al modulo 2.

L’idea è semplice:

• Se un esponente è pari, lo sostituiamo con 0 perché il resto della divisione per due di un numero pari è sempre zero.
• Se un esponente è dispari, lo sostituiasco con 1, perché il resto della divisione per due di un numero dispari è sempre uno.

$$\beta_i \equiv \alpha_i \pmod{2}$$

Dove il nuovo vettore ottenuto, detto B-vettore ridotto modulo 2, sarà:

$$w(m) = (\beta_1, \beta_2, ..., \beta_N)$$

Esempio con riduzione modulo 2

Riprendo il numero $m = 18$ con la base di fattorizzazione $B = \{2, 3, 5\}$:

Il B-vettore del numero è

$$v(m) = (1, 2, 0)$$

Riduco ogni elemento modulo 2:

• $1 \pmod{2} = 1$
• $2 \pmod{2} = 0$
• $0 \pmod{2} = 0$

Quindi, il B-vettore di $m=18$ ridotto al modulo 2 ha queste componenti:

$$w(m) = (1, 0, 0)$$

A cosa serve la riduzione modulo 2?

Ora viene la parte interessante. Questa rappresentazione semplificata aiuta a individuare se un numero è un quadrato perfetto modulo $n$.

Un numero è un quadrato perfetto se, nella sua fattorizzazione, tutti gli esponenti sono pari.

questo significa che, in un B-vettore ridotto modulo 2, un numero sarà un quadrato perfetto se il suo B-vettore ridotto è composto solo da zeri.

Esempio con un quadrato perfetto

Considero il numero $m = 4$ nella base di fattorizzazione $B = \{2, 3, 5\}$.

$$4 = 2^2 3^0 5^0 = 2^2$$

Il B-vettore è:

$$v(m) = (2, 0, 0)$$

Lo riduco al modulo 2:

$$w(m) = (0, 0, 0)$$

Tutti gli elementi sono zeri, quindi $m$ è un quadrato perfetto.

Esempio con un numero che non è un quadrato perfetto

Riprendo il numero intero $m = 18$ nella base di fattorizzazione $B = \{2, 3, 5\}$.

$$18 = 2^1 3^2 5^0$$

Il suo B vettore nella base B è

$$v(m) = (1, 2, 0)$$

il cui B-vettore ridotto al modulo 2 è

$$w(m) = (1, 0, 0)$$

In questo caso nel B-vettore ridotto c’è almeno un 1, quindi posso già dedurre che il numero 18 non è un quadrato perfetto.

Perché il B-vettore e la riduzione modulo 2 sono importanti? Questa tecnica è fondamentale in applicazioni avanzate come negli algoritmi di fattorizzazione quadratici (es. il metodo di Kraitchik), negli algoritmi di crittografia basati sulla difficoltà della fattorizzazione e nella teoria dei numeri per studiare proprietà dei numeri e delle loro radici quadratiche modulo $n$.

E così via.