2b:null 2c:["$","title",null,{"children":"Gyorshatványozás (Fast Modular Exponentiation) | Attila Bagossy | Observable"}] 31:[] 2f:{"id":"b2af6b1e669fa41a","slug":"gyorshatvanyozas-fast-modular-exponentiation","title":"Gyorshatványozás (Fast Modular Exponentiation)","thumbnail":"23e483b5b0accc77c59010cbd8fba259c0d7e0aedbbee0dbc165a419e9fcc556","access_level":"public","create_time":"$D2019-11-29T18:51:19.614Z","update_time":"$D2021-03-07T19:57:46.765Z","view_time":null,"first_public_time":"$D2019-11-29T21:17:48.260Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"ef739838e5a1d607","login":"battila7","name":"Attila Bagossy","avatar_url":"https://avatars-next.observableusercontent.com/90b1460199ec3e040db6a772368bce18487f1a014e7f564bfbc73d51132a4e07","tier":"starter_2024"},"version":333,"publish_version":333,"role":null,"authored":false,"authors":[{"type":"individual","id":"6afecd2e2d5dcc78","login":"battila7","name":"Attila Bagossy","avatar_url":"https://avatars-next.observableusercontent.com/90b1460199ec3e040db6a772368bce18487f1a014e7f564bfbc73d51132a4e07","tier":null}],"members":[{"type":"individual","id":"6afecd2e2d5dcc78","login":"battila7","name":"Attila Bagossy","avatar_url":"https://avatars-next.observableusercontent.com/90b1460199ec3e040db6a772368bce18487f1a014e7f564bfbc73d51132a4e07","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":{"id":"f61262f1bb38bd9f","slug":"az-informatikai-biztonsag-alapjai","title":"Az informatikai biztonság alapjai","owner":{"id":"ef739838e5a1d607","login":"battila7","name":"Attila Bagossy"}},"type":"notebook","body":{"title":"Gyorshatványozás (Fast Modular Exponentiation)","cells":[{"id":0,"value":"md`# Gyorshatványozás (Fast Modular Exponentiation)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":329,"value":"md`([English translation by Ádám Vécsi](https://observablehq.com/@beardofdoom/fast-modular-exponentiation))`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"md`## Előzetes ismeretek`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"md`### Hatvány- és modulo azonosságok`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":87,"value":"md`Szorzat modulo`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":74,"value":"tex.block`a \\cdot b \\; \\mathrm{mod} \\; m = (a \\;\\mathrm{mod}\\; m)(b \\;\\mathrm{mod}\\; m) \\; \\mathrm{mod}\\; m`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"md`----`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"md`\nIsmételt négyzetre emelés\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":85,"value":"tex.block`\n a^{2^{b + 1}} = a^{2^{b} \\cdot 2} = (a^{2^{b}})^{2}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":120,"value":"md`----`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"md`Ismételt négyzetre emelés modulo`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":102,"value":"tex.block`\n\\begin{aligned}\n a^{2} \\;\\mathrm{mod}\\; m &= (a \\;\\mathrm{mod}\\; m)(a \\;\\mathrm{mod}\\; m)\\;\\mathrm{mod}\\; m \\\\\n a^{4} \\;\\mathrm{mod}\\; m &= (a^{2} \\;\\mathrm{mod}\\; m)(a^{2} \\;\\mathrm{mod}\\; m)\\;\\mathrm{mod}\\; m \\\\\n a^{8} \\;\\mathrm{mod}\\; m &= (a^{4} \\;\\mathrm{mod}\\; m)(a^{4} \\;\\mathrm{mod}\\; m)\\;\\mathrm{mod}\\; m \\\\\n &\\vdots\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"md`## Feladat`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"md`\nLegyen ${tex`a`} egész, ${tex`b`} ${tex`1`}-nél nagyobb egész és ${tex`m`} pozitív egész. Szeretnénk kiszámolni az\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"tex.block`\na^{b} \\; \\mathrm{mod} \\; m\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"md`\nértéket oly módon, hogy minél kevesebb memóriára és elvégzett műveletre legyen szükség.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"gyorshatvanyozas_algoritmus = $styling.emitters.twoColumnContainer(\nmd`\n### Algoritmus\n#### Gyorshatványozás\n`,\nmd`\n 1. Legyen ${tex`a`} egész, ${tex`b`} ${tex`1`}-nél nagyobb egész és ${tex`m`} pozitív egész.\n 1. Írjuk fel a kitevőt (${tex`b`}) ${tex`2`} hatványainak összegeként:\n ${tex.block`\n b = 2^{b_{1}} + 2^{b_{2}} + \\cdots + 2^{b_{r}}\n `}\n 1. Ismételt négyzetre emeléssel számoljuk ki a következő értékeket:\n ${tex.block`\n \\begin{aligned}\n a^{2^{0}} \\\\\n a^{2^{1}} \\\\\n \\vdots\\;\\;\\; \\\\\n a^{2^{b_{r}}} \\\\\n \\end{aligned}\n `}\n 1. Határozzuk meg ezekből az eredetileg keresett értéket:\n ${tex.block`\n a^{b} = a^{2^{b_{1}}} \\cdot a^{2^{b_{2}}} \\cdot \\ldots \\cdot a^{2^{b_{r}}} \\;\\mathrm{mod}\\; m\n `}\n`\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":146,"value":"md`## Gyakorlás`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":148,"value":"md`A következőkben lépésről lépésre végighaladunk az algoritmus által elvégzett számításokon.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":152,"value":"mutable inputA = number({\n title: md`${tex`a`} értéke`,\n value: 6\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"mutable inputB = number({\n title: md`${tex`b`} értéke`,\n value: 73\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":159,"value":"mutable inputM = number({\n title: md`${tex`m`} értéke`,\n value: 100\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":162,"value":"viewof initiateCalculation = button({\n value: \"Számolás!\"\n});","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":165,"value":"md`### 0. Feladat`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":169,"value":"tex.block`\n${inputData.a}^{${inputData.b}} \\; \\mathrm{mod} \\; ${inputData.m}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":178,"value":"md`### 1. A kitevő felírása ${tex`2`} hatványainak összegeként`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":182,"value":"md`Sorozatosan osztjuk a kitevőt ${tex`2`}-vel, feljegyezve a maradékként kapott értékeket:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":201,"value":"{\n function rowToHtmlString(row, i) {\n return `\n \n ${tex`${i}`.outerHTML}\n ${tex`${row.q}`.outerHTML}\n ${tex`${row.r}`.outerHTML}\n \n `;\n };\n \n return html`\n \n \n \n \n \n \n \n \n \n \n \n \n ${binaryForm.map(rowToHtmlString).join('')}\n \n

${tex`i`}	${tex`q`}	${tex`r`}
	${tex`${inputData.b}`}

\n `\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":219,"value":"md`A kitevőt tehát felírhatjuk a következő alakban:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":222,"value":"tex.block`\n${inputData.b} = ${oneBits.map(obj => `2^{${obj.i}}`).join('+')}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":229,"value":"md`### 2. Ismételt négyzetre emelések`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":233,"value":"md`\nA kitevő előző felbontásában ${tex`${highestBit}`} volt a legmagasabb hatványkitevő, ezért ${tex`${highestBit + 1}`} lépést kell elvégeznünk:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":258,"value":"{\n function rowToTexString(row) {\n const isSignificant = binaryForm[row.i].r == 1\n \n return `\n ${inputData.a}^{2^{${row.i}}} &\\\\equiv \n ${isSignificant \n ? `\\\\mathbf{${row.r}}`\n : row.r\n } \n \\\\;\\\\mathrm{mod}\\\\; ${inputData.m} \\\\\\\\\n `\n };\n \n return tex.block`\n \\begin{aligned}\n ${repeatedSquares.map(rowToTexString).join('')}\n \\end{aligned}\n `;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":267,"value":"md`\nMinden lépésben vesszük az előző maradékot, négyzetre emeljük, majd képezzük az ${tex`m`}-mel (jelen esetben ${tex`${inputData.m}`}) vett osztási maradékát. Kivétel a ${tex`0.`} lépés, ekkor ugyanis egyszerűen ${tex`a`}-nak (most ${tex`${inputData.a}`}) vesszük az osztási maradékát.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":275,"value":"md`### 3. Az eredmény felírása`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":278,"value":"md`A hatványérték kiszámításához egyszerűen vesszük azokat a maradékokat, melyeket olyan kitevőjű hatványokból számoltunk, melyek szerepeltek ${tex`b`} első lépésbeli felbontásában. Ezen értékek az előző lépésben **vastag** betűvel szedve jelentek meg.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":289,"value":"md`\nTehát\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":292,"value":"tex.block`\n${inputData.a}^{${inputData.b}} = \n ${significantSquares.map(obj => `${obj.r}`).join('\\\\cdot')}\n \\equiv\n ${result}\n \\;\\mathrm{mod}\\;${inputData.m},\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":313,"value":"md`ami azt jelenti, hogy az eredmény ${tex`${result}`}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"md`## Függelék`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"import {\n $drawing,\n $curves,\n $figure,\n $maths,\n $styling,\n $plot,\n $utility\n} from '@battila7/kompgraf-stdlib'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"$$styling.css.twoColumnContainer","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"import {button, number} from \"@jashkenas/inputs\"\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"{\n initiateCalculation;\n mutable inputData = {\n a: Number.parseInt((mutable inputA)[0].value),\n b: Number.parseInt((mutable inputB)[0].value),\n m: Number.parseInt((mutable inputM)[0].value)\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"mutable inputData = ({\n a: 6,\n b: 73,\n m: 100\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":189,"value":"[...printableBinary(32)].forEach(x => console.log(x))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":187,"value":"printableBinary = function* printableBinary(n) {\n if (!Number.isInteger(n)) {\n throw new Error('n must be an integer!');\n }\n \n let q = n;\n while (q > 0) {\n const r = q % 2\n q = Math.floor(q / 2);\n \n yield {\n q,\n r\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":199,"value":"filterOneBits = binaryForm => binaryForm\n .map((obj, i) => Object.assign({ i }, obj))\n .filter(obj => obj.r == 1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"binaryForm = [...printableBinary(inputData.b)]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":212,"value":"oneBits = filterOneBits(binaryForm)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":234,"value":"highestBit = oneBits[oneBits.length - 1].i","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":241,"value":"printableRepeatedSquaring = function* printableRepeatedSquaring(a, highestBit, m) {\n let n = a\n \n for (let i = 0; i <= highestBit; ++i) {\n n = n % m\n \n yield {\n i,\n r: n\n }\n \n n = n * n\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":246,"value":"repeatedSquares = [...printableRepeatedSquaring(inputData.a, highestBit, inputData.m)]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":251,"value":"significantSquares = oneBits\n .map(obj => obj.i)\n .map(i => repeatedSquares[i])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":298,"value":"result = significantSquares.reduce((acc, curr) => (acc * curr.r) % inputData.m, 1) % inputData.m","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W31","stdlib":"1","titling":"auto"}} 30:"$2f:body"