Superkasvava sekvenssi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 18. maaliskuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 16 muokkausta .

Jaksoa kutsutaan superkasvavaksi , jonka jokainen termi on suurempi kuin kaikkien aikaisempien termien summa . Muodollisesti positiivisten kokonaislukujen sarja on superkasvava, jos ehto [1] [2] täyttyy : $s_{1},s_{2},\dots$

${\displaystyle \forall n>1\ :\ s_{n}>\sum _{j=1}^{n-1}s_{j))$

Tätä sekvenssiluokkaa käytetään laajalti Merkle-Hellmanin selkäreppujen salausjärjestelmässä .

Esimerkiksi se on supernouseva, mutta ei. ${\näyttötyyli \{1,3,6,13,27,52\}}$ ${\näyttötyyli \{1,3,4,9,15,25\}}$

Menetelmät superkasvavan sekvenssin rakentamiseen

Oletetaan, että edessämme on tehtävä superkasvava sekvenssi tietylle määrälle kohteita . Elementti valitaan satunnaisesti tasaisesta luonnollisten lukujen jakaumasta seuraavalle segmentille: . Seuraava elementti valitaan tasaisesti segmentistä , sitä seuraavan sekvenssin jäsen valitaan segmentistä , elementti valitaan satunnaisesti segmentistä . Ilmeisesti tällaisilla sekvenssin jäsenten jakaumilla superkasvun ehto täyttyy, koska kunkin segmentin alaraja on täsmälleen yhtä suuri kuin edellisten segmenttien kaikkien oikeiden rajojen summa lisättynä yhdellä [3] . Muodostetaan esimerkiksi useita superkasvavia sekvenssejä tällä tavalla : ${\displaystyle \{s_{n}\}_{1}^{N))$ $N$ $s_{1}$ $[1,2^{N}]$ $s_{2}$ $[1\cdot 2^{N}+1,2\cdot 2^{N}]$ $[3\cdot 2^{N}+1,4\cdot 2^{N}]$ $s_{n}$ $[(2^{n-1}-1)\cdot 2^{N}+1,2^{n-1}\cdot 2^{N}]$ $N=5$

n	Jana	Esimerkki 1	Esimerkki 2	Esimerkki 3
yksi	${\näyttötyyli [1,32]}$	5	kymmenen	32
2	$[33,64]$	56	49	64
3	$[97,128]$	98	113	97
neljä	$[225,256]$	225	225	225
5	$[481,512]$	481	510	493

Rakentaminen satunnaisesti valitulla askeleella

Jos ovat satunnaisesti valittuja lukuja, niin superkasvavan sekvenssin loput alkiot löytyvät epäyhtälöstä [4] : $h,s_{1}\geq 1$

${\displaystyle s_{n}>h+\sum _{j=1}^{n-1}s_{j))$

Anna , . Silloin esimerkiksi sekvenssi täyttää ehdon ja on superkasvava. $h=10$ $s_{1}=9$ ${\näyttötyyli \{9,20,52,100,192\))$

Rakentaminen perustuu Fibonacci-sekvenssiin

Jokainen Fibonacci-sekvenssin elementti täyttää suhteen: , jonka nolla ja ensimmäinen jäsen ovat: . Tästä voidaan nähdä, että Fibonacci-sekvenssin ensimmäiset jäsenet: . Joskus saatat kohdata yleistyneen Fibonacci-sekvenssin . Tämä on sekvenssi, jonka jäsenet täyttävät yhtälön ehdon: . Toisin sanoen yleistetty sekvenssi saadaan klassisesta sekvenssistä muuttamalla Fibonacci-sekvenssin kahta ensimmäistä termiä ja se säilyttää seuraavien termien muodostusperiaatteen. Superkasvavan sekvenssin rakentamiseen käytetään yleistetyn Fibonacci-sekvenssin muotoa. Jotta voidaan laskea mikä tahansa superkasvavan sekvenssin jäsen , on valittava neljä elementtiä: kaksi alkutekijää ( ja ) ja kaksi positiivista tekijää ( ja ) [5] . ${\displaystyle u_{n+1}=u_{n}+u_{n-1))$ $u_{0}=0,u_{1}=1$ ${\näyttötyyli \{0,1,1,2,3,5,8,13,21,34,55,89,...\}}$ ${\displaystyle u_{n+1}=a\cdot u_{n}+b\cdot u_{n-1))$ ${\displaystyle \{s_{n}\}_{1}^{N))$ ${\displaystyle s_{1))$ $s_{2}$ $a$ $b$

Saamme seuraavat tapaukset:

Sarja täyttää superlisäysehdon kohteelle . $s_{1}<s_{2},a\leq b$
Sarja ei ole superkasvava kohteelle . $a>b$
Sekvenssi alkaa täyttää superkasvun ehtoa useiden iteraatioiden jälkeen . $s_{1}>s_{2},a\leq b$
Kohteessa , sarja pysyy superkasvavana. $s_{1}<s_{2},T={a \over b}<0.669$

Otetaan esimerkiksi . Tuloksena olevan superkasvavan sekvenssin ensimmäiset elementit ovat: . $s_{1}=2,s_{2}=3,a=5,b=7$ $\{2,3,5\cdot 3+7\cdot 2,5\cdot 29+7\cdot 3,5\cdot 166+7\cdot 29\}=\{2,3,29,166\}$

Olemassa olevan superkasvavan sarjan pohjalta

Ylikasvun edellytys täyttyy useilla tehoilla . Kun tiedämme superkasvavan sekvenssin , voimme muodostaa uuden joukon avulla . Toteutusta varten on sovellettava seuraavien toimintojen joukkoa [6] : ${\näyttötyyli 2}$ ${\displaystyle \{s_{n}\}_{1}^{N))$ ${\displaystyle \{s_{n}^{'}\}_{1}^{N))$ $\{1,2,2^{2},...,2^{N-1}\}$ ${\displaystyle \{s_{n}\}_{1}^{N))$

$n=1:\{s_{1}+1,s_{2}+1,s_{3}+2,...,s_{N-1}+2^{N-3},s_ {N}+2^{N-2}}\$

$\ldots$

$n=k:\{s_{1},s_{2},s_{3},...,s_{k}+1,s_{k+1}+1,...,s_{ N-1}+2^{Nk-2},s_{N}+2^{Nk-1}}\$

$...$

$n=N-1:\{s_{1},s_{2},s_{3},...,s_{N-1}+1,s_{N}+1}\$

$n=N:\{s_{1},s_{2},s_{3},...,s_{N-1},s_{N}+1}\$

Yksityiskohtainen esimerkki valitusta superkasvavasta sarjasta : ${\näyttötyyli \{3,6,13,27,52,105\}}$

	${\displaystyle s_{1))$	$s_{2}$	${\displaystyle s_{3))$	${\displaystyle s_{4))$	$s_{5}$	$s_{6}$
	$3$	$6$	$13$	$27$	$52$	$105$
$n = 1$	${\näyttötyyli 3+1=4}$	$6+1=7$	$13+2=15$	$27+2^{2}=31$	$52+2^{3}=60$	$105+2^{4}=121$
$n = 2$	$4$	$7+1=8$	$15+1=16$	$31+2=33$	$60+2^{2}=64$	$121+2^{3}=129$
$n = 3$	$4$	$8$	$16+1=17$	$33+1=34$	$64+2=66$	$129+2^{2}=133$
$n = 4$	$4$	$8$	$17$	$34+1=35$	$66+1=67$	$133+2=135$
$n = 5$	$4$	$8$	$17$	$35$	$67+1=68$	$135+1=136$
$n = 6$	$4$	$8$	$17$	$35$	$68$	$136+1=137$

Saimme uuden supernousevan sarjan . ${\displaystyle \{s_{n}^{'}\}_{1}^{N}=\{4,8,17,35,68,137\))$

Superkasvavan sekvenssin käyttö kryptografiassa

Super-Increasing Reput

Merkle-Hellmanin salausjärjestelmä perustuu "reppuongelmaan" - julkisen avaimen salausalgoritmiin - joka kuvataan alla. Ongelma näyttää tältä: annetaan sarja ei- toistuvia positiivisia kokonaislukuja. Kuulkoon luku myös luonnollisten lukujen joukkoon. Jos tämä on mahdollista, on tarpeen löytää joukko näennäissatunnaisia binäärisekvenssejä ehdon täyttämiseksi: [2] . $\{a_{n}\}_{1}^{N}$ $k$ ${\displaystyle \{b_{n}\}_{1}^{N))$ ${\displaystyle k=b_{1}a_{1}+b_{2}a_{2}+...+b_{n}a_{n))$

Antaa olla superincreasing sekvenssi. Tässä tapauksessa kohtaamme "kevyen" repun ongelman, jota ei ole vaikea ratkaista. Tätä varten sitä verrataan elementtiin . Jos , niin arvoa pienennetään ja siirrytään sekvenssin jäseneen . Toimia toistetaan, kunnes prosessi päättyy. Jos lopulta , niin ongelman ratkaisu löytyy sekvenssin muodossa , muuten sitä ei ole olemassa [2] . $\{a_{n}\}_{1}^{N}$ $k$ $a_{n}$ ${\displaystyle k\geq a_{n))$ $b_{n}=1$ $k$ $a_{n}$ $a_{n-1}$ $k=0$ ${\displaystyle \{b_{n}\}_{1}^{N))$

Jos järjestys ei ole supernouseva (tai normaali), reput ovat "kova" ongelma, joka voidaan ratkaista vain luettelemalla kaikki mahdolliset vaihtoehdot. $\{a_{n}\}_{1}^{N}$

Merkle-Hellman-algoritmin yksityinen avain on superkasvavan reppuongelman painosarja, kun taas julkinen avain on normaalin reppuongelman painosarja samalla ratkaisulla. On olemassa tapa muuntaa superkasvava repputehtävä normaaliksi repputehtäväksi modulaarista aritmetiikkaa käyttämällä. Normaalin reppusarjan saamiseksi käytämme superkasvavaa reppusarjaa. Otetaan esimerkiksi numerosarja: , ja modulo kerrotaan tämän sekvenssin jokainen elementti numerolla . Edellytyksenä on : moduulin arvon on oltava suurempi kuin sekvenssin kaikkien elementtien summa, esimerkiksi . Ja kertoimen on oltava suhteellisen alkuluku , jossa on modulo, esimerkiksi . Tässä tapauksessa normaali selkäreppujärjestys olisi [2] : ${\näyttötyyli \{2,3,7,13,27,61\))$ $m$ $n$ $m$ $m=115$ $n$ $n=31$

$2\cdot 31mod115=62;$

$3\cdot 31mod115=93;$

$7\cdot 31mod115=102;$

$13\cdot 31mod115=58;$

$27\cdot 31mod115=32;$

$61\cdot 31mod115=51.$

Saamme normaalin numerosarjan: . Superkasvava reppusarja on yksityinen avain, kun taas normaali reppusarja on julkinen avain. $\{62,93,102,58,32,51\}$

Monenvälisen salaisuuden jakamisen järjestelmä

Vuonna 2017 ehdotettiin monen osapuolen salaisen jakamisen järjestelmää, jossa käytetään supernousevaa sekvenssiä. Järjestelmän ainutlaatuisuus piilee siinä, että se ei ole vain monenvälinen, vaan se toteuttaa myös peräkkäisen pääsyn rakenteen tasoittain. Algoritmi käyttää Shamir-mallia tai pikemminkin salaisten osuuksien generointia, jota seuraa salainen palautusvaihe [7] .

Esitetään algoritmi monenvälisen salaisen jakamisjärjestelmän toteuttamiseksi.

Salaisten osuuksien luominen [8]

Vaihe 1.1. Valitaan salaisuus , jossa on jokin kaikkien osapuolten tiedossa oleva alkuluku, joka määrittää lopullisen kokokentän . Olkoon , missä on niiden osallistujien määrä, joiden kesken sinun on jaettava salaisuus . ${\displaystyle s\in \mathbb {Z} _{p}-\{0\))$ $s$ $s$ $p=2^{l-1}$ $l$ $s$

Vaihe 1.2. Muunnetaan salaisuus -bittiseksi näennäissatunnaiseksi binäärilukujärjestelmäksi ja muodostetaan sekvenssi . $s$ ${\näyttötyyli (l-1)}$ ${\displaystyle st=\{s_{l-1},s_{l-2},s_{l-3},...,s_{3},s_{2},s_{1}\))$

Vaihe 1.3. Tehdään satunnaisesti valituista elementeistä pituinen binäärisekvenssi : . $l-1$ ${\displaystyle \{e_{l-1},e_{l-2},e_{l-3},...,e_{3},e_{2},e_{1}\))$

Vaihe 1.4. Käytämme XOR - operaatiota vaiheiden 1.2 ja 1.3 sekvenssien elementtien välillä. Tuloksena saamme uuden sekvenssin: . $st^{'}=\{s_{l-1}\oplus e_{l-1},s_{l-2}\oplus e_{l-2},s_{l-3}\oplus e_ {l-3},...,s_{3}\oplus e_{3},s_{2}\oplus e_{2},s_{1}\oplus e_{1}\}=\{s_{l -1}^{'},s_{l-2}^{'},s_{l-3}^{'},...,s_{3}^{'},s_{2}^{' },s_{1}^{'}\}$

Vaihe 1.5. Rakennetaan superkasvava sarja satunnaislukuja, joiden pituus on : . $l-1$ ${\displaystyle w=\{w_{l-1},w_{l-2},w_{l-3},...,w_{3},w_{2},w_{1}\))$

Vaihe 1.6. Laskemme summan , joka on kaikkien osallistujien tiedossa. Toiminnan pseudokoodi: $u=pussisumma(st^{'},w)$

funktio bugsum(a, b); Syöte: ja . lähtö: summa. summa ; for i r do summa summa ; loppu

a=\{a_{1},...,a_{r}}\

b=\{b_{1},...,b_{r}\}

\leftarrow 0

\sisään

\leftarrow

+

{\displaystyle a_{i}\times b_{i))

palautussumma;

Vaihe 1.7. Valitse alkuluku , joka ilmoitetaan kaikille osallistujille ja sellainen, että: ja for , jossa tasojen lukumäärä ja tason osallistujien kokonaismäärä . $q$ $w_{1}+w_{2}+w_{3}+...+w_{l-1}<q$ $\max(n_{i})$ $1\leq i\leq l$ $i-$ $n_{i}-$ $i$

Vaihe 1.8. Jaamme kaikkien tason osallistujien kesken käyttämällä , jossa määrittää Shamir-kaavion polynomin asteen tasolla . Seuraavaksi sinun on muutettava vaiheen 1.3 sekvenssin elementit desimaalijärjestelmään ja jaettava ne myös tasoittain käyttämällä . $w_{i}$ $i$ ${\näyttötyyli (t_{i}, n_{i})}$ ${\displaystyle t_{i}<n_{i))$ $F(x)$ $i$ $l$ ${\näyttötyyli (t_{l}, n_{l})}$

Salainen palautusvaihe [8]

Vaihe 2.1. Osallistujat saavat vähintään salaisuuden takaisin tasolle ja saavat osuuden . ${\näyttötyyli t_{i))$ $i$ $w_{i}$ $1\leq i\leq l-1$

Vaihe 2.2. Ensimmäinen taso tarkistaa, onko se todella totta vaiheessa 1.6 saadulle summalle. Jos epäyhtälö on tosi, ensimmäinen taso tulostaa ja lähettää toiselle tasolle uuden summa-arvon: . Muussa tapauksessa se tulostaa ja lähettää seuraavalle kerrokselle ja lisää tulosbittinsä tyhjään sekvenssiin . On tarpeen käydä läpi kaikki tasot täyttämällä sekvenssi vähitellen . $u\geq w_{1}$ $yksi$ ${\displaystyle u_{1,2}^{'}=u-w_{1))$ $0$ $u_{1,2}^{'}=u$ $0$ $st^{''}$ $st^{''}$

Vaihe 2.3. Taso suorittaa salaisen palautuksen ja sekvenssikylvön . Toistamme vaiheessa 1.4 suoritetut laskelmat XOR-operaatiolla: . $l$ $\{e_{l-1}^{'},e_{l-2}^{'},e_{l-3}^{'},...,e_{3}^{'} ,e_{2}^{'},e_{1}^{'}\}$ $st=\{e_{l-1}^{'}\oplus s_{l-1}^{'},e_{l-2}^{'}\oplus s_{l-2}^{ '},e_{l-3}^{'}\oplus s_{l-3}^{'},...,e_{3}^{'}\oplus s_{3}^{'},e_ {2}^{'}\oplus s_{2}^{'},e_{1}^{'}\oplus s_{1}^{'}\}$

Vaihe 2.4 . Lopuksi saimme salaisen binäärisekvenssin, joka voidaan muuntaa desimaaliluvuksi salaisuuden saamiseksi . $s$

Muistiinpanot

↑ Richard A. Mollin, Johdatus kryptografiaan (diskreetti matematiikka ja sovellukset) , Chapman & Hall/CRC; 1 painos (10. elokuuta 2000), ISBN 1-58488-127-5
↑ 1 2 3 4 Schneier, 1993 .
↑ Merkle, Hellman, 1978 .
↑ Salomaa, 1995 .
↑ Merzouga, Ali-Pachab, Hadj-Saidb, Ali-Pachab, 2019 .
↑ Murin, 2011 .
↑ Basit, Chanakya, Venkaiah, Abdul Moiz, 2020 .
↑ 1 2 Harsha, Chanakya, Vadlamudi Kiina Venkaiah, 2017 .

Kirjallisuus

Bruce Schneier. Sovellettu kryptografia: protokollat, algoritmit ja lähdekoodi julkaisussa C. - 1993. - P. 463-465. — ISBN 978-0471117094 .
Merkle RC ja Hellman ME Trapdoor -reppu. - 1978. - S. 525-526.
Salomaa A. Julkisen avaimen kryptografia. – 1995.
A. Merzouga, A. Ali-Pachab, N. Hadj-Saidb, H. Ali-Pachab. Erittäin kasvavan sekvenssin tuottaminen Fibonaci-sekvenssin perusteella . – 2019.
P. Harsha, P. Chanakya ja Vadlamudi China Venkaiah. Uudelleen käytettävä moniosainen salainen jakojärjestelmä, joka perustuu lisääntyvään järjestykseen . – 2017.
A. Basit, P. Chanakya, V. Ch. Venkaiah ja S. Abdul Moiz. Uusi monisalainen jakamisjärjestelmä, joka perustuu tasojärjestetyn käyttöoikeusrakenteen supernousevaan järjestykseen . – 2020.
Murin DM Injektio- ja superkasvavien reppuvektorien lukumäärän kasvujärjestyksessä . – 2011.

Linkit

Super kasvavat sekvenssit