2. Tõestada, et ei tarvitse kehtida sisaldavus R(SoT)c(RS)o(RT) 4. Kanooniline kuju 1. Mis on arvu kanooniline kuju? 2. Kuidas leida etteantud naturaalarvu tegureid, kui on teada arvu kanooniline kuju? 3. Määrata kanoonilise kuju abil, mitu tegurit on arvul 96000. 4. Milline iseloomulik omadus on arvude a ja b kanoonilistel kujudel, kui SÜT(a,b) = 1? 5. Olgu ja , kus < , algarvu p astmed vastavalt arvu a ja arvu b kanoonilises kujus. Leida algarvu p aste arvu a + b kanoonilises kujus.
104493 IAPB21 Kui J X 6 = 4, siis J = {10, 16, 22, 28 ... } Seega kui J X 6 = 0 õ 2 õ 4, peab arv n jaguma 2-ga ehk tegemist on paarisarvuga. Kuna algarvudest on ainuke paarisarv 2, siis jagades algarvu 6-ga ei ole võimalik saada jäägiks 0, 2 ega 4. Kui J X 6 = 3, siis J = {9, 15, 21, 27 ... } ning seega jagub n 3-ga. Kuna algarv võib jaguda ainult 1 ja iseendaga, siis kui J X 6 = 3, ei saa n olla algarv. Jääkide hulgast A jäävad järele veel 1 ja 5. Jääk 5 on võrdväärne jäägiga -1. Kui J X 6 = 1 või J X 6 = 5, siis rahuldavad arvud n kõiki algarvudele püstitatud tingimusi, kuna arvud 6J - 1 ja 6J + 1 ei saa olla paarisarvud
astendamise põhivalemit, mõnda neist tagurpidi , 19.Arvu 10 astmed - kasutatakse arvu Õ ül.59,69,115 kirjutamisel standardkujul = ja 20.Tähtavaldise väärtuse arvutamine - kirjutada Õ ül.108 tähtavaldis ja muutuja väärtus; moodustada kui x = 2 arvavaldis ja arvutada selle väärtus kui u= -1 -1:1=1 21.Astme kirjutamine algarvu astmena - Õ ül.89 kasutada astme astendamise ja korrutise astendamise valemeid 22.Võrrand astmetega - tundmatu teguri Õ ül.107,119 leidmiseks tuleb korrutis jagada antud teguriga; lahend on kasutada astmete jagamise eeskirja lahend on 23.Astmetega murru taandamine - leida arvud Õ ül.114,120 või astmed, millega saab taandada (vormistada võib ka mahatõmbamise abil nagu harilike taandasin -ga
e) a (b + c) = ab + ac a, b, c korrutamise distributiivsus 2) - hulk on kinnine liitmise ja korrutamise suhtes. 4. Algarvud. 1) Algarvuks nimetatakse 1-st suuremat naturaalarvu, mis jagub ainult iseenda ja 1-ga. 2) Eratosthenese sõel. a) Nimekiri arvudest 2..N. b) Nimekirjast tõmmatakse maha need arvud, mis on mingi algarvu kordsed. 5. Algarvud. 1) Eukleidese teoreem. a) Teoreem : algarvude hulk on lõpmatu. b) Tõestus : Tähistame p1=2, p2=3, p3=5, ... Oletame vastuväiteliselt, et leidub suurim algarv pn. Vaatleme naturaalarvu a=p1 p2 ... pn + 1. Et a on suurem 1-st, siis peab leiduma algarv millega a jagub. Kuna oletasime, et p1 ..
Teades avalikku suurust Ab ei tohi olla võimalik arvutada salajast suurust Ib. Selliseid funktsioone Ab nimetatakse tagauksega ühesuunalisteks funktsioonideks. RSA Krüptosüsteemi RSA leiutasid 1977(8) aastal R. Rivest, A. Shamir ja L. Adleman. Seda saab kasutada andmete krüpteerimiseks ja digitaalallkirjade moodustamiseks. RSA turvalisus põhineb arvu algteguriteks lahutamise keerukusel. RSA süsteemi ülesseadmiseks tuleb teha järgnevat: *valida kaks suurt (nt 512-bitist) erinevat algarvu p ja q. Arvutada n=p*q valida e , mis on väiksem N-ist nii, et SÜT (E, (p-1)(q-1))=1. Valida d, nii et d*e=1 mod (p-1)(q-1) avalikuks võtmeks saab Ab=(e,n) ja salajaseks võtmeks Ib = (d,p,q) RSA süsteemi võtmete saamiseks arvutame: valime kaks erinevat alg arvu p=5 ja q=11 arvutada n=p*q=55 valida e selliselt, et SÜT (e,(p-1)(q-1))=1 valime e=3, SÜT (3,4,10)=1 valida d nii, et d*e= 1 mod (p-1)(q-1) valime d=27, sest 27*3=1 mod 40 avalik võti on 3; 55 salajane võti: 27;5;11
Teades avalikku suurust Ab ei tohi olla võimalik arvutada salajast suurust Ib. Selliseid funktsioone Ab nimetatakse tagauksega ühesuunalisteks funktsioonideks. RSA Krüptosüsteemi RSA leiutasid 1977(8) aastal R. Rivest, A. Shamir ja L. Adleman. Seda saab kasutada andmete krüpteerimiseks ja digitaalallkirjade moodustamiseks. RSA turvalisus põhineb arvu algteguriteks lahutamise keerukusel. RSA süsteemi ülesseadmiseks tuleb teha järgnevat: *valida kaks suurt (nt 512-bitist) erinevat algarvu p ja q. Arvutada n=p*q valida e , mis on väiksem N-ist nii, et SÜT (E, (p-1)(q-1))=1. Valida d, nii et d*e=1 mod (p-1)(q-1) avalikuks võtmeks saab Ab=(e,n) ja salajaseks võtmeks Ib = (d,p,q) RSA süsteemi võtmete saamiseks arvutame: valime kaks erinevat alg arvu p=5 ja q=11 arvutada n=p*q=55 valida e selliselt, et SÜT (e,(p-1)(q-1))=1 valime e=3, SÜT (3,4,10)=1 valida d nii, et d*e= 1 mod (p-1)(q-1) valime d=27, sest 27*3=1 mod 40 avalik võti on 3; 55 salajane võti: 27;5;11
maksed ja laekumised ei toimu sünkroonselt. Osa laekumistest ja maksetest toimuvad ebakorrapäraselt, teised on pideva iseloomuga. Krediidimüügi korral võtab raha laekumine aega. Rahakontot juhtides lisaks optimaalse kassaseisu leidmisele pöörama tähelepanu nii varude kui ka debitoorse ja kreditoorse võlgnevuse juhtimisele. Rakenduslikumaks aspektiks rahakonto juhtimisel on rahaeelarve koostamine. Kui sissetulekud ei kata algarvu siis on vajalik saada välist lisafinantseeringut (nt arvelduskrediit, lühiajaline laen, pikaajaline laen, täiendav omakapital vms) 43. Debitoorse võlgnevuse juhtimise põhiprintsiibid Debitoorse võlgnevuse juhtimine algab krediidipoliitikast. Korraliku kontrollsüsteemi rakendamine võimaldab juba varakult teha parandusi ja vältida debitoorse võlgnevuse kontrolli alt väljumist. Krediidipoliitika rakendamiseks on neli erinevat võimalust (Brigham, Daves 2004): 1
avalik võti. Sellega krüpeeritud tekst läheb teele ja teine kasutaja dekrüpteerib
selle oma salajase võtmega. Kui me rakendame sõnumile avalikku võtit, siis veel
korra tulemusele salajast võtit, siis me saame lähteteksti tagasi ja ka vastupidi.
Üks tuntumaid ja veel ka kasutusel olevaid on RSA.
RSA seisneb selles, et me oskame korrutada, aga me ei oska suuri arve
teguriteks lahutada, sest see on keeruline. Kui on kahe algarvu korrutamisega
tegemist, siis on keerulisem teguriteks jagamine. Siiani ei ole keegi leiutanud
sellist algoritmi, kuidas seda teha. Meil on kaks suurt algarvu p ja q ning me
korrutame need omavahel läbi, siis saame n-i (n=p*q). See on üks võtme
komponent. Kui me oskame selle n-i uuesti p-ks ja q-ks tagasi teha, siis on pool
lahtimurdmist tehtud. Järgmisena tuleb arvutada välja z, mille saame nii: z = (p-
1)(q-1). Järgmisena valime e (e
toore jõuga seda lahti murda on peaaegu võimatu, samas kui salajase võtmega on see juba küllaltki lihtne. RSA algoritm on pööratav, st. võtmed on paarikaupa ja võivad olla mõlemad krüpteerivaks või vastavalt siis dekrüpteerivateks võtmeteks. Avaliku võtme krüptograafia töötab funktsioonide peal, mis on küllaltki lihtsalt arvutatavad kuid "raskesti" pööratavad. ==> RSA Rivest, Shamit, Adelson algoritm. 1) vali kaks suurt algarvu p ja q; 2) arvuta n=pq ja z=(p-1)(q-1); 3) Vali e < n, et puuduksid ühised faktorid e ja z vahel; 4) Vali d, et ed- 1 jagub täpselt z-ga; 5) Avalik võti on (n, e), privaatne võti (n, d); //// Kui tahad m-i krüpteerida, siis arvuta c=mE mod n //// ja et dekrüpteerida arvuta m=cD mod n 51. AUTENTIMINE ==> Autentimisega tehakse kindlaks, et sõnum tuleb tõepoolest sellest allikast, millest see väidetavalt on teele pandud ehk autentimise eesmärk on tuvastada, kes on osapooled. Selleks
murda on peaaegu võimatu, samas kui salajase võtmega on see juba küllaltki lihtne. RSA algoritm on pööratav, st. võtmed on paarikaupa ja võivad olla mõlemad krüpteerivaks või vastavalt siis dekrüpteerivateks võtmeteks. Avaliku võtme krüptograafia töötab funktsioonide peal, mis on küllaltki lihtsalt arvutatavad kuid "raskesti" pööratavad. ==> RSA – Rivest, Shamit, Adelson algoritm. 1) vali kaks suurt algarvu p ja q; 2) arvuta n=pq ja z=(p-1)(q-1); 3) Vali e < n, et puuduksid ühised faktorid e ja z vahel; 4) Vali d, et ed-1 jagub täpselt z-ga; 5) Avalik võti on (n, e), privaatne võti (n, d); //// Kui tahad m-i krüpteerida, siis arvuta c=mE mod n //// ja et dekrüpteerida arvuta m=cD mod n 51. AUTENTIMINE ==> Autentimisega tehakse kindlaks, et sõnum tuleb tõepoolest sellest allikast, millest see väidetavalt on teele pandud ehk autentimise eesmärk on tuvastada, kes on osapooled
Kui Jüri oli läbinud 9641 meetrit 3456 detsimeetrit ja 12340 millimeetrit, siis ta peatus ja katkestas jooksu. Mitu sentimeetrit jäi tal 10 kilomeetrist puudu? Vastus: 106 cm 128. raamat on 4 korda kallim kui pastakas, aga pastakas 30 krooni võrra odavam kui raamat. Kui palju maksab raamat ja kui palju pastakas? Vastus: raamat 40 krooni ja pastakas 10 krooni 129. Leia 5 esimese algarvu ja 5 esimese kordarvu summa. Vastus: 2 + 3 + 5 + 7 + 11 = 28 algarvude summa (1 pole algarv ja 2 ainuke paarisarvuline algarv) 4 + 6 + 8 + 9 + 10 = 37 kordarvude summa 130. Ostja arve on 37 krooni. Kuidas saab ta oma ostu eest tasuda ainult 2- kroonistega, kui müüjal pole münte, Vastus: 21 x 2 = 42 krooni ( annab 21 2- kroonist) 42 5 = 37 krooni ( müüja annab 5- kroonise tagasi) 131
sõnum on enne krüptimist ja pärast dekrüptimist identne: m = db(eb(m)). Kui rakendada alguses sõnumile PDK krüptimiseks ja dekrüptimiseks PEK, siis saadakse sama tulemus: eb(db(m)) = m. RSA algoritm (Rivest, Shamir, Adleman algoritm) - on saanud avaliku võtme krüptograafia sünonüümiks. Kaks omavahel seotud komponenti RSA-l: * avaliku ja privaatse võtme valik; * krüptimise ja dekrüptimise algoritmi valik. Võtmete valikuks peab saaja: 1) valima kaks suurt algarvu p ja q (mida suurem arv, seda raskem koodi murda). Soovituslikult võiksid p ja q olla 1024 biti(väga tähtsa info jaoks) või 768 biti(vähem tähtsa info jaoks). 2) arvutama n = pq ja z = (p-1)(q-1) 3) valima arvu e < n, millel pole ühtki ühist tegurit z-ga (v.a. 1). 4) Valima arvu d nii, et ed -1 jagub täpselt (jäägita) arvuga z. (ehk: e*d mod z = 1) 5) avalik võti on eb(n,e), privaatvõti on db(n,d). Saatjapoolne krüptimine ja saajapoolne dekrüptimine:
Kui rakendada alguses sõnumile PDK krüptimiseks ja dekrüptimiseks PEK, siis saadakse sama tulemus: eb(db(m)) = m. RSA algoritm (Rivest, Shamir, Adleman algoritm) - on saanud avaliku võtme krüptograafia sünonüümiks. Kaks omavahel seotud komponenti RSA-l: * avaliku ja privaatse võtme valik; * krüptimise ja dekrüptimise algoritmi valik. Võtmete valikuks peab saaja: 1) valima kaks suurt algarvu p ja q (mida suurem arv, seda raskem koodi murda). Soovituslikult võiksid p ja q olla 1024 biti(väga tähtsa info jaoks) või 768 biti(vähem tähtsa info jaoks). 2) arvutama n = pq ja z = (p-1)(q-1) 3) valima arvu e < n, millel pole ühtki ühist tegurit z-ga (v.a. 1). 4) Valima arvu d nii, et ed -1 jagub täpselt (jäägita) arvuga z. (ehk: e*d mod z = 1) 5) avalik võti on eb(n,e), privaatvõti on db(n,d). Saatjapoolne krüptimine ja saajapoolne dekrüptimine:
dekrüptimist identne: m = db(eb(m)). Kui rakendada alguses sõnumile PDK krüptimiseks ja dekrüptimiseks PEK, siis saadakse sama tulemus: eb(db(m)) = m. RSA algoritm (Rivest, Shamir, Adleman algoritm) - on saanud avaliku võtme krüptograafia sünonüümiks. Kaks omavahel seotud komponenti RSA-l: * avaliku ja privaatse võtme valik; * krüptimise ja dekrüptimise algoritmi valik. Võtmete valikuks peab saaja: 1) valima kaks suurt algarvu p ja q (mida suurem arv, seda raskem koodi murda). Soovituslikult: p * q = 1024 (väga tähtsa info jaoks) või 768 (vähem tähtsa info jaoks). 2) arvutama n = p*q ja z = (p-1)*(q-1) 3) valima arvu e < n, millel pole ühtki ühist tegurit z-ga (v.a. 1). 4) Valima arvu d nii, et e*d -1 jagub täpselt (jäägita) arvuga z. (ehk: e*d mod z = 1) 5) avalik võti on eb(n,e), privaatvõti on db(n,d). Saatjapoolne krüptimine ja saajapoolne dekrüptimine:
vaadata. Ja lisaks tundub mulle, et sellel programmil võib olla kursusest osavõtjatele praktiline rakendusala ;) Näide 3. Ü l e s a n n e: Leida kõik algarvud, mis on väiksemad kui 1000. Ma loodan, et Te teate, mis on algarv. Ja loodetavasti olete Te kuulnud, mis asi on Eratosthenese sõel? Ei ole? Niimoodi nimetatakse meetodit, mille abil võibki leida etteantud naturaalarvust väiksemad algarvud. Vaatame seda siis lähemalt. Algarvu definitsioonist selgub, et algarv on ühest suurem ning jagub parajasti arvuga 1 ja iseendaga. Kui me nüüd võtame meile antud arvude hulga { 2, ..., 999 } ( arvu 1 ei ole vajadust vaadelda) ja hakkame nende hulgast eemaldama arve, mis jaguvad 2-ga, 3-ga, 5-ga ja teiste juba leitud algarvudega, siis jäävadki alles ainult algarvud. Üksikasjad leiate alljärgnevast Basic- programmist. ' P r o g r a m m i a l g u s DIM arv(2 TO 999) AS INTEGER ' vaadeldav arvuhulk
Kui sisendfail on tühi, siis ei ole vajadust ühtegi sümbolit läbi vaadata. Näide 3. Ü l e s a n n e: Leida kõik algarvud, mis on väiksemad kui 1000. Ma loodan, et Te teate, mis on algarv. Ja loodetavasti olete Te kuulnud, mis asi on Eratosthenese sõel? Ei ole? Niimoodi nimetatakse meetodit, mille abil võibki leida etteantud naturaalarvust väiksemad algarvud. Vaatame seda siis lähemalt. 69 / 115 Algarvu definitsioonist selgub, et algarv on ühest suurem ning jagub parajasti arvuga 1 ja iseendaga. Kui me nüüd võtame meile antud arvude hulga { 2, ..., 999 } ( arvu 1 ei ole vajadust vaadelda) ja hakkame nende hulgast eemaldama arve, mis jaguvad 2-ga, 3-ga, 5-ga ja teiste juba leitud algarvudega, siis jäävadki alles ainult algarvud. Üksikasjad leiate alljärgnevast Basic- programmist. ' P r o g r a m m i a l g u s DIM arv(2 TO 999) AS INTEGER ' vaadeldav arvuhulk
kõik teised arvud võime esitada algarvude korrutisena. Näiteks võime algarvude korrutisena kirjutada ja Üritame lugejat selles teoreemis järgnevalt ka veenda. Meenutame, et arutlust, mis veenaks ka kõige skeptilisemat matemaatikut, nimetatakse tõestuseks ning sisuliselt annamegi siin tõestuse. Tõestus: Alustuseks märgime, et algarve kindlasti leidub – näiteks 2, 3 ja 5 on algarvud ja nii mõnigi veel. Oletame, et oleme leidnud juba erinevat algarvu . Kas leidub mõni veel? Kuidas teda leida? Uus algarv ei tohiks kindlasti jaguda ühegagi juba teadaolevatest arvudest. Kõige lihtsam oleks siis vaadata arvu , mis on ühe võrra suurem kui kõikide seni leitud algarvude korrutis: Nii ei saa see arv kindlasti jaguda ühegagi juba leitud algarvudest, sest nendega jagamisel jätab ta jäägi 1. Kui see arv ei jagu enam ühegi teise arvuga peale ühe ja iseenda, ongi tegemist
annaabi.ee 
