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.
