Përmbledhje e përparimeve më të fundit në kriptografi. Çështja e parë

Shembulli 13.13

Për cilën vlerë të n-së grupi ka rrënjë primitive: 17, 20, 38 dhe 50?

Zgjidhje

a. ka rrënjë primitive sepse 17 është një numër i thjeshtë (p t, ku t është 1).

b. nuk ka rrënjë primitive.

c. dhe 19 është një numër i thjeshtë.

d. ka rrënjë primitive sepse , dhe 5 është një numër i thjeshtë.

Nëse një grup ka një rrënjë primitive, ai zakonisht ka disa rrënjë të tilla. Numri i rrënjëve primitive mund të llogaritet si - . Për shembull, numri i rrënjëve primitive - Kjo -. Ju lutemi vini re se së pari duhet të kontrolloni nëse grupi ka ndonjë rrënjë primitive përpara se të gjeni numrin e rrënjëve.

Nëse grupi G =< Z n* , x > ka të paktën një rrënjë primitive, atëherë numri i rrënjëve primitive është ((n))

Le të shqyrtojmë tre pyetje:

1. Duke pasur parasysh një element a dhe një grup, si mund të përcaktohet nëse a është një rrënjë primitive e G? Kjo nuk është një detyrë aq e lehtë.

A. Ne duhet të gjejmë - kjo detyrë është e ngjashme në kompleksitet me detyrën e faktorizimit të numrit n.

b. Duhet të gjejmë .

2. Duke pasur parasysh një grup, si të gjeni të gjitha rrënjët primitive? Ky problem është më i vështirë se problemi i parë sepse duhet të përsërisim llogaritjet në hapin 1.b për të gjithë grupin.

3. Nëse jepet një grup, atëherë si të zgjedhim një rrënjë primitive G? Në kriptografi, ne duhet të gjejmë të paktën një rrënjë primitive në një grup. Megjithatë, në këtë rast, vlera e n zgjidhet nga përdoruesi dhe përdoruesi e di . Përdoruesi provon disa elementë me radhë derisa të gjejë të parin.

Grupi ciklik. Grupet ciklike tashmë janë diskutuar në leksionet 5-6. Ju lutemi vini re se nëse një grup ka rrënjë primitive, atëherë ato përsëriten në mënyrë ciklike. Çdo rrënjë primitive është një gjenerator dhe mund të përdoret për të krijuar një grup të tërë. Me fjalë të tjera, nëse g është një rrënjë primitive në një grup, ne mund të gjenerojmë grupin Zn* si

Shembulli 13.14

Grupi ka dy rrënjë primitive, sepse dhe . Ju mund të gjeni rrënjë primitive - këto janë 3 dhe 7. Më poshtë është se si mund të krijoni një grup të tërë Z 10* duke përdorur çdo rrënjë primitive.

g = 3 -> g 1 mod 10 = 3 g 2 mod 10 = 9 g 3 mod 10 = 7 g 4 mod 10 = 1 g = 7 -> g 1 mod 10 = 7 g 2 mod 10 = 9 g 3 mod 10 = 3 g 4 mod 10 = 1

Ju lutemi vini re se grupi gjithmonë ciklike sepse p është i thjeshtë.

Grupi G =< Z n * , x >është një grup ciklik nëse ka rrënjë primitive. Grupi G =< Z p * , x >është gjithmonë ciklik.

Ideja e një logaritmi diskret. Grupi ka disa veti interesante.

Zgjidhja e logaritmit modular duke përdorur logaritme diskrete

Tani le të shohim se si zgjidhen probleme si y = a x (mod n), pra jepet y, dhe ne duhet të gjejmë x.

Tabelimi i logaritmeve diskrete. Një mënyrë për të zgjidhur problemin e mësipërm është përdorimi i një tabele për çdo Z p* dhe bazat e ndryshme. Ky lloj tabele mund të parallogaritet dhe ruhet. Për shembull, Tabela 13.4 tregon vlerat logaritmi diskret për Z 7*. Ne e dimë se kemi dy rrënjë ose baza primitive në këtë grup.

Bërja e tavolinave për të tjerët logaritme diskrete për të gjitha grupet dhe të gjitha bazat e mundshme, ne mund të zgjidhim çdo problem logaritmike diskrete. Kjo qasje është e ngjashme me logaritmet tradicionale të studiuara në të kaluarën. Para ardhjes së kalkulatorëve dhe kompjuterëve, tabelat u përdorën për të llogaritur logaritmet në bazën 10.

Shembulli 13.15

Gjeni x në secilin nga rastet e mëposhtme:

a.

b.

Ne mund të përdorim lehtësisht tabelën 13.4 logaritmi diskret.

Logaritmi diskret

Logaritmi diskret(DLOG) – detyrë e përmbysjes së funksionit g x në ndonjë grup shumëzues të fundëm G .

Më shpesh, problemi i logaritmit të floppy konsiderohet në grupin e elementeve të kthyeshëm të unazës së mbetur, në grupin shumëzues të një fushe të fundme ose në grupin e pikave në një kurbë eliptike mbi një fushë të fundme. Algoritmet efikase për zgjidhjen e problemit të logaritmit të floppy janë përgjithësisht të panjohur.

Për të dhënë g Dhe a zgjidhje x ekuacionet g x = a thirrur logaritmi diskret element a bazuar në g. Në rast se Gështë grupi i elementeve të kthyeshëm të modulit të unazës së mbetur m, quhet edhe zgjidhja indeks numrat a bazuar në g. Indeksi i numrave a bazuar në gështë e garantuar të ekzistojë nëse gështë një modul rrënjësor primitiv m.

Zgjidhja për problemin e logaritmit diskret është gjetja e një numri të plotë jo negativ x, ekuacioni i kënaqshëm (1). Nëse është e zgjidhshme, duhet të ketë të paktën një zgjidhje natyrale që nuk e kalon rendin e grupit. Kjo menjëherë jep një vlerësim të përafërt të kompleksitetit të algoritmit për gjetjen e zgjidhjeve nga lart - një algoritëm shterues kërkimi do të gjente një zgjidhje në një numër hapash jo më të lartë se rendi i grupit të caktuar.

Më shpesh, rasti konsiderohet kur , domethënë, grupi është ciklik i krijuar nga elementi g. Në këtë rast, ekuacioni ka gjithmonë një zgjidhje. Në rastin e një grupi arbitrar, çështja e zgjidhshmërisë së problemit të logaritmit diskret, domethënë çështja e ekzistencës së zgjidhjeve të ekuacionit (1), kërkon shqyrtim të veçantë.

Shembull

Mënyra më e lehtë është ta konsiderojmë problemin e logaritmit diskret në modulin e unazës së mbetur si një numër të thjeshtë.

Le të jepet krahasimi

Ne do ta zgjidhim problemin duke përdorur metodën e forcës brutale. Le të shkruajmë një tabelë me të gjitha fuqitë e numrit 3. Sa herë që llogarisim pjesën e mbetur të pjesëtimit me 17 (për shembull, 3 3 ≡27 - pjesa e mbetur e pjesëtimit me 17 është 10).

Tani është e lehtë të shihet se zgjidhja e krahasimit në fjalë është x=4, që nga 3 4 ≡13.

Në praktikë, moduli është zakonisht një numër mjaft i madh që metoda e forcës brutale është shumë e ngadaltë, kështu që ka nevojë për algoritme më të shpejtë.

Algoritmet e zgjidhjes

Në një grup shumëzues arbitrar

Artikulli i kushtohet zgjidhshmërisë dhe zgjidhjes së problemit të logaritmit diskret në një grup arbitrar të fundëm abelian BuchmannJ., Jacobson M.J., Teske E. Mbi disa probleme llogaritëse në grupet abeliane të fundme. Algoritmi përdor një tabelë të përbërë nga çifte elementësh dhe kryen shumëzimet. Ky algoritëm është i ngadalshëm dhe i papërshtatshëm për përdorim praktik. Grupet specifike kanë algoritmet e tyre, më efektive.

Një mundësi tjetër për zgjidhjen efikase të problemit të llogaritjes së një logaritmi diskrete përfshin llogaritjen kuantike. Teorikisht është vërtetuar se, duke i përdorur ato, logaritmi diskret mund të llogaritet në kohë polinomiale. Në çdo rast, nëse zbatohet algoritmi polinomial për llogaritjen e logaritmit diskret, kjo do të nënkuptojë papërshtatshmërinë praktike të kriptosistemeve të bazuara në të.

Skemat klasike kriptografike të bazuara në kompleksitetin e problemit të logaritmit diskret janë skema e gjenerimit të çelësit publik Diffie-Hellman, skema e nënshkrimit elektronik El-Gamal dhe kriptosistemi Massey-Omura për transmetimin e mesazheve.

Lidhjet

• Vasilenko O. N. Algoritmet teorike të numrave në kriptografi. - Moskë: MTsNMO, 2003. - 328 f. - ISBN 5-94057-103-4
• Koblitz N. Kursi i teorisë së numrave dhe kriptografisë. - Moskë: TVPb, 2001. - 254 f. - ISBN 5-85484-014-6
• Odlyzko A. M. Logaritmet diskrete në fusha të fundme dhe rëndësia e tyre kriptografike // LNCS. - 1984. - T. 209. - F. 224-316.
• Buchmann J., Jacobson M.J., Teske E. Mbi disa probleme llogaritëse në grupet abeliane të fundme // Matematika e Llogaritjes. - 1997. - T. 66. - Nr 220. - F. 1663-1687.
• Neni Logaritmi diskret në faqen e internetit të Rrjetit Shkencor
• Rishikimi i metodave për llogaritjen e logaritmeve diskrete (në Anglisht)
• Nechaev V.I. Në çështjen e kompleksitetit të një algoritmi determinist për një logaritëm diskret // Shënime matematike. - 1994. - V. 2. - T. 55. - F. 91-101.

Fondacioni Wikimedia. 2010.

Shihni se çfarë është "Logaritmi diskret" në fjalorë të tjerë:

logaritmi diskret- Në grup ka dy elementë d; g janë të tilla që ka një numër të plotë r që plotëson kushtin gr = d; r quhet logaritmi diskret i d në bazën g. Temat teknologjia e informacionit në përgjithësi EN logaritmi diskrete ... Udhëzues teknik i përkthyesit

Algoritmi Hellman i Polig (i quajtur edhe algoritmi Hellman i Silver Polig) është një algoritëm diskret determinist i logaritmit në unazën e mbetjes që modulon një numër të thjeshtë. Një nga veçoritë e algoritmit është se... ... Wikipedia

- (Anglisht: Baby step step giant; i quajtur edhe algoritmi i hapave të mëdhenj dhe të vegjël) në teorinë e grupeve, një algoritëm përcaktues për logaritmin diskret në unazën e mbetur modulon një numër të thjeshtë. Për modulet e një lloji të veçantë kjo ... ... Wikipedia

Pra, ne kemi fuqi prej dy. Nëse e merrni numrin nga fundi, mund të gjeni lehtësisht fuqinë në të cilën do t'ju duhet të ngrini dy për të marrë këtë numër. Për shembull, për të marrë 16, ju duhet të ngrini dy në fuqinë e katërt. Dhe për të marrë 64, ju duhet të ngrini dy në fuqinë e gjashtë. Kjo mund të shihet nga tabela.

Dhe tani - në fakt, përkufizimi i logaritmit:

Baza e një logaritmi të x është fuqia në të cilën duhet të rritet a për të marrë x.

Përcaktimi: log a x = b, ku a është baza, x është argumenti, b është ajo me çfarë logaritmi është në të vërtetë i barabartë.

Për shembull, 2 3 = 8 ⇒ log 2 8 = 3 (logaritmi bazë 2 i 8 është tre sepse 2 3 = 8). Me të njëjtin regjistër suksesi 2 64 = 6, pasi 2 6 = 64.

Veprimi i gjetjes së logaritmit të një numri në një bazë të caktuar quhet logaritmizim. Pra, le të shtojmë një rresht të ri në tabelën tonë:

Fatkeqësisht, jo të gjitha logaritmet llogariten kaq lehtë. Për shembull, provoni të gjeni regjistrin 2 5 . Numri 5 nuk është në tabelë, por logjika dikton që logaritmi do të shtrihet diku në segment. Sepse 2 2< 5 < 2 3 , а чем больше степень двойки, тем больше получится число.

Numra të tillë quhen irracionalë: numrat pas presjes dhjetore mund të shkruhen pafundësisht dhe nuk përsëriten kurrë. Nëse logaritmi rezulton irracional, është më mirë ta lëmë kështu: log 2 5, log 3 8, log 5 100.

Është e rëndësishme të kuptohet se një logaritëm është një shprehje me dy variabla (bazën dhe argumentin). Në fillim, shumë njerëz ngatërrojnë se ku është baza dhe ku është argumenti. Për të shmangur keqkuptimet e bezdisshme, mjafton të shikoni foton:

Para nesh nuk është gjë tjetër veçse përkufizimi i një logaritmi. Mbani mend: logaritmi është një fuqi, në të cilën duhet të ndërtohet baza për të marrë një argument. Është baza që është ngritur në një fuqi - është e theksuar me të kuqe në foto. Rezulton se baza është gjithmonë në fund! Unë u them studentëve të mi këtë rregull të mrekullueshëm që në mësimin e parë - dhe nuk lind asnjë konfuzion.

Ne e kemi kuptuar përkufizimin - gjithçka që mbetet është të mësojmë se si të numërojmë logaritmet, d.m.th. hiqni qafe shenjën "log". Për të filluar, vërejmë se nga përkufizimi rrjedhin dy fakte të rëndësishme:

1. Argumenti dhe baza duhet të jenë gjithmonë më të mëdha se zero. Kjo rrjedh nga përkufizimi i një shkalle nga një eksponent racional, në të cilin reduktohet përkufizimi i një logaritmi.
2. Baza duhet të jetë e ndryshme nga një, pasi një në çdo shkallë mbetet ende një. Për shkak të kësaj, pyetja "në çfarë fuqie duhet të ngrihet për të marrë dy" është e pakuptimtë. Nuk ka një diplomë të tillë!

Kufizime të tilla quhen varg vlerash të pranueshme(ODZ). Rezulton se ODZ e logaritmit duket kështu: log a x = b ⇒ x > 0, a > 0, a ≠ 1.

Vini re se nuk ka kufizime në numrin b (vlera e logaritmit). Për shembull, logaritmi mund të jetë negativ: log 2 0.5 = -1, sepse 0,5 = 2 −1.

Megjithatë, tani po shqyrtojmë vetëm shprehjet numerike, ku nuk kërkohet të dihet VA e logaritmit. Të gjitha kufizimet tashmë janë marrë parasysh nga autorët e detyrave. Por kur ekuacionet logaritmike dhe pabarazitë hyjnë në lojë, kërkesat DL do të bëhen të detyrueshme. Në fund të fundit, baza dhe argumenti mund të përmbajnë ndërtime shumë të forta që nuk korrespondojnë domosdoshmërisht me kufizimet e mësipërme.

Tani le të shohim skemën e përgjithshme për llogaritjen e logaritmeve. Ai përbëhet nga tre hapa:

1. Shprehni bazën a dhe argumentin x si fuqi me bazën minimale të mundshme më të madhe se një. Gjatë rrugës, është më mirë të heqësh qafe numrat dhjetorë;
2. Zgjidheni ekuacionin për ndryshoren b: x = a b ;
3. Numri b që rezulton do të jetë përgjigja.

Kjo eshte e gjitha! Nëse logaritmi rezulton irracional, kjo do të jetë e dukshme që në hapin e parë. Kërkesa që baza të jetë më e madhe se një është shumë e rëndësishme: kjo zvogëlon gjasat e gabimit dhe thjeshton shumë llogaritjet. Është e njëjta gjë me thyesat dhjetore: nëse i shndërroni menjëherë në ato të zakonshme, do të ketë shumë më pak gabime.

Le të shohim se si funksionon kjo skemë duke përdorur shembuj specifikë:

Detyrë. Llogaritni logaritmin: log 5 25

1. Le të imagjinojmë bazën dhe argumentin si një fuqi prej pesë: 5 = 5 1 ; 25 = 5 2;

Le të krijojmë dhe zgjidhim ekuacionin:
log 5 25 = b ⇒ (5 1) b = 5 2 ⇒ 5 b = 5 2 ⇒ b = 2 ;

2. Morëm përgjigjen: 2.

Detyrë. Llogaritni logaritmin:

Detyrë. Llogaritni logaritmin: log 4 64

1. Le të imagjinojmë bazën dhe argumentin si një fuqi prej dy: 4 = 2 2 ; 64 = 2 6;
2. Le të krijojmë dhe zgjidhim ekuacionin:
   log 4 64 = b ⇒ (2 2) b = 2 6 ⇒ 2 2b = 2 6 ⇒ 2b = 6 ⇒ b = 3 ;
3. Morëm përgjigjen: 3.

Detyrë. Llogaritni logaritmin: log 16 1

1. Le të imagjinojmë bazën dhe argumentin si një fuqi prej dy: 16 = 2 4 ; 1 = 2 0 ;
2. Le të krijojmë dhe zgjidhim ekuacionin:
   log 16 1 = b ⇒ (2 4) b = 2 0 ⇒ 2 4b = 2 0 ⇒ 4b = 0 ⇒ b = 0 ;
3. Morëm përgjigjen: 0.

Detyrë. Llogaritni logaritmin: log 7 14

1. Le të imagjinojmë bazën dhe argumentin si një fuqi prej shtatë: 7 = 7 1 ; 14 nuk mund të përfaqësohet si një fuqi e shtatë, pasi 7 1< 14 < 7 2 ;
2. Nga paragrafi i mëparshëm rezulton se logaritmi nuk llogaritet;
3. Përgjigja është pa ndryshim: log 7 14.

Një shënim i vogël në shembullin e fundit. Si mund të jeni i sigurt se një numër nuk është një fuqi e saktë e një numri tjetër? Është shumë e thjeshtë - thjesht vendoseni në faktorët kryesorë. Nëse zgjerimi ka të paktën dy faktorë të ndryshëm, numri nuk është një fuqi e saktë.

Detyrë. Zbuloni nëse numrat janë fuqi të sakta: 8; 48; 81; 35; 14 .

8 = 2 · 2 · 2 = 2 3 - shkalla e saktë, sepse ka vetëm një shumëzues;
48 = 6 · 8 = 3 · 2 · 2 · 2 · 2 = 3 · 2 4 - nuk është një fuqi e saktë, pasi ekzistojnë dy faktorë: 3 dhe 2;
81 = 9 · 9 = 3 · 3 · 3 · 3 = 3 4 - shkalla e saktë;
35 = 7 · 5 - përsëri jo një fuqi e saktë;
14 = 7 · 2 - përsëri jo një shkallë e saktë;

Vini re gjithashtu se vetë numrat e thjeshtë janë gjithmonë fuqi të sakta të tyre.

Logaritmi dhjetor

Disa logaritme janë aq të zakonshme sa kanë një emër dhe simbol të veçantë.

Logaritmi dhjetor i x është logaritmi me bazën 10, d.m.th. Fuqia në të cilën duhet të rritet numri 10 për të marrë numrin x. Emërtimi: lg x.

Për shembull, log 10 = 1; log 100 = 2; lg 1000 = 3 - etj.

Që tani e tutje, kur një frazë si "Gjeni lg 0.01" shfaqet në një libër shkollor, dijeni se kjo nuk është një gabim shtypi. Ky është një logaritëm dhjetor. Sidoqoftë, nëse nuk jeni të njohur me këtë shënim, gjithmonë mund ta rishkruani atë:
log x = log 10 x

Çdo gjë që është e vërtetë për logaritmet e zakonshme është gjithashtu e vërtetë për logaritmet dhjetore.

Logaritmi natyror

Ekziston një logaritëm tjetër që ka përcaktimin e vet. Në disa mënyra, është edhe më i rëndësishëm se dhjetori. Po flasim për logaritmin natyror.

Logaritmi natyror i x është logaritmi me bazën e, d.m.th. fuqia në të cilën duhet të rritet numri e për të marrë numrin x. Emërtimi: ln x.

Shumë do të pyesin: cili është numri e? Ky është një numër irracional, vlera e tij e saktë nuk mund të gjendet dhe të shkruhet. Unë do të jap vetëm shifrat e para:
e = 2.718281828459...

Ne nuk do të hyjmë në detaje se çfarë është ky numër dhe pse është i nevojshëm. Vetëm mbani mend se e është baza e logaritmit natyror:
ln x = log e x

Kështu ln e = 1; ln e 2 = 2; ln e 16 = 16 - etj. Nga ana tjetër, ln 2 është një numër irracional. Në përgjithësi, logaritmi natyror i çdo numri racional është irracional. Përveç, natyrisht, për një: ln 1 = 0.

Për logaritmet natyrore, të gjitha rregullat që janë të vërteta për logaritmet e zakonshme janë të vlefshme.

Pyetjet më të shpeshta

A është e mundur të bëhet një vulë në një dokument sipas mostrës së dhënë? Përgjigju Po, është e mundur. Dërgoni një kopje të skanuar ose një foto me cilësi të mirë në adresën tonë të emailit dhe ne do të bëjmë kopjen e nevojshme.

Çfarë lloje pagese pranoni? Përgjigju Ju mund të paguani për dokumentin pas marrjes nga korrieri, pasi të kontrolloni korrektësinë e përfundimit dhe cilësinë e ekzekutimit të diplomës. Kjo mund të bëhet edhe në zyrat e kompanive postare që ofrojnë shërbime me para në dorë.
Të gjitha kushtet e dorëzimit dhe pagesës për dokumentet përshkruhen në seksionin "Pagesa dhe Dorëzimi". Ne jemi gjithashtu të gatshëm të dëgjojmë sugjerimet tuaja në lidhje me kushtet e dorëzimit dhe pagesës për dokumentin.

A mund të jem i sigurt që pas vendosjes së një porosie nuk do të zhdukesh me paratë e mia? Përgjigju Ne kemi një përvojë mjaft të gjatë në fushën e prodhimit të diplomave. Ne kemi disa faqe interneti që përditësohen vazhdimisht. Specialistët tanë punojnë në pjesë të ndryshme të vendit, duke prodhuar mbi 10 dokumente në ditë. Gjatë viteve, dokumentet tona kanë ndihmuar shumë njerëz të zgjidhin problemet e punësimit ose të kalojnë në punë me paga më të larta. Ne kemi fituar besimin dhe njohjen midis klientëve, kështu që nuk ka absolutisht asnjë arsye që ne ta bëjmë këtë. Për më tepër, kjo është thjesht e pamundur të bëhet fizikisht: ju paguani për porosinë tuaj kur e merrni në duart tuaja, nuk ka parapagim.

A mund të porosis një diplomë nga ndonjë universitet? Përgjigju Në përgjithësi, po. Ne kemi punuar në këtë fushë për gati 12 vjet. Gjatë kësaj kohe u formua një bazë pothuajse e plotë e dokumenteve të lëshuara nga pothuajse të gjitha universitetet e vendit dhe për vite të ndryshme lëshimi. Gjithçka që ju nevojitet është të zgjidhni një universitet, specialitet, dokument dhe të plotësoni formularin e porosisë.

Çfarë duhet të bëni nëse gjeni gabime shtypi dhe gabime në një dokument? Përgjigju Kur merrni një dokument nga korrieri ose kompania jonë postare, ju rekomandojmë që të kontrolloni me kujdes të gjitha detajet. Nëse zbulohet një gabim shtypi, gabim ose pasaktësi, ju keni të drejtë të mos e merrni diplomën, por defektet e zbuluara duhet t'i tregoni personalisht korrierit ose me shkrim duke dërguar një email.
Do ta korrigjojmë dokumentin sa më shpejt të jetë e mundur dhe do ta ridërgojmë në adresën e specifikuar. Natyrisht, transporti do të paguhet nga kompania jonë.
Për të shmangur keqkuptime të tilla, përpara se të plotësoni formularin origjinal, i dërgojmë me email klientit një model të dokumentit të ardhshëm për të kontrolluar dhe miratuar versionin përfundimtar. Përpara dërgimit të dokumentit me korrier ose postë, ne bëjmë gjithashtu foto dhe video shtesë (përfshirë dritën ultravjollcë) në mënyrë që të keni një ide të qartë se çfarë do të merrni në fund.

Çfarë duhet të bëj për të porositur një diplomë nga kompania juaj? Përgjigju Për të porositur një dokument (certifikatë, diplomë, certifikatë akademike, etj.), duhet të plotësoni formularin e porosisë online në faqen tonë të internetit ose të jepni emailin tuaj në mënyrë që ne t'ju dërgojmë një formular aplikimi, të cilin duhet ta plotësoni dhe ta dërgoni përsëri. tek ne.
Nëse nuk dini çfarë të tregoni në ndonjë fushë të formularit/pyetësorit të porosisë, lini ato bosh. Prandaj, ne do t'i sqarojmë të gjitha informacionet që mungojnë përmes telefonit.

Vlerësimet e fundit

Valentina:

Ju e shpëtuat djalin tonë nga shkarkimi! Fakti është se, pasi u largua nga kolegji, djali im u bashkua me ushtrinë. Dhe kur u kthye, ai nuk donte të shërohej. Punoi pa diplomë. Por kohët e fundit ata filluan të pushojnë të gjithë ata që nuk kanë një "korre". Kjo është arsyeja pse ne vendosëm t'ju kontaktojmë dhe nuk u penduam! Tani ai punon me qetësi dhe nuk ka frikë nga asgjë! Faleminderit!

Logaritmi diskret(DLOG) - detyrë e përmbysjes së funksionit g x (\displaystyle g^(x)) në ndonjë grup shumëzues të fundëm G (\displaystyle G).

Më shpesh, problemi diskrete i logaritmit konsiderohet në grupin shumëzues të një unaze mbetjeje ose një fushe të fundme, si dhe në grupin e pikave të një kurbë eliptike mbi një fushë të fundme. Algoritmet efikase për zgjidhjen e problemit të logaritmit diskret janë përgjithësisht të panjohur.

Për të dhënë g Dhe a zgjidhje x quhet ekuacion logaritmi diskret element a bazuar në g. Në rast se Gështë grupi shumëzues i modulit të unazës së mbetur m, quhet edhe zgjidhja indeks numrat a bazuar në g. Indeksi i numrave a bazuar në gështë e garantuar të ekzistojë nëse gështë një modul rrënjësor primitiv m.

YouTube enciklopedik

1 / 5

✪ Detyra e llogaritjes së logaritmit diskret

✪ Logaritmi diskret (pjesa 11)| Kriptografia | Programimi

✪ Protokolli Diffie-Hellman (pjesa 12) | Kriptografia | Programimi

✪ Makinë portative enkriptimi "Enigma" (pjesa 6) | Kriptografia | Programimi

✪ Vernam Shipher (pjesa 4) | Kriptografia | Programimi

Titra

Ne kemi nevojë për një procedurë numerike që është e lehtë për t'u bërë në një drejtim dhe shumë më e vështirë për t'u bërë në drejtim të kundërt. Kjo na sjell në aritmetikën modulare, e njohur edhe si "aritmetika e orës" (ose "mbetja"). Për shembull, për të gjetur modulin 46 12, mund të merrni një litar 46 njësi të gjatë dhe ta mbështillni atë rreth orës, që quhet modul. Aty ku mbaron litari është zgjidhja. Kjo do të thotë, 46 moduli 12 është i barabartë me 10. Është e thjeshtë. Tani le të marrim një modul të thjeshtë për ta bërë këtë. 17, për shembull. Pastaj gjejmë rrënjën primitive të 17, në këtë rast tre. Ka një veti shumë të rëndësishme kur ngrihet në fuqi të ndryshme - vlerat shpërndahen në mënyrë të barabartë gjatë gjithë orës. 3 quhet elementi gjenerues ose gjenerator. Nëse ngreni 3 në çdo fuqi x, atëherë rezultati ka të ngjarë të jetë njësoj çdo numër nga 1 në 16. Kjo do të thotë, procedura e kundërt është mjaft e ndërlikuar. Thuaj, cila fuqi prej 3 do të rezultojë në 12? Ky është problemi i llogaritjes së logaritmit diskret. Dhe tani kemi një funksion njëkahësh. E thjeshtë për ekzekutim të drejtpërdrejtë dhe e vështirë për ekzekutim të kundërt. Për një numër të caktuar 12, duhet të drejtohemi për të provuar shumë opsione të gabuara për të gjetur eksponentin e duhur. Pra, sa e vështirë është? Epo, me vlera të vogla është e lehtë, por nëse përdoret një modul i thjeshtë me qindra karaktere, problemi bëhet pothuajse i pakapërcyeshëm. Edhe nëse keni akses në të gjithë fuqinë llogaritëse të Tokës, të provoni të gjitha opsionet mund të zgjasin mijëra vjet. Kështu, fuqia e një funksioni njëkahëshe bazohet në kohën që duhet për të kthyer konvertimin.

Formulimi i problemit

Lëreni disa grupe abeliane shumëzuese të fundme G (\displaystyle G) jepet ekuacioni

Zgjidhja për problemin e logaritmit diskret është gjetja e një numri të plotë jo negativ x (\displaystyle x), ekuacioni i kënaqshëm (1). Nëse është e zgjidhshme, duhet të ketë të paktën një zgjidhje natyrale që nuk e kalon rendin e grupit. Kjo menjëherë jep një vlerësim të përafërt të kompleksitetit të algoritmit për gjetjen e zgjidhjeve nga lart - një algoritëm shterues kërkimi do të gjente një zgjidhje në një numër hapash jo më të lartë se rendi i grupit të caktuar.

Rasti më i konsideruar është kur G = ⟨ g ⟩ (\displaystyle G=\langle g\rangle ), domethënë grupi është ciklik i gjeneruar nga elementi g (\displaystyle g). Në këtë rast, ekuacioni ka gjithmonë një zgjidhje. Në rastin e një grupi arbitrar, çështja e zgjidhshmërisë së problemit të logaritmit diskret, domethënë çështja e ekzistencës së zgjidhjeve të ekuacionit (1), kërkon shqyrtim të veçantë.

Shembull

Le të shqyrtojmë problemin e logaritmit diskret në modulin e unazës së mbetur, një numër i thjeshtë. Le të jepet krahasimi

Për numrat e një lloji të veçantë, rezultati mund të përmirësohet. Në disa raste, është e mundur të ndërtohet një algoritëm për të cilin do të jenë konstantet c ≈ 1,00475 (\displaystyle c\afërsisht 1,00475), d = 2 5 (\displaystyle d=(\frac (2)(5))). Për faktin se konstantja c (\displaystyle c)është mjaft afër 1, algoritme të ngjashme mund të tejkalojnë algoritmin me d = 1 3 (\displaystyle d=(\frac (1)(3))).

Në një fushë të fundme arbitrare

Problemi konsiderohet në terren  GF(q), Ku q = p n (\displaystyle q=p^(n)), p (\displaystyle p)- e thjeshtë.

Në një grup pikash në një kurbë eliptike

Konsiderohet një grup pikash të një kurbë eliptike mbi një fushë të fundme. Ky grup përcakton veprimin e shtimit të dy pikave. Pastaj m P (\displaystyle mP)- Kjo P + … + P ⏟ m (\stil i ekranit \nënbrace (P+\ldots +P) \ limitet _(m)). Zgjidhja e problemit të logaritmit diskret në një kurbë eliptike është gjetja e një numri të tillë natyror m (\displaystyle m), Çfarë m P = A (\displaystyle mP=A) për pikat e dhëna P (\displaystyle P) Dhe A. (\displaystyle A.)

Përpara vitit 1990, nuk kishte algoritme diskrete logaritmesh që merrnin parasysh veçoritë strukturore të një grupi pikash në një kurbë eliptike. Më pas, Alfred J. Menezes, Tatsuaki Okamoto dhe Scott A. Vanstone propozuan një algoritëm duke përdorur çiftimin Weyl. Për një kurbë eliptike të përcaktuar mbi një fushë G F (q) (\displaystyle GF(q)), ky algoritëm redukton problemin e logaritmit diskret në një problem të ngjashëm në terren G F (q k) (\displaystyle GF(q^(k))). Megjithatë, ky informacion është i dobishëm vetëm nëse diploma k (\displaystyle k) i vogël Ky kusht plotësohet kryesisht për kurbat eliptike mbisingulare. Në raste të tjera, një reduktim i tillë pothuajse kurrë nuk çon në algoritme nëneksponencialë.

Kompleksiteti kompjuterik dhe aplikimet në kriptografi

Problemi i logaritmit diskret është një nga problemet kryesore mbi të cilat bazohet kriptografia me çelës publik. Skemat klasike kriptografike të bazuara në të janë skema e çelësit publik Diffie-Hellman, skema e nënshkrimit elektronik El-Gamal dhe kriptosistemi Massey-Omura për transmetimin e mesazheve. Forca e tyre kriptografike bazohet në kompleksitetin e supozuar të lartë llogaritës të përmbysjes së funksionit eksponencial. Megjithëse vetë funksioni eksponencial llogaritet në mënyrë mjaft efikase, edhe algoritmet më moderne për llogaritjen e logaritmit diskret kanë një kompleksitet shumë të lartë, i cili është i krahasueshëm me kompleksitetin e algoritmeve më të shpejta.