Il pdf con l’intero articolo ( con alcune cose in più ) e’ raggiungibile qui: legno (pdf)
Sebbene le successioni sono oggetti matematici molto antichi, ancora oggi si scoprono nuove caratteristiche riguardo ad esse e studi approfonditi possono ancora essere svolti.
Tutti noi conosciamo almeno per nome la Successione di Fibonacci. Tale successione e’ costruita calcolando l’n-esimo termine come somma dell’n-1-esimo più l’n-2-esimo. Partendo dalla coppia generatrice (1,1) si ha quindi che i primi termini della Successione di Fibonacci valgono:
F = 1,1,2,3,5,8,13,21,34,55,89….
Generalizzazioni in cui si sommano tutti gli n termini precedenti (Trinacci, Tetranacci, n-acci…) sono già state studiate. Noi invece ci soffermiamo su un’altra famiglia di Successioni generalizzate di Fibonacci dove a sommarsi sono l’ultimo termine insieme all’(n-i)-esimo dove i e’ il numero di 1 iniziali che generano tali Successioni. Si può dunque avere per
i=2: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946 …
i=3: 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278 …
i=4: 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181, 250, 345 …
i=5: 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 20, 26, 34, 45, 60, 80, 106, 140 …
I due casi estremi per i=1 e i-> infinito sono particolari:
il caso i=1 e’ particolare nel senso che se l’n-esimo termine è la somma del precedente con se stesso allora i numeri di tale successione altro non sono che le potenze di 2.
i=1: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576 …
Per nostra comodità ci riferiremo a tali successioni sia considerando tutti gli 1 iniziali, sia considerando solo i numeri dopo tali sequenze di 1.
Se i → +infinito e non si considerano gli infiniti 1 di tale serie allora la Successione è esattamente l’insieme dei numeri naturali N.
Tutti avranno sentito parlare della sezione aurea. E’ un numero magnifico che troviamo in natura spessissimo, ad esempio come rapporto tra la distanza delle venatura di una foglia, o la relativa spirale aurea nelle conchiglie e in tanti altri casi. Tale numero vale 1.6180339887 = φ … ed è connesso con la Successione di Fibonacci perchè il rapporto tra due numeri consecutivi di tale successione approssima proprio la sezione aurea.
E se ci fossero numeri analoghi per le nostre successioni?
Per i due casi estremi i=1 e i → infinito e’ facile.
Per i = 1 il rapporto e’ 2
per i → infinito sia ha i / i-1 che quindi → 1+
Tutti gli altri quindi si troveranno in questo intervallo (2;1(
Per Fibonacci abbiamo già nominato la sezione aurea quindi
ri=2 (rapporto) = 1.618 … per gli altri valori invece:
ri=3 = 1.4656 …
ri=4 = 1.3802 …
ri=5 = 1.3247 …
ri=6 = 1.2851 …
ri=7 = 1.2554 …
ri=8 = 1.2320 …
ri=9 = 1.2131 …
…
Partiamo da alcune proprietà della sezione aurea per capire se almeno alcune di queste infinite altre costanti le hanno:
Tra le proprietà interessanti della sezione aurea citiamo le seguenti:
E’ un numero di Pisot. *
E’ la soluzione reale dell’equazione x2-x-1=0
E’ esprimibile come radice di (uno più radice di (uno più radice di …))
*Cosa è un numero di Pisot?
Un numero di Pisot è un numero algebrico a tale che e’ un numero algebrico soluzione di una equazione a coefficienti interi e deve inoltre valere che i coniugati di Galois sono in valore assoluto minori di uno. Si definiscono coniugati di Galois tutte le soluzioni del polinomio minimo di un certo numero algebrico dove con polinomio minimo si indica il polinomio monico di grado minore la cui soluzione reale è tale numero algebrico preso in considerazione.
Esistono inoltre i “piccoli” numeri di Pisot e con tale dicitura si indicano tutti quei numeri di Pisot minori della sezione aurea. Se ne sono trovati 38 e il piu’ piccolo e’ definito “Costante di plastica” e vale 1.3247 …
ma non lo abbiamo già visto questo numero? E’ proprio la costante che si ottiene per i=4!
Vediamo altri numeri di Pisot, piccoli ancora. Il secondo piu’ piccolo e’ 1.3802 … anch’esso rapporto di una nostra funzione!
Ci si chiede come si puo’ verificare se altre costanti sono numeri di Pisot e, magari, trovare un nuovo “piu’ piccolo numero di Pisot”
A riguardo vi è una dimostrazione ad opera di Siegel del 1944 raggiungibile a [1]
Cosa può tornare utile per tale congettura?
Prima abbiamo enunciato tra le tante proprietà della sezione aurea quella di essere soluzione di x2-x-1 = 0
E inoltre noto che la costante di plastica e’ soluzione di
x3-x-1 = 0
tale equazione e’ il polinomio minimo di un altra equazione:
x5-x4-1=0
in generale si capisce facilmente che tutte le costanti trovate come rapporto di due termini successivi della famiglia di successioni prese in considerazione sono le soluzioni di una famiglia di equazioni tutte della forma
xi-xi-1-1=0
dove i e’ pari al numero di 1 iniziali
Congettura: se si dimostra l’irriducibilità di un polinomio del tipo xi-xi-1-1 o si trova il relativo polinomio minimo e si verifica che l’insieme delle soluzioni, esclusa la costante presa in considerazione relativa a tale equazione, contenga solo numeri minori di uno in valore assoluto, allora tale costante e’ un numero di Pisot.
Tale congettura e’ verificata nei casi in cui i=2,3,4,5 e se fosse vera anche per un i >= 6 allora si troverebbe un numero più piccolo della costante plastica 1.3237…
Ritornando alla dimostrazione di Siegel, essa si basa sulle seguenti considerazioni:
Sia S l’insieme dei numeri di Pisot
Sia θ un intero algebrico e si assuma che tutti i suoi coniugati escluso θ siano in valor assoluto minore di 1
Data una dimostrazione di Salem che prova come θ =1 sia un punto isolato in S, tale asserzione implica che esista un altro θ > 1 anch’esso isolato.
Un punto isolato P è un punto che non ne ha altri “vicini”, ovvero esiste un ε scelto tale che l’intervallo ( P+ε ; P-ε ) non contiene altri punti. E questo e’ verificato per le nostre costanti, poiché ε possiamo sceglierlo arbitrariamente e basta che sia ε minore della differenza di due costanti successive.
Ritengo che nella dimostrazione di Siegel vi sia una mancanza. Ha utilizzato alcune funzioni generatrici le cui soluzioni sono numeri di Pisot ma non si e’ accorto che alcune di queste equazioni avevano la proprietà di essere del tipo xi-xi-1-1=0. Inoltre Siegel ha identificato il numero di plastica come il più piccolo perchè è il minore che ha calcolato utilizzando delle equazioni con la particolarità che più il grado aumentava più la soluzione reale si avvicinava al punto di accumulazione 1,618 … . Invece le costanti che abbiamo trovato noi le abbiamo calcolate utilizzando delle equazioni che al crescere del grado restituiscono una soluzione reale sempre più vicina a 1.
Per comodità potremmo chiamare tali numeri, che siano di Pisot o meno (visto che sebbene abbiano in comune praticamente tutte le proprietà di tali numeri, ancora bisogna verificare l’irriducibilità delle equazioni associate) numeri “di legno”: mi sembra adeguato come nome dato che si passa dalla costante aurea al numero di plastica e i seguenti, appunto “di legno”.
– CRITTOGRAFIA e i numeri di Fibonacci
Recentemente si e’ iniziato ad utilizzare le curve ellittiche in crittografia. A parità di lunghezza della chiave utilizzare tali curve permette di accorciare moltissimo i tempi di generazione delle chiavi e di calcolo degli algoritmi.
Una curva ellittica e’ una curva definita da una equazione, detta di Weierstrass della forma y2 = x3 +ax +b
L’insieme delle soluzioni di tale equazioni sono ovviamente tutti i punti che compongono la curva e in crittografia possiamo utilizzare questi punti, ad esempio, per scegliere una chiave pubblica e una chiave privata.
Chiaramente, alcuni punti saranno più adatti di altri: essendoci infiniti punti alcuni saranno razionali e altri irrazionali, ovvero i primi siamo in grado di rappresentarli tramite coordinate razionali.
Definendo una curva ellittica definiamo anche delle operazioni che possiamo svolgere su di esse. Di nostro interesse e’ la moltiplicazione di un punto.
Dato P un punto che appartiene alla curva ellittica E, possiamo calcolare 2P trovando l’intersezione tra la tangente alla curva in P e la curva stessa, e scegliendo il punto simmetrico a quello trovato come soluzione del problema. Per trovare un punto come nP basterà iterare il processo n volte.
Nella crittografia ellittica questo viene utilizzato per la scelta delel chiavi. Un utente A in particolare deve:
Scegliere un punto P che appartiene alla curva
Scegliere un intero k
Calcolare P* = kP
P* sara’ la chiave pubblica di A mentre k sara’ la sua chiave privata.
Tutto ovviamente puo’ essere implementato in una aritmetica modulare su un campo Fn o ancora meglio, Fp con p un numero primo.
Approfondendo l’argomento in rete mi sono imbattuto in alcuni altri documenti dove venivano mostrati diversi punti razionali sulle curve ellittiche ( [3] e [4] e in particolare [4] perchè l’intuizione degli studenti si avvicina a quello trattato in queste pagine ma in maniera incompleta: parlano di potenze di due e Fibonacci senza accorgersi che di fatto sono due successioni di una grande famiglia di serie)
Conseguenze possibili su un collegamento tra tali punti e i valori delle successioni presentate potrebbe avere un impatto sulla crittografia ellittica: due prime ipotesi che si possono fare sono che 1) potrebbe essere possibile restringere i valori da verificare nel caso si volesse eseguire un attacco di forza bruta 2) potrebbe (molto difficilmente ma non si puo’ mai sapere!) essere possibile trovare un collegamento diretto tra tali valori, i coefficienti della curva utilizzata e le chiavi per risalire in qualche modo dalla chiave pubblica a quella privata e quindi “rompere” la crittografia ECC.
RIFERIMENTI:
[1] Duke Math. J. Volume 11, Number 3 (1944), 597-602. Algebraic integers whose conjugates lie in the unit circle . Carl Ludwig Siegel Purtroppo è accessibile solo la prima pagina all’indirizzo
https://projecteuclid.org/euclid.dmj/1077472667#ui-tabs-1
[3] Crittosistemi basati su Curve Ellittiche
http://www.di.unisa.it/professori/ads/corso-security/www/CORSO-0001/ECC/index.htm
[4] Congettura sulle curve ellittiche con punti razionali connessi ai numeri di Fibonacci.
Per discussioni e commenti potete scrivermi all’indirizzo email matteopapa93[at]gmail[dot]com 😀
