Loading
Study Reminders
Support
Text Version

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 Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bengaluru Collezione – 55 Numero Teoria Hello ognuno. Benvenuti a questa lezione. Solo un rapido recap, nell'ultima lezione abbiamo concluso la nostra discussione sulla crittografia a chiave pubblica. Così in questa lezione la roadmap è la seguente. (Riferimento Slide Time: 00.29) In sostanza discuteremo alcuni dei principali risultati relativi alla teoria dei numeri che abbiamo utilizzato durante la nostra estesa discussione sulla crittografia a chiave pubblica. Sottolineo che non avremo una discussione a tutto campo sulla teoria dei numeri perché personalmente la sento come; in un corso sulle fondamenta della crittografia dovremmo sostanzialmente utilizzare i fatti importanti dalla teoria dei numeri. Ma ho pensato che probabilmente avremmo dovuto fare una discussione di altissimo livello su alcuni dei risultati importanti che abbiamo usato diffusamente durante la nostra discussione sulla crittografia a chiave pubblica. Così motivati da ciò che avremo questa discussione; oggi la lezione di "s" è basata completamente sulla teoria dei numeri che discuteremo di aritmetica Modulare, Prime numeri e relative proprietà e vedremo l'algoritmo GCD di Euclide. (Riferimento Slide Time: 01.28)Così iniziamo con Aritmetica Modulare. Immaginate quindi di ricevere 2 numeri o 2 numeri interi a, N appartenenti alla serie di integre Z. E qui N è il modulo dove N > 1. Poi un mod N è definito il resto r, tale che il resto r è nella gamma da 0 a N - 1, tale che la relazione a = q orari N + r trattiene per alcuni interi q. Se è così, allora diciamo che un modulo N è r. Quindi per esempio, se voglio scoprire 5 modulo 4 poi 5 modulo 4 è 1, perché se divido 5/4 prendo il resto 1. Allo stesso modo, se voglio scoprire -11 modulo 3 poi -11 modulo 3 è 1 perché 1 è nella gamma da 0 a 2 e -11 può essere correlato a 3 da questo rapporto cioè posso dire che -11 è 3 volte - 4 + 1. Si scopre che posso scrivere -11 come una combinazione lineare del mio modulo 3 anche in un'altra forma, cioè posso dire che – 11 = (3 volte – 3) - 2. E quindi si potrebbe sentire che -11 modulo 3 dovrebbe essere - 2 ma non è così perché come per nostra definizione il resto r dovrebbe essere compreso tra 0 e N - 1. Ecco perché il -11 modulo 3 è 1 e non -2. Ora abbiamo la definizione di un modulo N; quindi se abbiamo due numeri interi a e b tale che sia un bene che b ti dà lo stesso modulo restante modulo, il modulus N poi diciamo che un è congruo a b e noi la notazione che un &equivalente; b modulo N. Così questo significa che un e b sono equivalenti nel senso che ti danno lo stesso promemoria quando ci si divide per la definizione di un modulo N si scopre che, se un è congruo a b modulo N allora questo è possibile se e solo se la differenza di un e b è completamente divisibile per N. Perché se un dà il resto r modulo N e dato che un è congruo a b modulo N che significa b modulo N è anche lo stesso promemoria r e se sottratto b da un allora il resto r e r annulla e ciò che ottengo è che un - b è completamente un multiplo di N e da qui sarà completamente divisibile per N. (Fare Slide Time: 03.58) Così abbiamo alcune ben note regole aritmetiche per l'aritmetica modulare. Così per esempio abbiamo due numeri a e b e se so che un modulo N è undi e b modulo N è b allora posso dire che un + b modulo N sarà lo stesso valore che hai ottenuto facendo l'operazione un + b modulo N. Lo stesso vale per la sottrazione oltre che per la moltiplicazione. Così il modo in cui si può interpretare queste regole è che si può immaginare come se si possa prima eseguire i modulari o si può prima fare la riduzione modulo, il modulo N. E poi si può eseguire l'aggiunta, sottrazione, operazione di moltiplicazione invece di aggiungere o sottrarre o moltiplicare e poi fare la riduzione modulo N. Per essere più specifica per esempio immagino di voler calcolare il valore di questo numero cioè voglio eseguire il prodotto di 1093028 e 190301 modulo 100. Se voglio calcolare questo valore, allora ci sono due modi per farlo. Il primo modo sarà che prima eseguo il prodotto qui o prima compone il prodotto qui e poi faccio la riduzione modulo 100. Ma questa sarà un'operazione complicata perché moltiplicare questi due grandi numeri sarà davvero impegnativo. Non posso farlo facilmente su un notebook. D'altra parte, la stessa operazione che posso eseguire riducendo in primo luogo i singoli valori qui ovvero 1093028 e 190301 modulo 100. E ridurre ciascuno dei modulo 100 è molto semplice. Perché devo solo concentrarmi sulle ultime due cifre qui che prendo come 28 e 1 e poi posso moltiplicare 28 e 1 e poi ridurlo di nuovo, ridurre la risposta modulo 100. E qualunque sia stato ottenuto per opzione 1 e qualunque risultato abbia ottenuto per opzione 2 saranno uguali a seconda delle nostre regole aritmetiche di aritmetica modulare. Si tratta quindi di un trucco molto potente o potente applicabile nel contesto dell'aritmetica modulare dove si deve; dove; invece di applicare l'operazione e poi fare la modulistica o riduzione modulo N e si può prima ridurre gli operandi modulo N e poi è possibile eseguire l'operazione e se richiesto è possibile eseguire nuovamente una riduzione modulo N. (Fare Slide Time: 06.13) Così abbiamo visto l'aggiunta, la sottrazione e la moltiplicazione modulo N e cosa riguarda la divisione modulare. Quindi la domanda è possiamo dire la seguente, immaginate un modulo N è unmt e b modulo N è bmt allora possiamo dire che un diviso per b modulo N sarà lo stesso di unmt/b modulo N. Answer è no, perché in realtà a quanto pare in quella operazione una divisa da b modulo N non è affatto ben definita. Così per dimostrare il mio punto immaginavo il mio e b sono 3 e 5 e il mio modulo è 4 così mi sono dato 3 modulo 4 è 3 e 5 modulo 4 è 1 e so che 3 diviso per 1 modulo 4 che mi hanno dato 3 ma se voglio calcolare 3 diviso per 5 modulo 4 non ho la risposta, perché questa operazione 3 divisa da 5 modulo 4 non è affatto ben definita. Questo significa in aritmetica modulare non posso dire che, se mi viene dato che il prodotto di ac modulo N e il prodotto bc modulo N sono uguali. Poi non posso dire che annullare c da entrambi i lati e non può ottenere implicazione che un modulo N = b modulo N, che sarebbe stato possibile se avessi eseguito la stessa operazione in aritmetica regolare e c non sarebbe; e c non è 0. Questo significa nell'aritmetica regolare se so che ac = bc e c non è 0 allora posso dire che se divido entrambi i lati da c poi ottengo un = b. Ma la stessa cosa non posso concludere nell'aritmetica modulare perché la divisione modulare non è ben definita. (Riferimento Slide Time: 07.50) Quindi ora parliamo di alcuni algoritmi per l'aritmetica modulare. Immaginate quindi di dare due operandi a e b ciascuno di dimensioni n - bit e il modulo N la cui dimensione è anche n - bit, e alcune delle operazioni comuni che abbiamo incontrato nella crittografia a chiave pubblica sono quelle di eseguire l'aggiunta modulare, la moltiplicazione, la sottrazione e l'esponente. Quindi ricordare l'esponente modulare è un'operazione molto importante in quasi ogni istanziazione della crittografia a chiave pubblica, dove abbiamo incontrato l'esponente modulare. Quindi ora vogliamo avere algoritmi per eseguire queste operazioni aritmetiche modulari, tali che gli algoritmi che ne derivano, la loro complessità, la loro complessità temporale dovrebbero essere una qualche funzione polinomiale nel numero di bit cioè n. Così si scopre che se voglio eseguire aggiunta modulare, sottrazione e moltiplicazione posso eseguirle in poli (n) numero di operazioni di bit. Ma che dire dell'esponente modulare, immaginate di voler calcolare ab modular N, un algoritmo ingenuo sarà che io eseguo a2 modulo N qualunque sia il risultato che lo moltiplica di nuovo con un modulo N, e come quello che devo eseguire in pratica b - 1 moltiplicazioni modulari e dato che ogni moltiplicazione modulare richiede un numero di operazioni di tipo polare (n) e sto eseguendo b tale ordine di b tali operazioni si può dire che, la complessità temporale complessiva di questo algoritmo di esponente modulare ingenuo sarà O (b * poly (n)) - bit operations e quindi è polinomiale globale. Ma questo non è corretto perché qual è esattamente il valore di b qui. Devo esprimere il valore di b anche come qualche funzione di n e si scopre che la grandezza di b qui è una qualche funzione esponenziale in numero di bit n. Praticamente b può essere grande come 2n. Questo significa, questo ingenuo algoritmo di exponentizzazione modulare; la sua complessità temporale è la funzione esponenziale e il numero di bit che devi rappresentare il tuo a b e il modulo N ed è per questo che è l'algoritmo in tempo esponenziale. Non possiamo usare questo ingenuo algoritmo di exponentizzazione per eseguire; per compencire ab modulo N. (Fare Slide Time: 10.16)Quindi ora quello che andiamo a discutere è che vedremo un algoritmo di tempo polare per calcolare le espansioni modulari. Così questo metodo è chiamato come il metodo Square e Multiphysics. E per dimostrare l'algoritmo farò un esempio qui. Voglio calcolare una alla potenza 53 modulo N. Ricordi, l'approccio ingenuo sarà quello di moltiplicare una 52 volte e ciascuna; con ogni moltiplicazione si fa un'operazione mod N. Quindi in sostanza, l'approccio ingenuo richiederà di eseguire 52 moltiplicazioni modulari. Ma quello che vedremo qui è che usando il metodo quadrato e moltiplicato possiamo eseguire lo stesso calcolo con appena 9 moltiplicazioni modulari. Così l'idea alla base di questo metodo quadrato e moltiplicato è la seguente. Così esprimo il mio esponente 53 in questo caso in binario. E a seconda della bit rappresentazione di 53 dovunque io abbia il bit value 1 devo prendere quella potenza di 2. Ovunque il bit di potenza sia 0 devo escludere quella potenza di 2 e da qui posso dire che 53 minuti a seconda della sua rappresentazione binaria si può esprimere come sommatoria di questi poteri di 2. E da qui posso dire che un alla potenza 53 non è altro che il prodotto di alcune potenze selettive di una potenza 32, una alla potenza 16, una alla potenza 4 e una alla potenza 1. Quindi l'idea alla base di questo metodo quadrato e moltiplicato come suggerisce il nome è che in ogni iterazione ci accumuleremo o calcoleremo i poteri successivi di un. E questo significa che inizieremo con una potenza 1 e poi passeremo in un quadrato allora da un quadrato arriveremo ad una alla potenza 4 poi da una alla potenza 4 andremo a una alla potenza 8 e così via e poi selettivamente a seconda del bit corrente nella rappresentazione binaria dell'esponente ovvero 53 in questo caso decideremo se accumulare il potere corrente di un o meno, ed è per questo che il nome quadrato e si moltiplica. In modo più dettagliato immagino di scrivere 53 in questa rappresentazione binaria da LSB a MSB in questa forma. E mentre vado da LSB a MSB i diversi poteri di un che ottengo man mano che vado da 1 minuti di corrente a quello successivo è solo un quadrato del precedente potere, giusto ed è facile vedere che il mio obiettivo è quello di calcolare una alla potenza 53 e una alla potenza 53 praticamente si può calcolare solo moltiplicando alcuni poteri selettivi di una cioè i poteri di un corrispondente alle posizioni di bit dove nella rappresentazione binaria di 53, dove ho il bit 1. Così basato su questa idea l'algoritmo è il seguente. Così abbiamo impostato un accumulatore qui che avrà la risposta finale. La risposta finale che voglio calcolare è una alla potenza b o una alla potenza 53 in questo caso. Così inizierò il mio accumulatore ad essere 1 e una volta eseguo le tutte le iterazioni il mio accumulatore avrà la risposta finale. Quindi in ogni iterazione quello che sto per fare è, farò un aggiornamento condizionale, ovvero farò l'operazione che y = y in corrente di potenza di un dipende se il mio bit di corrente in esponente b che sto esplorando ora è 1 o meno. Così per esempio, attualmente inizio con la LSB di 53 o l'esponente b, in questo momento il bit è 1 che significa che devo assumere questo potere ed è per questo che aggiorcero il mio accumulatore da parte già esistente e l'attuale potenza di un e poi vado al prossimo potere di un. E controllo la posizione bit, la posizione di bit è 0; bit è 0 quindi non ho bisogno di accumulare questo potere. Poi vado alla prossima potenza di un che sarà un alla potenza 4 e controllo il bit corrente, è uno. Il che significa che devo accumulare questo potere, quindi è per questo che aggirerò il mio accumulato moltiplicando il contenuto attuale dei accumulati con l'attuale potenza di un. Poi vado alla prossima potenza di una che non ho bisogno di includere o accumulare perché la posizione di bit nell'esponente è 0 poi vado alla prossima potenza di un e controllo la posizione di un esponente dell'esponente nella sua rappresentazione binaria è di 1, quindi devo accumulare. E da qui sto aggiornando il mio accumulatore, e poi finalmente vado all'MSB della piccola rappresentazione del mio esponente, è il 1, questo significa che devo accumulare l'attuale potere di un e di qui la mia risposta definitiva. Quindi non sto scrivendo il codice pseudo esatto qui. Puoi capire; spero che tu sia in grado di scrivere qui il codice pseudo. Ma idea qui è che avrò bisogno di eseguire una sequenza di iterazione, il numero di iterazioni non è altro che il numero di bit che devi rappresentare il tuo esponente b. E in ogni iterazione dobbiamo fare una quadratura obbligatoria per computer la prossima potenza di un. E un accumulo opzionale a seconda che il bit corrente nella rappresentazione binaria dell'esponente b sia di 0 o 1 e si scopre che nel peggiore dei casi il mio esponente b potrebbe essere tale che tutti i bit nella sua rappresentazione binaria siano 1, questo significa nel peggiore dei casi in ogni iterazione questo accumulo opzionale deve essere eseguito obbligatorio. Ma anche in quel caso il numero totale di moltiplicazioni modulari che finiamo per esibirsi è due volte n che è qualche funzione polinomiale nel numero di bit che devi rappresentare il tuo n, il tuo modulo e i tuoi numeri a e b e da qui questo è un algoritmo a tempo di polpa e questo è l'algoritmo che usiamo per eseguire l'esponenziazione modulare in tutte le nostre criptovalute. (Riferimento Slide Time: 15.33)Ora parliamo di numeri primi. Quindi la definizione dei numeri primi è che un intero p > 1 è chiamato numero primo se i suoi unici fattori positivi sono il numero stesso e il 1. E un numero intero positivo maggiore di 1 che non è primo è chiamato numero composito. E un teorema ben conosciuto dell'aritmetica che viene spesso chiamato anche come teorema fondamentale dell'aritmetica è che qualsiasi numero n > = 1 può sempre essere espresso come prodotto di diversi poteri di primo e questo vale per ogni n > = 1. Questo è un fatto ben noto che possiamo provare usando l'induzione e non entrando nella prova esatta. E c'è un altro dato ben noto dalla teoria dei numeri che dice che, ci sono infinitamente molti primes. Non è il caso di avere solo un numero finito di primes. E ancora questo teorema possiamo provare usando contraddizione o qualsiasi metodo di prova. Quindi ci sono diverse prove ben note per dimostrare il fatto che ci sono infinitamente molti primes. Non entrerò nei dettagli della prova qui. (Riferimento Slide Time: 16.39)Quindi se si ricorda che nel nostro sistema di crittografia RSA e anche nell'ambito dello schema di crittografia Elgamale, fondamentalmente ci si richiede come parte della descrizione di impostazione di un numero primo da mettere a disposizione di tutte le parti e il numero primo dovrebbe essere sufficientemente grande. Quindi la domanda è come scegliamo esattamente i numeri primi. Questo significa che abbiamo bisogno di un algoritmo per verificare se un numero di n - bit scelto casualmente è un numero primo o meno. E c'è un algoritmo ingenuo per farlo. E l'algoritmo ingenuo si basa sul fatto che se un numero p è composito poi ha almeno uno dei divisori che è inferiore o uguale a   e la prova di questo teorema è molto semplice perché se si hanno tutti i divisori di un numero composito p maggiore di  . Diciamo che hai due fattori tali a e b e né un e né b è inferiore o uguale a e sia a e b sono i fattori di p e p è composito poi si scopre che il prodotto ab sarà più grande di p che è una contraddizione. Quindi questo significa che se a tutti hai un numero composito p è legato ad avere almeno uno dei fattori della gamma 1 a. E in base a questa osservazione possiamo avere questo seguente algoritmo di Primality Testing. Immaginate quindi di ricevere un numero p e di voler verificare se il numero p è primo o meno e dire che il numero p è un numero n. Quindi l'algoritmo ingenuo è in sostanza verificare se sono presenti qualsiasi divisore i nella gamma da 2 a   per il numero p. Perché se effettivamente p sarebbe stato composito il suo legato per avere almeno uno dei divisori nell'intervallo 2 a questo significa che avrà almeno un divisore i nella gamma 2 a e questo è ciò che si sta cercando in questo algoritmo ingenuo. Si scopre che il tempo di esecuzione di questo algoritmo è O ( ) divisioni perché si sta eseguendo il numero di divisioni in questo algoritmo. E dato che p è n - bit numero la magnitudo di p è 2n quindi sostanzialmente si sta eseguendo 2 alla potenza n / 2 divisioni in questo algoritmo ingenuo. E da qui si tratta di un algoritmo in tempo esponenziale che non possiamo usare in pratica per testare se un dato numero p è primo o no, se il mio n è sufficientemente grande. Quindi è stato davvero un problema molto impegnativo verificare se un dato numero p è primo o non in quantità polinomiale. Infatti, la gente ha creduto che non sia possibile inventarsi con l'algoritmo del tempo polare per verificare se un dato numero p è primo o no. Ma la storia è stata fatta nell'anno 2002 dove un gruppo di scienziati informatici di IIT - Kanpur ovvero Manindra Agrawal, Neeraj Kayal e Nitin Saxena. Sono arrivati con un algoritmo a tempo di polpa, polinomiale nel numero di bit che devi rappresentare con il tuo primo p, o numero p. E sono arrivati che questo algoritmo a tempo di polpa che ti dice se un dato numero p è primo o no e quell' algoritmo è ormai ben conosciuto come algoritmo AKS. Quindi è possibile utilizzare quell' algoritmo per verificare se un determinato numero p è primo o meno. Ma si scopre che non usiamo l'algoritmo AKS perché anche se è un algoritmo di tempo polare i polinomi sottostanti sono sufficientemente grandi e questo ci impedisce di distribuire questo algoritmo come in pratica. Invece quello che facciamo in realtà per verificare se un dato numero è primo o no è che usiamo un algoritmo che viene chiamato come Miller - Rabin primality testing algoritmo. Ed è un algoritmo randomizzato nel senso che non si può sempre fidarsi dell'output di questo algoritmo. Nel senso che, per 99,99% casi ti darà la risposta giusta mentre c'è una piccola probabilità di errore nell'output di questo algoritmo. Questo significa che anche se il tuo input potrebbe non essere un numero primo potrebbe finire per etichettare il numero come numero primo. Quindi in quel senso si tratta di un algoritmo di errore di prona. E il motivo per cui utilizziamo Miller - Rabin prova a verificare se un dato numero è primo o meno è che il suo tempo di esecuzione è super, super veloce rispetto al tuo algoritmo AKS. Sottolineo che l'algoritmo AKS è completamente privo di errori. È possibile fidarsi completamente dell'esito che viene dato dall'algoritmo AKS perché è un algoritmo deterministico. Non esiste una randomizzazione coinvolta come parte dell'algoritmo. (Riferimento Slide Time: 21.08) Ora parliamo di Greatest Common Divisor o GCD. Quindi se un e b sono due interi non zero allora il GCD di a e b è il più grande numero intero che è un fattore comune sia per quanto riguarda sia b. E se abbiamo 2 numeri o 2 interi a e b il cui GCD è 1 allora diciamo che gli interi a e b sono co - prime. E se abbiamo così diverse coppie di numeri simili o diversi interi dicono a1 a un noi diciamo che sono coprimi coprimi o relativamente prime se a coppia - i GCD sono 1 per ogni coppia di interi ai, aj nella lista. Quindi se vogliamo uscire dalla GCD di 2 numeri a e b poi l'algoritmo ingenuo sarà che prima scopro la prima fattorizzazione di un perché come per il teorema fondamentale dell'aritmetica posso esprimere un prodotto di potenze di prime. E allo stesso modo posso esprimere il mio numero b come prodotto di poteri di prime. E poi posso dire che GCD di a e b non è altro che prendo i minimi esponenti dalla singola fattorizzazione individuale di un e b e li organizziamo e questo mi darà il GCD di a e b. Ma il problema di questo algoritmo è che come al primo posto trovo la prima fattorizzazione di un e b. (Riferimento Slide Time: 22.31) Così si scopre che qui possiamo fare qualcosa di molto interessante. Possiamo utilizzare un algoritmo efficiente per calcolare l'algoritmo GCD e questo algoritmo è chiamato come algoritmo di Euclide s GCD. E base per l'algoritmo di Euclid's s è il fatto seguente. Quindi se ci vengono dati interi a e b tale che un è (b times q) + r. E se il vostro obiettivo è trovare GCD di a e b poi GCD di a e b non è altro che GCD di b e r, se a = (b times q) + r. Ancora non sto dando la prova di questo fatto. Devi credermi. Ma in base a questo possiamo scoprire un algoritmo per calcolare la GCD di a e b. E in sostanza, quello che facciamo in questo algoritmo è che impostiamo il mio x valore su un valore e y value a b e iterativamente trovo il valore di x modulo y, ho impostato la mia attuale y per essere il prossimo x e prendo il resto della mia attuale x modulo y per essere la prossima y. E eseguo questa operazione fino a quando la mia y diventa 0. Appena la mia y diventa 0 che alla fine accadrà, ottengo la x a quel punto per essere la GCD di a e b. E una correttezza di questo algoritmo segue dal fatto che GCD di a e b sarà uguale a GCD di b e r e GCD di b e r sarà uguale a GCD di r e b modulo r e così via. Questo significa ad ogni passo che sto praticamente riducendo il valore di così chiamato b e alla fine diventerà 0.So se vi starete chiedendo che cos' è la complessità temporale o quante divisioni modulari che sto eseguendo qui; quante operazioni mod sto eseguendo all'interno di questo algoritmo di Euclide. Posso arrivare con un legato esatto usando il teorema di Lame di Lame ben conosciuto che dice che se il GCD di un, b è calcolato usando l'algoritmo di Euclide e ha bisogno di n numero di divisioni allora la tua b dovrebbe essere almeno n + TSI numeri di Fibonacci cioè b dovrebbe essere maggiore o uguale a f (n + 1), quindi qui f (n + 1) denota un numero di Fibonacci n + 1 Fibonacci. Se vi state chiedendo qual è il numero di Fibonacci, è una sequenza a partire da 0 il numero successivo è uno. Questi sono i primi due numeri di Fibonacci. E poi se voglio calcolare il valore del numero di ith Fibonacci, il numero di ith Fibonacci è sostanzialmente la sommatoria del precedente numero di Fibonacci e poi precedente al precedente numero di Fibonacci. Ecco allora la mia sequenza di Fibonacci qui. Quindi quello che in sostanza il teorema di Lame fa dice è che, se l'algoritmo di Euclid's GCD avrebbe eseguito n numero di divisioni allora la magnitudo di b sarà almeno altrettanto grande quanto il n + 1 numero di Fibonacci. E esiste anche limiti più bassi noti sul valore dell'ennesimo numero di Fibonacci. Dice, il legato più basso dice che per ogni fine del valore di nono numero di Fibonacci è almeno α times n - 2 dove α è chiamato anche il rapporto golden ratio ovvero 1 + 5. 2 Così basato su questi due fatti posso dire che se il mio GCD di un, b ha bisogno di n numero di divisioni allora è massimo il n sarà massimo cinque volte 10 (b). Da qui, asintoticamente il numero di divisioni che dobbiamo eseguire in questo algoritmo è proporzionale al numero di bit che dobbiamo rappresentare il valore b e da qui l'algoritmo complessivo è un algoritmo efficiente. (Riferimento Slide Time: 25:57)Si scopre che possiamo utilizzare l'algoritmo di Euclid e s GCD per fare qualcosa di più. Quindi per capire che mi lasci andare per la prima volta a qui il teorema di Bezout. Quindi quello che dice il teorema di Bezout s è che, si può sempre esprimere il GCD di due numeri a e b come combinazione lineare dei numeri a e b. Il che significa che puoi sempre venire in alto, puoi sempre scoprire combinatori lineari s e t, in modo da poter esprimere gli input a e b come una combinazione lineare che ti darà il GCD di a e b. Ciò significa che il GCD di un e b può essere sempre espresso come una combinazione lineare degli input a e b dove i combinatori s e t esistono sempre. E se vi state chiedendo come esattamente potete scoprire questi coefficienti di Bezout s e t o i combinatori s e t dove potete farlo eseguendo qualche libretto extra o mantenendo alcune variabili extra nell'algoritmo di Euclide. E questo algoritmo esteso dove si esegue l'attività di prenotazioni extra per scoprire i combinatori lineari s e t è anche noto come algoritmo di Euclid. Quindi non entrerò nei dettagli completi di come esattamente questo libretto extra avviene nell'algoritmo di Euclide. Lasciamelo dimostrare. Supponiamo quindi di voler scoprire i coefficienti combinatori lineari o i coefficienti di Bezout per i numeri a 252 e b ad essere 198. Quindi se si vede il modo in cui opererà l'algoritmo GCD, l'algoritmo di Euclide s GCD opererà per l'input da 252 e b to be 198 è il seguente. Nella prima iterazione il tuo a sarà di 252, b sarà di 198 e otterrete il valore di 252 modulo 198. Nella prossima iterazione il tuo un sarà diventato 198 e il tuo b diventerà l'attuale restante 54 e così via. E fai questa operazione fino a quando il tuo resto diventa 0. E quando il tuo resto diventa 0 sai che 18 è il tuo GCD. Quindi ora il tuo obiettivo è quello di scoprire i combinatori lineari in modo da poter rappresentare il GCD 18 come combinazione lineare di 252 e 198. E per questo possiamo fare marcia indietro qui e possiamo vedere che posso riscrivere 18 per essere; in base a questa equazione posso riscrivere 18 per essere 54 volte 1 - 36. E se torno una volta passo sopra allora so che il mio 36 non è altro che 198 - 3 volte 54. Quindi se torno qui e sostituendo il valore di 36 qui poi ottengo che il 18 può essere riscritto come una combinazione lineare di 54 e 198, ma questo non è il mio obiettivo. Quello che posso fare è di nuovo posso tornare indietro di un passo e posso riscrivere il mio 54 come una combinazione lineare di 252 e 198. E se sostituendo quella combinazione lineare in quest' ultima equazione finendo per ottenere che il 18 sia rappresentato come una combinazione lineare di 252 e 198, questo significa che i miei coefficienti di Bezout sono 4 e - 5. Quindi in questa dimostrazione in realtà per scoprire i coefficienti Bezout's coefficients ho fatto un tracking indietro ma nell'algoritmo in realtà Euclide si deve solo il passaggio in avanti, non è necessario fare un back track in, fare la prenotazione e scoprire i coefficienti di Bezout. (Riferimento Slide Time: 29:21)Così come sarà utile esattamente questo algoritmo GCD di Euclide Euclid. Quindi sarà utile calcolare l'inverso moltiplicativo modulo N. Così ricordare come è stato; il modo in cui definiamo operazione di modulo N moltiplicativo. Così un * b modulo N è definito al promemoria di un in b modulo N e ricordare che definiamo un intero b per essere l'inverso moltiplicativo di un modulo N se il prodotto di un e b modulo N ti dà 1. E usiamo la notazione b = a-1 per denotare l'inverso moltiplicativo di un modulo N e il fatto fondamentale qui è che se b è inversamente moltiplicativo di un modulo N allora un è anche l'inverso moltiplicativo di b modulo N e si scopre che se effettivamente abbiamo un inno moltiplicativo di un modulo N, cioè se hai b tale che un tempo b modulo N è 1 poi così è b + qualsiasi multiplo del modulo N. Significa che non importa se aggiungere multipli di modulo N a b o sottrarre multipli di modulo N da b tutti anche sarà l'inverso moltiplicativo di un modulo N e questo è dovuto al fatto che un tempo b + - k volte N termina up fresate come la combinazione lineare di un e N usando i combinatori s e t. E ora se prendo mod N su entrambi i lati di questa equazione poi sul lato destro ottengo una modulo N e 1 modulo N mi darà 1. Ma il mio lato sinistro e cioè un tempo s + N volte t modulo N mi darà un tempo s modulo N perché N volte t modulo N mi darà 0 perché è il multiplo di N. Così quello che ottengo prendendo mod N su entrambi i lati è che io ottengo il rapporto che un tempo s modulo N = 1 che mostra che s è in realtà l'inverso moltiplicativo di un modulo N. Ed è così che possiamo ottenere l'; oppure si può calcolare l'inverso moltiplicativo di un numero a se è co - prime a N. Così che mi porta alla fine di questa lezione. Tanto per riassumere e questa lezione abbiamo appena discusso su un altissimo livello di base; alcuni dei fatti importanti dalla teoria dei numeri che abbiamo usato diffusamente durante la nostra discussione sulla crittografia a chiave pubblica. Nello specifico abbiamo visto; discusso di aritmetica modulare. Abbiamo visto un algoritmo di tempo polare per calcolare l'esponente modulare che è un'operazione fondamentale che eseguiamo in qualsiasi crittosistema a chiave pubblica o qualsiasi algoritmo di crittografia nella crittografia a chiave pubblica. Abbiamo anche discusso di un test di Primality, proprietà di numero primo. E abbiamo anche discusso di Extended Euclid di s Algoritmo per calcolare il GCD di due numeri e per calcolare i coefficienti di Bezout s i coefficienti saranno utili per calcolare l'inverso moltiplicativo dei numeri.