Base di fattorizzazione

Una base di fattorizzazione è semplicemente un insieme di numeri primi distinti $ B = \{p_1, p_2, ..., p_N\} $ da utilizzare per fattorizzare i numeri.

In altre parole, i numeri primi nella base di fattorizzazione saranno gli unici che si considerano nella scomposizione dei numeri.

Esempio

Se scelgo la base $ B = \{2,3,5\} $, significa che mi interessano solo i numeri che si possono scrivere come prodotti di questi primi.

Con questa base posso scomporre in fattori primi il numero $ n = 30 = 2 \times 3 \times 5 $ o il numero $ n = 18 = 3^2 \times 2 $ ma non posso fattorizzare il numero $ n = 21 = 3 \times 7 $.

I numeri B-modulo n
Cos'è un B-vettore
La riduzione modulo 2

I numeri B-modulo n

Un numero è detto B-numero modulo n se si può scomporre con una base $ B $ nel modulo $ n $.

In parole povere, quando lo scompongo in fattori primi, compaiono solo i numeri della base $ B $.

Un esempio pratico

Considero il numero $ n = 77 $ come modulo e prendo come base $ B = \{7, 11\} $.

Poi cerco quali numeri possono essere scritti come combinazione dei fattori $ 7 $ e $ 11 $, cioè numeri della forma:

\[ 7^a \cdot 11^b \]

I numeri $ B $-modulo $ 77 $ sono tutte le combinazioni di $ 7^a \cdot 11^b $ ridotte modulo $ 77 $.

Ecco un elenco dei primi numeri:

$ 1 = 7^0 \cdot 11^0 $
$ 7 = 7^1 \cdot 11^0 $
$ 11 = 7^0 \cdot 11^1 $
$ 49 = 7^2 \cdot 11^0 $
$ 77 = 7^1 \cdot 11^1 $
$ 121 = 7^0 \cdot 11^2 $
$ 343 = 7^3 \cdot 11^0 $
$ 539 = 7^1 \cdot 11^2 $
$ 847 = 7^2 \cdot 11^1 $
$ 1331 = 7^0 \cdot 11^3 $
ecc.

Quindi, se un numero $ m $ modulo 77 ha solo fattori primi 7 e 11, allora è un $ B $-numero modulo 77.

Ad esempio $ m=49 $ è un $ B $-numero perché usa solo $ 7 $, che è nella base $ B $. \[ m = 49 \equiv 7^2 \pmod{77} \] D'altra parte $ m = 20 $ non è un $ B $-numero, perché contiene i primi $ 2 $ e $ 5 $, che non fanno parte della base $ B $. \[ m = 20 \equiv 2^2 \times 5 \pmod{77} \]

Poiché sto considerando i numeri modulo $ 77 $, posso ridurre ciascuno di questi numeri rispetto a $ 77 $. Ecco qualche esempio di riduzione:

\[ 1 \equiv 1 \mod 77 \]

\[ 7 \equiv 7 \mod 77 \]

\[ 11 \equiv 11 \mod 77 \]

\[ 49 \equiv 49 \mod 77 \]

\[ 121 \equiv 44 \mod 77 \]

\[ 343 \equiv 49 \mod 77 \]

\[ 1331 \equiv 14 \mod 77 \]

L'insieme dei residui modulo $ 77 $ formati da questi numeri è quindi $\{1, 7, 11, 49, 44, 14, \dots\} $.

Cos'è un B-vettore

Il $ B $-vettore di un numero $ m $ rispetto a una base di fattorizzazione $ B = \{p_1, p_2, ..., p_N\} $ è il vettore degli esponenti $(\alpha_1, \alpha_2, ..., \alpha_N)$ nella sua fattorizzazione modulo $ n $ $$ m \equiv p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_N^{\alpha_N} \pmod{n} $$

In altre parole, un numero $ m $ posso scriverlo come un prodotto di primi della base $ B $ nel modulo $ n $:

\[ m \equiv p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_N^{\alpha_N} \pmod{n} \]

Il $ B $-vettore di $ m $ è semplicemente il vettore degli esponenti $ (\alpha_1, \alpha_2, ..., \alpha_N) $.

Esempio

Considero la base di fattorizzazione $ B = \{2, 3, 5\} $ e un numero $ m = 18 $

\[ m = 18 = 2^1 \cdot 3^2 \cdot 5^0 \]

Il suo $ B $-vettore è:

\[ v(m) = (1, 2, 0) \]

Questo perché gli esponenti dei fattori primi sono 1, 2, 0 da sinistra verso destra.

La riduzione modulo 2

Dato un numero $ m \equiv p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_N^{\alpha_N} \pmod{n} $ la riduzione modulo 2 del suo vettore di esponenti $$ v(m) = ( \alpha_1, \alpha_2, \alpha_3 , ... , \alpha_N ) $$ consiste nel sostituire ogni esponente $ \alpha_i $ con il suo resto nella divisione per 2 $$ \beta_i \equiv \alpha_i \pmod{2} $$ trasformando così ogni valore pari in 0 e ogni valore dispari in 1 \[ w(m) = ( \beta_1, \beta_2, \beta_3, ... , \beta_N ) \]

In altre parole, per semplificare la rappresentazione di un B-vettore posso ridurlo al modulo 2.

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

In questo modo, se un esponente è pari viene sostiituito con lo zero (0), se è disperi con uno (1).

Il risultato è un nuovo B-vettore ridotto al modulo 2 contenente solo 0 e 1.

\[ w(m) = ( \beta_1, \beta_2, \beta_3, ... ) \]

Ma a cosa serve la riduzione modulo 2? Questa rappresentazione mi aiuta a individuare più facilmente se un numero è un quadrato perfetto nel modulo $ n $ oppure no. Se tutti gli esponenti nella fattorizzazione di $ b^2 $ sono pari, allora il numero $ m $ è un quadrato perfetto nel modulo $ n $.

Esempio

Ad esempio, considero il B-vettore del numero $ m = 18 = 2^1 \cdot 3^2 \cdot 5^0 $ nella base $ B = \{2, 3, 5\} $

\[ v(m) = (1, 2, 0) \]

Lo riscrivo in questa forma ridotta.

\[ w(m) = (1, 0, 0) \]

Questa forma è molto utile in alcune applicazioni pratiche. Ad esempio, mi permette di capire a colpo d'occhio se il numero $ m $ è un quadrato perfetto oppure no. In questo caso non lo è.

Viceversa, il numero $ m = 4 = 2^2 $ nella base $ B = \{2, 3, 5\} $ ha il seguente B-vettore

\[ v(m) = (2, 0, 0) \]

che ridotto in modulo 2 diventa

\[ w(m) = (0, 0, 0) \]

In questo caso $ m $ è un quadrato perfetto perché tutti gli esponenti sono pari.

Questa tecnica è fondamentale in applicazioni come la crittografia, la teoria dei numeri e gli algoritmi di fattorizzazione.

Del resto trovare un numero che sia un quadrato perfetto in una base data è un po’ come cercare parcheggio in centro: si può fare, ma bisogna avere molta pazienza. La riduzione modulo 2 aiuta a trovarlo più rapidamente.

E così via.