Loading
Note di Apprendimento
Study Reminders
Support
Text Version

Introduzione ai gruppi ciclici

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Fondamenti di Cryptography Prof. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bangalore Lecture - 38 Gruppi ciclici Ciao a tutti. Benvenuti a questa lezione. (Riferimento Slide Time: 00.30) Il piano per questa lezione è il seguente. In questa lezione introdurremo il concetto di gruppi ciclici. Vedrete varie definizioni e proprietà e il motivo per cui siamo interessati a studiare i gruppi ciclici è che in seguito introdurremo alcune ipotesi di durezza crittografica nell'ambito dei gruppi ciclici che ci aiuteranno ulteriormente a progettare o sviluppare le idee di base utilizzate per progettare il protocollo di scambio delle Diffie – Hellman. (Riferimento Slide Time: 01 :00) Quindi ricordate l'abstract Diffie – Hellman key Exchange Protocol che abbiamo spiegato ipotizzando che abbiamo alcune funzioni speciali E e F. Solo per ricordare quale esattamente il requisito dalla funzione E e F erano, beh abbiamo bisogno delle seguenti proprietà: abbiamo bisogno che quella funzione E sia facile da compattare per qualsiasi input. Abbiamo anche bisogno che se ci viene fornito qualsiasi α dal dominio di E e una funzione output E (β), poi senza conoscere il valore β dovrebbe essere facile calcolare il valore della funzione F sulla coppia di input (α β) e questo dovrebbe tenere per qualsiasi (α, β). Se si desidera ottenere una privacy debole allora la proprietà che richiediamo qui dalla funzione E e F è quella per ogni casuale (α β) dovrebbe essere difficile da calcolare a valore di F (α, β) se hai appena dato il valore di E (α) e E (β). Mentre per la forte privacy abbiamo bisogno che il valore di F (α, β) deve essere computazionalmente indistinguibile da qualsiasi valore casuale dal co - dominio anche se si conosce il valore di E (α) e conosci il valore di E (β). Ora la domanda è che come instanziamo questa funzione E e F? Potrebbe essere il seguente: quindi immaginate di assumere esponenzialismo alla base pubblica g. Quindi supponete che g sia qualche base fissa pubblica e possiamo prendere la funzione candidata E per essere la seguente: E (α) è definito tale base g α e questa funzione F (α, β) può essere definito l'esponenziazione di questo rispetto a questa base g e una potenza di exponentiation è α times β Ecco quindi il mio candidato F (α β). Ora è facile vedere che se definiamo la mia funzione E e F funzionano così. Poi sono in grado di soddisfare uno dei requisiti della funzione E e F che mi interessano. Ovvero se mi viene dato E (α) e se voglio calcolare F (α, β) allora quello che devo fare è solo alzare quella E (α) β che mi darà il valore di F (α, β). Allo stesso modo se possedevo E (β) e non conosco β poi solo conoscere α e E (β) Posso calcolare F (α, β) innalzando quel valore E (β) α Quindi questo soddisfa uno dei requisiti chiave che mi servono dalla mia funzione E e funzione F, ma si scopre che prendere questo intero esponente non è sufficiente per instanziare quell' abstract Diffie – Hellman Key Exchange Protocol perché ci sono diversi altri problemi di sicurezza con questa funzione E e F. Il primo problema maggiore è che la funzione E non è una funzione di senso unico e di vedere che immagina di conoscere la descrizione della base g e di conoscere il valore di E (α) cioè g α e il tuo obiettivo è quello di scoprire l'α poi è molto facile calcolare la α sconosciuta semplicemente prendendo il logarissimo naturale. E il computing naturale di calcolo è un compito computazionalmente facile. Quindi la funzione E al primo posto in sé non è una funzione unidirezionali e questo significa che non posso realizzare questa nozioni di privacy debole e di forte privacy. Non solo la funzione E è una funzione a senso unico, il problema qui è che non posso usarlo per scopi pratici. Non posso utilizzare questa funzione E e la funzione di candidato F per scopi pratici perché qui il mio α e β possono essere numeri interi arbitrari. Mentre se voglio istanziare e implementare questa funzione E e F, non posso lavorare su una funzione o un dominio alla gamma che consistono in numeri interi arbitrari e che potrebbero essere di dimensioni infinite. Piuttosto ci interesserà lavorare su domini finiti in natura così per questo ora cercheremo di cercare funzioni candidate E e F che non sono solo funzioni unidirezionate e non solo soddisfa il requisito delle funzioni E e F di cui abbiamo bisogno per questo abstract Diffie – Hellman Key Exchange Protocol, ma ci interessa anche che quelle funzioni siano da un appropriato dominio algebrico finito. (Riferirsi Slide Time: 05 :25) Per questo ora dobbiamo ricordare la teoria dei gruppi che avevamo visto quando abbiamo costruito i nostri MACs teorici dell'informazione cioè quando abbiamo costruito funzione universale. Quindi lasciatemi rapidamente passare attraverso la definizione di gruppi. Quindi un gruppo che io denota da questo simbolo è un set con qualche operazione appropriata sugli elementi del set e diciamo che ambientato (è un gruppo se soddisfa i seguenti assiomi ovvero deve soddisfare la proprietà di chiusura che afferma che per ogni,, l'elemento. La seconda proprietà è che l'operazione debba soddisfare la proprietà associatività cioè per ogni,,, () = () detiene. Serve l'esistenza di un elemento di identità e cioè ci dovrebbe esistere un elemento unico che io dengo come e nel set tale che, tale che per ogni. Si dovrebbe avere un elemento inverso per ogni elemento del set e cioè per ogni elemento a partire dal set ci dovrebbe esistere un elemento unico che io dengo di un -1 tale che un -1 = un -1 = trattiene. Sottolineo che questo elemento a -1 non significa il 1/a numerico. Si tratta solo di un'interpretazione o semplicemente di una notazione per l'elemento inverso speciale corrispondente all'elemento a cui ho bisogno dal mio set. Così, ancora solo per ricordare avevamo visto anche alcuni esempi di gruppi. L'insieme di numeri interi (Z, +) costituisce un gruppo Abelian. Che cos' è un gruppo Abelian? Un gruppo Abelian è un gruppo speciale che soddisfa tutti gli assiomi di gruppo e sopra di esso dovrebbe soddisfare la proprietà commutativa. Ovvero la vostra operazione dovrebbe soddisfare la proprietà commutativa ed è facile vedere che l'insieme di numeri interi insieme a questa operazione + che soddisfa gli assiomi di gruppo. Se si assumono qualsiasi 2 interi aggiungi, si ottiene un intero, l'aggiunta è associativa, 0 è l'elemento di identità perché se si aggiungono 0 a qualsiasi intero si ottiene quel numero intero. Se si prende un qualsiasi numero intero, l'inverso corrispondente è – a. Mentre si scopre che l'insieme dei numeri naturali non forma un gruppo rispetto all'operazione + perché non abbiamo l'inverso additivo. Perché l'inverso additivo dell'elemento, diciamo 2 è – 2, ma il -2 non appartiene all'insieme dei numeri naturali. Allo stesso modo il set di numeri reali non zero R − {0} formano un gruppo rispetto all'operazione di moltiplicazione perché la moltiplicazione di qualsiasi 2 numeri reali ti dà un numero reale, quindi la chiusura è soddisfatta, la moltiplicazione è associativa, l'elemento 1 è l'elemento identitario. Per ogni elemento non zero a, l'inverso corrispondente è il 1/a numerico perché il numero reale un moltiplicato con l'inverso 1/a vi darà l'elemento di identità 1 ed è per questo che il set di numeri reali non zero forma un gruppo. (Riferimento Slide Time: 08.59) Ora siamo interessati a tipi speciali di gruppi che chiamiamo gruppi ciclici. Quindi, vediamo cosa è esattamente un gruppo ciclico? Un gruppo rispetto a un'operazione o si chiama gruppo ciclico di ordine q se le seguenti condizioni le trattiene: prima di tutto, (, o) deve soddisfare gli assiomi di gruppo cioè la chiusura, la proprietà associativa, l'esistenza di identificazione, l'esistenza dell'inverso per ogni elemento di gruppo. Se si tratta di un gruppo Abelian allora va bene, ma non ne abbiamo bisogno per essere un gruppo Abelian. Quindi pittoricamente immaginate di avere certi elementi da questo set e questa operazione o soddisfa tutti questi assiomi di gruppo. Il secondo requisito corretto qui è che siccome sto dicendo che il gruppo è un gruppo ciclico di ordine q. Per ordine q, intendo che ci sono q numero di elementi nel mio set. Quindi, ecco cosa intendo per ordine del gruppo di essere q. E perché si chiama gruppo ciclico? Si chiama gruppo ciclico perché ho bisogno di un elemento speciale che io chiamo un generatore che denota dicendo g. Questo g dovrebbe essere uno degli elementi da questo set tale che tutti gli elementi dal set possono essere generati da questo elemento speciale g da potenze diverse. Qui “ potenze ”, sarà chiaro a voi molto presto cosa intendo esattamente dai poteri qui. In sostanza, l'idea qui è che questo elemento speciale g che io chiamo come generatore ha la capacità, ha la capacità di generare tutti gli elementi del tuo set. Se ho almeno un elemento di generatore così speciale che chiamo come generatore, allora il mio gruppo è chiamato come ciclico, ma non ho nessun elemento così speciale g poi il mio gruppo non è chiamato gruppo ciclico. Allora, vi spiego cosa intendo esattamente generando elementi diversi da diversi poteri del generatore di elementi. Quindi lascia che p sia un primo e defini un set Zp * che consiste nell'elemento 1 a p – 1 e ora mi lasci definire un'operazione di moltiplicazione che sia diversa dalla normale moltiplicazione aritmetica così l'operazione che sto per definirlo è denotata da .p e che viene anche chiamata moltiplicatore modulo p. Il modo in cui verrà eseguita questa moltiplicazione è il seguente: Se prendo qualsiasi 2 elementi a, b dal set Zp * poi la moltiplicazione modulo p di a e b è uguale a quanto si moltiplica a e b numericamente e si prende il promemoria rispetto al modulo p. Qualunque promemoria si ottenga che sarà un numero compreso nell'intervallo da 0 a p-1 e che è il modo in cui definiamo questa operazione di moltiplicazione modulo p. Ora sto per dichiarare un risultato che è un risultato standard che segue dalla teoria dei numeri. Non lo dimostrerò, ma se siete interessati alla prova di questo teorema allora potete fare riferimento a qualsiasi riferimento standard dalla teoria dei numeri. Così il teorema afferma sostanzialmente che per ogni numero primo p il set Zp * insieme all'operazione di moltiplicazione modulo p è un gruppo o costituisce un gruppo composto da p – 1 elementi. Questo significa che l'ordine di gruppo è p – 1. Così non lo dimostreremo, ma dimostrerò che effettivamente questo è vero se p è il tuo primo. Quindi sto prendendo p = 5 qui e Z5 * fondamentalmente sono costituiti da elementi {1, 2, 3, 4}. Quindi quello che ho fatto è lungo le righe che ho scritto l'elemento 1, 2, 3, 4 e lungo le colonne ho denotato gli elementi 1,2, 3, 4 e questo è come una matrice qui. E quello che ho fatto qui è il (i, j) l'ingresso denota i risultati di (i. j) modulo 5 qui. Se considero questa voce, questo è il risultato di (2. 2) modulo 5. Allo stesso modo (4. 3) modulo 5 vi darà 2 e così via. Così potete vedere da questa matrice che la vostra proprietà di chiusura è soddisfatta. Prendi qualsiasi io e qualsiasi j nella gamma che appartiene a Z5 * ed esegui l'operazione (i. j) modulo 5, si ottiene il numero compreso nell'intervallo da 1 a 4. L'operazione di moltiplicazione che abbiamo definito qui soddisfa la proprietà associatività che significa se prendo (i, j) l'ingresso, poi non importa in quale ordine moltiplicare (i, j) l'ingresso e prendere modulo 5, otterrò lo stesso promemoria. L'elemento identit è l'elemento 1 qui perché se vedi questa matrice qui e se ti concentri sulla colonna sotto 1 qui poi sotto quella 1, 1 dot 1 modulo 5 ti dà 1, 2 dot 1 modulo 5 ti dà 2, 3 dot 1 modulo 5 ti dà 3 e 4 dot 1 modulo 5 ti dà 4. Quindi l'elemento 1 serve come elemento di identità qui. Ora sotto ogni elemento avrete il corrispondente elemento inverso. Quindi l'inverso di 1 è 1 qui perché 1 dot 1 ti dà 1. L'inverso di 2 è 3 perché 2 dot 3 modulo 5 ti dà l'elemento di identità 1, l'inverso di 3 è 2 perché 3 dot 2 modulo 5 ti dà l'elemento di identità 1 e inverso di 4 è 4 perché 4 dot 4 modulo 5 ti dà l'elemento di identità 1. Così avete tutti gli assiomi soddisfatti e ora potete vedere, avete presenti anche alcuni elementi di generatore speciali presenti qui. Lo dimostrerò anche io. Prima di andare a vedere se l'elemento generatore qui esiste o no, fatemi prima definire cosa intendiamo per esponente di gruppo in questo set Zp *. Per qualsiasi elemento g appartenente al set Zp *, io defino g0 da 1. E io definiamo g 1 per essere g perché effettivamente g0 modulo p si otterra ' ottenere 1 modulo p che è uguale a 1 e g 1 se g è un elemento di Zp *. Ovviamente è meno di p e se si fa g1 e poi si prende mod p poi l'effetto della mod p non fa effetto. Si sta per ottenere solo g. Mentre io defino g i to be the moltiplication modulo p operation applicato i – 1 volte. E si scopre che non importa se prendo il promemoria alla fine o se prendo in promemoria dopo aver eseguito ogni singolo individuo. p operation i – 1 volte, i risultati saranno uguali perché ciò deriva dalla proprietà associativa del mio gruppo Zp *. Così posso definire gi di essere lo stesso che si esegue i gi numerici e poi si prende una mod finale p per riportare il risultato nella gamma 0 a p – 1. Così, a causa del modo in cui gi è definito per il caso i 0, io per essere 1 e per essere un generico i posso dire che posso definire i miei gi. Posso usare la notazione gi nel set Zp * per denotare il valore numerico gi modulo p in modo che sia una notazione che userò qui ed è quello che intendo per potenza di un elemento g nel set Zp * qui. Così ancora sto andando a dichiarare un altro risultato ben noto dalla teoria dei numeri che afferma che per ogni numero primo p esistono almeno ad un elemento g nel set Zp * tale che quando si calcola g a potenze diverse ed effettua operazione modulo p ovvero si fa g0 mod p, g1 mod p up to gp – 2 mod p, poi si va ad ottenere tutti gli elementi nel set Zp * in qualche ordine arbitrario. Questo significa p – 1 distinti poteri di questo elemento speciale g vi darà tutti gli elementi in Zp * e questo significa che avete almeno un generatore presente in questo set Zp *. Questo è ciò che intendo generando tutti gli elementi del set da potenze diverse. Il tuo qui in questo particolare esempio è Zp * e il claim della teoria dei numeri è che esiste almeno un elemento in questo Zp * tale che se qui si solleva g ai diversi poteri e si esegue l'operazione di gruppo ovvero l'operazione di moltiplicazione modulo modulo che si sta andando ad ottenere tutti gli elementi di Zp *. Ancora una volta non sto dando una prova di questo, ma se siete interessati alla prova potete vedere qualsiasi riferimento standard. Vediamo se questo teorema detiene per l'esempio attuale che stiamo considerando qui. Quindi se prendo l'elemento 2 che è un elemento di Z5 * ed eseguo 20 modulo 5, 21 modulo 5, 22 modulo 5 e 23 modulo 5, vado ad ottenere gli elementi 1, 2, 4, 3 rispettivamente. Così notate che non sto ottenendo tutti gli elementi di Z5 * nell'ordine esatto. Ma sto ottenendo tutti gli elementi in qualche ordine arbitrario. Quindi per la definizione di gruppo ciclico, il requisito è che i diversi poteri di g dovrebbero darvi tutti gli elementi di quel set in qualsiasi ordine arbitrario. L'ordine non importa qui. Allo stesso modo anche l'elemento 3 è un elemento speciale qui perché 30 modulo 5, 31 modulo 5, 32 modulo 5 e 33 modulo 5 vi darà l'elemento 1,3, 4, 2 ovvero l'intero Z5 *. Ma se prendo l'elemento 4 e cerco di alzare o compimento diversi poteri di 4, non sono in grado di generare tutti gli elementi di Z5 *. Potrei generare solo gli elementi 1 e 4. Così dal risultato della teoria dei numeri che sto affermando qui afferma che ho qualche elemento speciale g che ha la capacità di generare l'intero set Zp *. Questo significa il set Zp * insieme a questa operazione di moltiplicazione modulo p è un gruppo ciclico di ordine p – 1. Perché ha p – 1 elementi ed effettivamente in questo esempio 2 è quello dei generatori di Z5 *, il 3 è anche uno dei generatori di Z5 *, ma il 4 non è un generatore di Z5 *. Ora vi starete chiedendo come mai il nome ciclico qui. Il motivo per cui lo chiamo ciclico perché non appena si dispone di un generatore g dice ad esempio per il gruppo Zp*e poi se si calcola la potenza successiva di g ovvero g p – 1 si ottiene uno degli elementi che c'è già in Zp *. Essenzialmente si otterrà l'elemento g0 solo. Quindi ancora la prova per quella che segue dalla teoria dei numeri, ma non proverò che se computi g p – 1 otterrete lo stesso valore di g 0. La prossima potenza di g ti darà g1 e così via. In quel senso è ciclico che significa non appena si va fino al limite gp – 2 e se si va ad iniziare a prendere la successiva sequenza di potenze di g si inizierà a ripartire lo stesso ciclo. Otterrai gli stessi elementi di Zp * e continuerà a succedere ed è per questo che il nome cyclic. Quindi i gruppi ciclici, solo per riepilogare i gruppi ciclici sono tipi speciali di gruppo che ha almeno un generatore. (Riferimento Slide Time: 20 :59) Così il gruppo Zp * rispetto all'operazione di moltiplicazione modulo p costituisce il gruppo ciclico moltiplicativo perché lì l'operazione è stata molteplice. Non è stata la moltiplicazione naturale. Non è stata la moltiplicazione intera, ma potrebbe essere interpretata come un'operazione moltiplicativa. Si scopre che possiamo anche definire gruppi ciclici in base alla nozione di operazione di aggiunta e lasciateci fare. Quindi, let p be a prime e definiamo un set Zp per essere il set di numeri interi da 0 a p – 1. Così la differenza tra Zp * e Zp è che l'elemento 0 non c'è in Zp *, ma l'elemento 0 è ora consentito in Zp. Ora lasciatemi definire un'operazione di aggiunta in questo set Zp che chiamo come aggiunta modulo p denotato da questo simbolo + p e l'aggiunta modulo p di qualche coppia di numeri a, b dal set Zp non è altro che eseguire l'aggiunta numerica o intera a e b e prendere il modulo p. Così che il resultante sia un elemento nel set 0 a p – 1. Quindi ancora una volta facciamo un esempio qui il set Z5 è costituito dal numero intero {0, 1, 2, 4, 4} e quello che ho fatto qui è che ho fatto la matrice che denota il risultato di eseguire l'operazione + modulo 5 su qualsiasi coppia di elementi nel set Z5. Ancora, c'è un fatto ben noto dalla teoria dei numeri che afferma che se si prende qualsiasi primo p poi il set Zp insieme all'aggiunta operazione modulo p costituisce un gruppo. Ma ora l'ordine del gruppo è primo e cioè ha p numero di elementi perché ora si sta avendo elemento da 0 a p – 1 mentre il set Zp * era un gruppo moltiplicativo di ordine p – 1. Così ora vediamo come possiamo interpretare l'esponente del gruppo in questo gruppo di additivi. Così abbiamo definito 0 volte g per essere 0 e abbiamo definito un tempo g per essere g dove g è qualsiasi elemento nel set Zp. Mentre i tempi g sono definiti per essere il risultato di questa aggiunta modulo p che viene applicata sull'elemento g, i – 1 volte. Si scopre che non importa se prendo la mod all'ultimo o se prendo il mod dopo ogni operazione + il risultato sarà lo stesso perché quello segue dalla proprietà associativa dell'operazione + e da qui posso dire che i tempi g sono gli stessi della moltiplicazione dei numeri interi di i e g modulo p. Così quando dico che i tempi g che non significavano che mi sto moltiplicando io e g, i volte g è la notazione che ho seguito per g e ho seguito per g è uguale alla moltiplicazione intera di i e g modulo p. Quindi in base a questi 3 modi o al modo in cui questo esponente di gruppo è definito rispetto a questa operazione + posso usare la notazione che io. g è uguale a numero intero moltiplicazione di i e g modulo p. E ancora c'è un risultato ben noto dalla teoria dei numeri che afferma che per ogni primo p esistono almeno un elemento speciale g nel set Zp tale che 0 volte g, 1 volte g fino a p – 1 volte g la p – 1 distinti poteri di g ridanno tutti gli elementi del set Zp in qualche ordine arbitrario. Così ora qui l'esponente è fondamentalmente trattato come se si desidera compere g x. In sostanza, g x qui viene interpretato come se si sta eseguendo l'operazione + modulo p x – 1 numero di volte. Ecco quindi l'interpretazione del potere di g quando sto considerando l'operazione di gruppo sottostante nelle serie additive. Quindi ancora, nel contesto di Z5 l'elemento 1 si scopre un elemento così speciale dove tutti i diversi poteri del 1 vi ridanno tutti gli elementi di Z5. Stesso vale per il 2 come potenze ben diverse del 2 vi ridarà tutti gli elementi di Z5. Questo significa che il set Zp insieme all'operazione + modulo p è un gruppo ciclico di ordine p. Così avevamo visto esempi di gruppi ciclici basati sull'operazione di moltiplicazione. (Riferimento Slide Time: 25 :26) Così avevamo visto esempi di gruppo ciclico basato sull'operazione di aggiunta. Ora definiamo ciò che intendiamo per esponente di gruppo in gruppi ciclici astratti. Quindi per spiegazione sto assumendo che il mio è qualche gruppo astratto dove l'operazione sottostante è un'operazione moltiplicativa. Non serve essere una moltiplicazione intera, ma può interpretare in senso moltiplicativo e ha un ordine q cioè ha q numeri di elementi. Dato che si tratta di un gruppo astratto, io dengo l'elemento identit per essere e lasciare che g sia un elemento di questo gruppo. Poi usiamo la seguente notazione. Così siccome qui stiamo usando la notazione moltiplicativa per quel gruppo astratto, userò la notazione g0 per denotare l'elemento identitario e g1 per denotare l'elemento identitario. E la notazione gi per denotare l'elemento che ottengo componendo o eseguendo l'operazione di gruppo sull'elemento g, i – 1 volte. Sottolineo che questa notazione è completamente diversa dall'esponente intero. Questa è solo una notazione, gi non significa che sto moltiplicando g, i – 1 volte. Praticamente è solo una notazione che ho usato per rappresentare che sto eseguendo l'operazione di gruppo sull'elemento g, i – 1 volte. Tuttavia, si scopre che le regole dell'esponente intero sono ancora applicabili in questo gruppo moltiplicativo astratto. Ovvero se prendo l'elemento di gruppo gm che è sostanzialmente l'elemento g composto da sé m – 1 numeri di volte come per l'operazione di gruppo e prendo l'altro elemento di gruppo diciamo g n che è l'elemento di gruppo g composto da se stesso n – 1 volte. Poi se eseguo l'operazione di gruppo su questi 2 elementi poi il risultato sarà lo stesso dell'elemento g composto m + n – 1 numero di volte. Allo stesso modo, se prendo l'elemento gm ed eseguo l'operazione di gruppo su quell' elemento n – 1 volte poi otterrò lo stesso risultato che ottengo eseguendo l'operazione di gruppo sull'elemento g, m + n – 1 numero di volte e così via. Del resto, se questo elemento g è un gruppo ciclico allora si scopre che diversi poteri di g e di nuovo da diversi poteri di g non intendo l'esponente intero. Potenza con poteri diversi di g significa la definizione di esponente di gruppo in quel senso astratto. Quindi se questo g è un generatore allora diversi poteri di g che spaziano dalla 0 potenza alla q – 1 ° potenza mi ridanno tutto l'elemento di set in qualche ordine arbitrario. E infine un fatto interessante che incontreremo più tardi o che useremo dopo è il seguente: se avete qualsiasi elemento g che sia un generatore del gruppo allora l'elemento gi è uguale all'elemento gi modulo q, questo significa che è possibile eseguire l'operazione mod q anche nell'esponente. Quindi per qualsiasi io che sia < q questo fatto è trivialmente vero perché gi e gi mod q sono uguali se io < q. Ma quello che questo fatto dice che se sono più grande di q, poi g al potere che più grande potenza vi rido la stessa risposta del risultato che otterrete alzando g all'indice i modulo q. Ancora, non vi sto dando la prova per questo potete fare riferimento a qualsiasi testo standard sulla teoria dei numeri per la prova di questo. Ora questa discussione che abbiamo fino ad ora qui è rispetto a un gruppo ciclico moltiplicativo. Possiamo estendere la nostra definizione per qualsiasi gruppo ciclico astratto dove l'operazione sottostante è additiva. Così possiamo definire g ai tempi g g per essere e o l'elemento di identità ovvero la 0 potenza di g qui è l'elemento di identità e la g1 nel gruppo ciclico additivo verrà interpretata come una volta g e definizione dice che 1 volte g vi darà l'elemento g. E gi in questo gruppo ciclico additivo verranno interpretati come i tempi g definiti per essere l'operazione di gruppo, o l'operazione di gruppo additive eseguita sull'elemento g, i – 1 volte. E si scopre che le regole di exponentiation detengono anche nel gruppo ciclico additivo. Ovvero se prendo l'elemento m volte g che è uguale a gm nel gruppo ciclico additivo e un altro elemento n volte g che è l'equivalente di gn nel gruppo ciclico additivo. Se eseguo l'operazione di gruppo allora il risultato sarà lo stesso di m + n volte l'elemento g ovvero l'equivalente dell'elemento g (m + n).E lo stesso vale così. Se prendo l'elemento m time g e poi se eseguo n volte quell' elemento, allora il risultato sarà lo stesso di nm volte quell' elemento g e così via. Inoltre, se l'elemento g è un generatore, allora diversi poteri di g mi daranno l'intero set in qualche ordine arbitrario e i diversi poteri di g sono scritti come 0 volte g, 1 volte g e q- 1 volte g. E come è stato il caso per il gruppo ciclico moltiplicativo ho un dato di fatto corrispondente anche qui che se g è un generatore allora qualsiasi I volte g che è il corrispondente equivalente di gi è lo stesso modulo q volte g. Questo significa se io > q e poi se si desidera compattare che i volte g poi si può prima ridurre quell' indice i modulo q e poi alzare quell' indice all'elemento g per ottenere la risposta risultante. (Riferimento Slide Time: 31:55) Così ora abbiamo definito una nozione di gruppi ciclici e ora vediamo cosa intendiamo per logaritmo discreto nei gruppi ciclici. Quindi immaginate di ricevere un gruppo ciclico arbitrario di ordine q e senza perdita di generalità ipotizza che l'operazione di gruppo sottostante sia un'operazione moltiplicativa. Non serve essere una moltiplicazione intera, ma per lo scopo di notazione utilizzeremo qui la notazione moltiplicativa. Dato che l'ordine è q che significa che ha un numero finito di elementi. Così questi doti di colore denotano il vari elemento nel tuo set. Dal momento che si tratta di un gruppo ciclico ha qualche generatore almeno un generatore che dengo di g. Così ho evidenziato che elemento g qui e come per la definizione di gruppo ciclico diversi poteri di questo elemento g vi darà l'intero set in qualche ordine arbitrario. Quello che significa è che se prendete qualsiasi elemento y da questo set allora esistono qualche indice univoco x nella gamma 0 a q – 1 tale che gx vi avrebbe dato l'elemento y e ricordate gx sta eseguendo l'operazione di gruppo sull'elemento g, x – 1 numero di volte. Non significa necessariamente che mi sto moltiplicando g, x numero di volte. Sto eseguendo l'operazione di gruppo moltiplicativo sottostante sull'elemento g, x – 1 numero di volte. Quindi il motivo per cui esiste un x in questa gamma da 0 a q – 1 tale che gx ti avrebbe dato y. Deriva dal fatto che l'elemento g è un generatore. Ora questo unico x nella gamma 0 a q – 1 è chiamato logaritmo discreto del vostro elemento y alla base g che denottiamo da questa notazione DLog yg = x. E si può considerare questo log discreto essere un equivalente del log naturale. Nel mondo dei numeri reali se hai un qualsiasi numero reale g al potere che ti dà y allora diciamo che definiamo quel log yg = x. Quello che stiamo cercando di fare qui è che stiamo cercando di dare una definizione equivalente nel mondo discreto cioè nel contesto di un gruppo in cui abbiamo qualche numero finito di elementi diciamo q numeri di elementi e visto che stiamo valutando un gruppo. Gli elementi qui sono discreti. Tra gli eventuali due elementi di gruppo non sarà un elemento di gruppo arbitrario in arrivo. Ecco perché questo logaritmo che stiamo definendo la nozione di logaritmo che stiamo definendo in questo gruppo ciclico è chiamato come il logaritmo discreto. Curiosamente, si scopre che il logaritmo discreto obbedisce alle regole del logarimo naturale i.e Dlogge = 0, Dlogghr = r (Dloggh) mod q. Perché stiamo prendendo modulo q è che questa è la cosa che stiamo avendo la staffa che può uscire da q, che può attraversare la gamma 0 a q – 1, ma come per la definizione di log discreto l'indice il logaritmo discreto deve essere compreso nell'intervallo 0 a q – 1 ed è per questo che stiamo prendendo modulo q qui e allo stesso modo Dloggh1 h2 = (Dloggh1 + Dloggh2) mod q. Si sta andando a verificare questi fatti. Questi sono alcuni semplici esercizi per te e il fatto finale che useremo nell'ambito del logaritmo discreto è che se hai qualche gx dato per essere y dove x non deve essere compreso nell'intervallo 0 a q – 1. Poi il DLogyg è uguale a x modulo q. Beh se il tuo x che ti viene dato è effettivamente nella gamma da 0 a q – 1 allora x modulo q è uguale a x. ma il fatto interessante qui è che se si ha se si dà una x che si trova al di fuori della gamma 0 a q – 1 tale che gx è dato y e se si è interessanti per calcolare il DLogyg è uguale ad eseguire l'operazione x modulo q. Ancora, si tratta di un fatto ben noto dalla teoria dei numeri che non proverò qui potete vedere qualsiasi testo standard per la prova di questo teorema. Così questo mi porta alla fine di questa lezione. Per riassumere in questa lezione abbiamo introdotto la nozione di gruppi ciclici e abbiamo visto la definizione di logaritmo discreto. Nella lezione successiva vedremo alcune assunzioni di durezza della crittografia basate sui ciclici