2b:null 2c:["$","title",null,{"children":"Kibővített euklideszi algoritmus (Extended Euclidean Algorithm) | Attila Bagossy | Observable"}] 31:T479,{ console.log(tex`r_{i}.outerHTML`) function rowToHtmlString(row) { console.log(row) const isLastRow = row.k == (table.length - 1) return ` ${isLastRow ? `${tex`\color{blue}\mathbf{${row.k}}`.outerHTML}` : `${tex`${row.k}`.outerHTML}` } ${isLastRow ? `${tex`\color{red}\mathbf{${row.r}}`.outerHTML}` : `${tex`${row.r}`.outerHTML}` } ${tex`${row.q || ''}`.outerHTML} ${tex`${row.x}`.outerHTML} ${tex`${row.y}`.outerHTML} ` }; const lastRow = ` ${tex`${table.length}`.outerHTML} ${tex`0`.outerHTML} `; return html` ${[...table.map(rowToHtmlString), lastRow].join('')}

${tex`i`}	${tex`r_{i}`}	${tex`q_{i}`}	${tex`x_{i}`}	${tex`y_{i}`}

` }32:[] 2f:{"id":"0a43b8478b80852e","slug":"kibovitett-euklideszi-algoritmus","title":"Kibővített euklideszi algoritmus (Extended Euclidean Algorithm)","thumbnail":"6bc4bc563c14c067109a83c2be6014ecd38d6d28512e3b99c2a30a12c42c6531","access_level":"public","create_time":"$D2019-11-29T15:59:01.650Z","update_time":"$D2021-03-07T19:58:04.440Z","view_time":null,"first_public_time":"$D2019-11-29T18:48:44.397Z","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":397,"publish_version":397,"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":"Kibővített euklideszi algoritmus (Extended Euclidean Algorithm)","cells":[{"id":0,"value":"md`# Kibővített euklideszi algoritmus (Extended Euclidean Algorithm)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":388,"value":"md`([English translation by Ádám Vécsi](https://observablehq.com/@beardofdoom/extended-euclidean-algorithm?fbclid=IwAR1JP9Yd7vdXg5JOyrwDpSbzpqswmsv4RUHLqYuuuD4E1gwX-3wuPpwmvZk))`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":30,"value":"md`## Előzetes ismeretek`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"md`### Maradékos osztás`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"md`\nHa ${tex`a, b \\in \\mathbb{Z}`} és ${tex`b \\neq 0`}, akkor egyértelműen léteznek olyan ${tex`q, r \\in \\mathbb{Z}`} számok, hogy\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"tex.block`\n a = b \\cdot q + r,\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"md`\nahol ${tex`0 \\leq r < |\\,b\\,|`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"md`### Oszthatóság`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"md`\nAz ${tex`a`} egész számot ${tex`b`} egész szám osztójának nevezzük, ha létezik olyan ${tex`q`} egész szám, hogy\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":74,"value":"tex.block`\nb = a \\cdot q.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":78,"value":"md`\nEzt ${tex`a\\,|\\,b`} módon jelöljük.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":83,"value":"md`### Legnagyobb közös osztó`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":84,"value":"md`\nLegyenek ${tex`a`} és ${tex`b`} egész számok. Ekkor az ${tex`a`} és ${tex`b`} legnagyobb közös osztója ${tex`d`}, ha\n\n * ${tex`d \\,|\\, a`},\n * ${tex`d \\,|\\, b`} és\n * ${tex`\\forall c \\in \\mathbb{Z}`} esetén, ha ${tex`c \\,|\\, a`} és ${tex`c \\,|\\, b`} teljesül, akkor ${tex`c \\,|\\, d`}.\n\nA legnagyobb közös osztót ${tex`(a, b)`} módon jelöljük.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"md`## Euklideszi algoritmus (Euclidean Algorithm)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":96,"value":"md`\nAdott ${tex`a`} és ${tex`b`} esetén ${tex`(a, b)`} (azaz a legnagyobb közös osztó) meghatározására alkalmas algoritmus.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":106,"value":"euklideszi_algoritmus = $styling.emitters.twoColumnContainer(\nmd`\n### Algoritmus\n#### Euklideszi algoritmus\n`,\nmd`\n 1. Legyenek ${tex`a`} és ${tex`b`} adott egészek.\n 1. Legyen ${tex`r_{0} = a`} és ${tex`r_{1} = b`}.\n 1. Amíg ${tex`r_{i} \\neq 0`}, addig végezzünk maradékos osztásokat:\n ${tex.block`r_{i - 2} = q_{i - 1} \\cdot r_{i - 1} + r_{i}`}\n 1. Ha ${tex`r_{n + 1} = 0`}, akkor ${tex`(a, b) = r_{n}`} (azaz az utolsó nullától különböző maradék lesz a legnagyobb közös osztó).\n`\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":118,"value":"md`## Kibővített euklideszi algoritmus (Extended Euclidean Algorithm)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":132,"value":"md`\nAz algoritmus segítségével adott ${tex`a`} és ${tex`b`} egészekre nemcsak ${tex`(a, b)`} értékét határozhatjuk meg, hanem a következő lemmában megjelenő ${tex`x`} és ${tex`y`} értékeket is.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"md`### Bézout-lemma`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":136,"value":"md`\nAz ${tex`a`} és ${tex`b`} egész számok legnagyobb közös osztója alkalmas ${tex`x, y \\in \\mathbb{Z}`} számokkal kifejezhető\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":139,"value":"tex.block`\n(a, b) = ax + by\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":140,"value":"md`\nalakban.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":151,"value":"kibovitettEuklideszi_algoritmus = $styling.emitters.twoColumnContainer(\nmd`\n### Algoritmus\n#### Kibővített euklideszi algoritmus\n`,\nmd`\n 1. Legyenek ${tex`a`} és ${tex`b`} adott egészek.\n 1. Legyen\n * ${tex`r_{0} = a`} és ${tex`r_{1} = b`},\n * ${tex`x_{0} = 1`} és ${tex`x_{1} = 0`},\n * ${tex`y_{0} = 0`} és ${tex`y_{1} = 1`}.\n 1. Amíg ${tex`r_{i} \\neq 0`}, addig számoljuk ki a következő összefüggések segítségével az ${tex`r_{i}, x_{i}, y_{i}`} értékeket:\n ${tex.block`\n \\begin{aligned}\n r_{i - 2} &= q_{i - 1} \\cdot r_{i - 1} + r_{i}, \\\\\n x_{i} &= x_{i - 1}q_{i - 1} + x_{i - 2}, \\\\\n y_{i} &= y_{i - 1}q_{i - 1} + y_{i - 2}\n \\end{aligned}\n `}\n 1. Ha ${tex`r_{n + 1} = 0`}, akkor\n ${tex.block`\n \\begin{aligned}\n (a, b) &= r_{n}, \\\\\n x &= (-1)^{n} \\cdot x_{n}, \\\\\n y &= (-1)^{n + 1} \\cdot y_{n}\n \\end{aligned}\n `}\n`\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"md`## Gyakorlás`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":175,"value":"md`\nA következőkben táblázatos módszerrel fogjuk végigszámolni az előző algoritmus lépéseit.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":189,"value":"mutable inputA = number({\n title: md`${tex`a`} értéke`,\n value: 402\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":195,"value":"mutable inputB = number({\n title: md`${tex`b`} értéke`,\n value: 123\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":201,"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":244,"value":"md`### 1. Az ${tex`r_{i}, x_{i}, y_{i}`} értékek meghatározása`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":206,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":303,"value":"md`\nA ${tex`\\color{blue}kékkel`} kiemelt érték lesz ${tex`n`}, míg a ${tex`\\color{red}pirossal`} kiemelt érték az utolsó nem nulla maradék:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":315,"value":"tex.block`\n\\begin{aligned}\n \\color{blue}\n n &= ${table.length - 1} \\\\\n \\color{red}\n r_{${table.length - 1}} &= ${result.gcd}\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"md`### 2. Az ${tex`(a, b), x, y`} értékek meghatározása`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":308,"value":"tex.block`\n\\begin{aligned}\n (a, b) &= r_{${table.length - 1}} = ${result.gcd} \\\\\n x &= (-1)^{${table.length - 1}}\\cdot${table[table.length - 1].x} = ${result.x} \\\\\n y &= (-1)^{${table.length}}\\cdot${table[table.length - 1].y} = ${result.y}\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":333,"value":"md`\nAzaz\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":336,"value":"{\n const wrap = n => n < 0 ? `(${n})` : `${n}`\n \n return tex.block`\n ${result.gcd} = ${wrap(inputData.a)} \\cdot ${wrap(result.x)} + ${wrap(inputData.b)} \\cdot ${wrap(result.y)}\n `\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"md`## Függelék`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"isEven = a => a % 2 == 0;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"isOdd = a => !isEven(a);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"printableExtendedEuclideanAlgorithm = function* printableExtendedEuclideanAlgorithm(a, b) {\n if (!Number.isInteger(a) || !Number.isInteger(b)) {\n throw new Error('a and b must be integers!');\n }\n\n let k = 0\n let x = 0, prevx = 1;\n let y = 1, prevy = 0;\n let r = b, prevr = a;\n let q = null;\n\n yield {\n k,\n x: prevx,\n y: prevy,\n r: prevr,\n q\n };\n\n while (r != 0) {\n k += 1;\n\n q = Math.floor(prevr / r);\n\n [prevr, r] = [r, prevr % r];\n [prevx, x] = [x, x * q + prevx];\n [prevy, y] = [y, y * q + prevy];\n\n yield {\n k,\n x: prevx,\n y: prevy,\n r: prevr,\n q\n }; \n }\n};\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"calculateCorrectBezoutCoefficients = function calculateCorrectBezoutCoefficients(lastPrintableOutput) {\n const n = lastPrintableOutput.k;\n const nIsEven = isEven(n)\n \n return {\n gcd: lastPrintableOutput.r,\n x: nIsEven ? lastPrintableOutput.x : -lastPrintableOutput.x,\n y: !nIsEven ? lastPrintableOutput.y : -lastPrintableOutput.y\n };\n};","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"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":104,"value":"$$styling.css.twoColumnContainer","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":178,"value":"import {button, number} from \"@jashkenas/inputs\"\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":222,"value":"{\n initiateCalculation;\n mutable inputData = {\n a: Number.parseInt((mutable inputA)[0].value),\n b: Number.parseInt((mutable inputB)[0].value)\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":219,"value":"mutable inputData = ({\n a: 123,\n b: 402\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"table = [...printableExtendedEuclideanAlgorithm(inputData.a, inputData.b)]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":255,"value":"result = calculateCorrectBezoutCoefficients(table[table.length - 1])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":358,"value":"assertion = result.gcd == inputData.a * result.x + inputData.b * result.y","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":384,"value":"extendedEuclideanAlgorithm = (a, b) => calculateCorrectBezoutCoefficients([...printableExtendedEuclideanAlgorithm(a, b)].pop())","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 30:"$2f:body"