// Numbas version: exam_results_page_options
{"name": "Blakley", "extensions": ["numbertheory", "polynomials"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Blakley", "tags": [], "metadata": {"description": "<p>The students should solve a Blakley secret sharing scheme and find the secret.</p>", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "<p>We want to set up a $(\\var{k},\\var{n})$ Blakley scheme, that is, we want to share a secret between $n=\\var{n}$ people so that any $k=\\var{k}$ of them can find the secret, but no $\\var{k-1}$ alone can (clearly we need $n\\geq k$). We work modulo the prime $p=\\var{p}$ and the secret is $x_0$.</p>\n<p>Our first step is to generate a $\\var{k}$-dimensional point $Q = (x_0,\\var{xstring})$: the first coordinate of this point is the secret $x_0$, and the other coordinates $(\\var{xstring})$ are picked randomly $\\pmod{\\var{p}}$.</p>\n<p>Each of the $\\var{n}$ persons is given the equation of a plane in $\\mathbb R^3$ &nbsp;passing through the point $Q= (x_0,\\var{xstring})$: for each plane we generate random coefficients $a_i,b_i\\pmod{\\var{p}}$ and then set $c_i=z_0-a_ix_0-b_iy_0\\pmod{\\var{p}}$. The equation of the plane is $z=a_ix+b_iy+c_i\\pmod{\\var{p}}$. The key for Person $i$ is therefore the pair &nbsp;$((a_i,b_i),c_i)$.</p>\n<p>After generating the keys, Alice, Bob and Charles get the keys $\\var{keystrings}$.</p>", "advice": "<h2>System</h2>\n<p>The equations are given as $a_ix+b_iy-z=-c_i$. So for each of the keys, the corresponding row in the matrix will be $[a_i, b_i, -1]$ and the corresponding coefficient for $b$ will be $-c_i\\pmod{\\var{p}}$.</p>\n<ul>\n<li>Since Alice's key is $(a_1,b_1)=\\var{values[0][0][0..k-1]}$ and $c_i=\\var{values[0][1]}$, the first row of the matrix have coefficients $\\var{transpose(values[0][0])}$, and the right hand side has coefficient $\\var{p-values[0][1]}$.</li>\n<li>Since Bob's key is $(a_1,b_1)=\\var{values[1][0][0..k-1]}$ and $c_i=\\var{values[1][1]}$, the first row of the matrix have coefficients $\\var{transpose(values[1][0])}$, and the right hand side has coefficient $\\var{p-values[1][1]}$.</li>\n<li>Since Charles key is $(a_1,b_1)=\\var{values[2][0][0..k-1]}$ and $c_i=\\var{values[2][1]}$, the first row of the matrix have coefficients $\\var{transpose(values[2][0])}$, and the right hand side has coefficient $\\var{p-values[2][1]}$.</li>\n</ul>\n<h2>Inverting the system</h2>\n<p>The matrix $\\var{M}$ has determinant $\\var{detm}\\pmod{\\var{p}}$ and adjoint $\\var{adjm}$. So, its inverse is $\\var{detm}^{-1}\\var{adjm}\\pmod{\\var{p}} = \\var{invm}$.</p>\n<h2>Solving the system</h2>\n<p>To solve the system it remains to multiply $M^{-1}$ by the right hand side: \\[\\var{invm}\\var{b} = \\var{q}\\].</p>\n<h2>The original message</h2>\n<p>The original message is simply the first coordinate of this point: $\\var{s}$.</p>", "rulesets": {}, "extensions": ["numbertheory", "polynomials"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"p": {"name": "p", "group": "parameters", "definition": "random(primelist(100,200))", "description": "<p>We are working in $\\mathbb{Z}_p$.</p>", "templateType": "anything", "can_override": false}, "k": {"name": "k", "group": "parameters", "definition": "3", "description": "<p>How many people are needed to retrieve the secret.</p>", "templateType": "anything", "can_override": false}, "n": {"name": "n", "group": "parameters", "definition": "random(10,20)", "description": "<p>Number of people among which the secret is divided.</p>", "templateType": "anything", "can_override": false}, "rhs": {"name": "rhs", "group": "Ungrouped variables", "definition": "map(mod(sum(map(a*b,[a,b],zip(pl,q))),p),pl,planes)", "description": "<p>The Right hand side of the equation is $-c$, where $c=z_0 - ax_0 - by_0$. This is to ensure that the plane contains the point $Q$.</p>", "templateType": "anything", "can_override": false}, "s": {"name": "s", "group": "Ungrouped variables", "definition": "random(1..p-1)", "description": "<p>secret to share.</p>", "templateType": "anything", "can_override": false}, "Q": {"name": "Q", "group": "Ungrouped variables", "definition": "[s] + repeat(random(0..p-1),k-1)", "description": "<p>We pick a point randomly such that the first coordinate is the secret and the other coordinates are random values.</p>", "templateType": "anything", "can_override": false}, "planes": {"name": "planes", "group": "Ungrouped variables", "definition": "repeat(vector(repeat(random(1..p-1),k-1) + [-1]),n)", "description": "<p>The coefficients for the plane, (a,b,-1) will be such that $ax_0+by_0-z_0 = c$.</p>", "templateType": "anything", "can_override": false}, "x": {"name": "x", "group": "parameters", "definition": "mod_polynomial(x,[0,1],p)", "description": "", "templateType": "anything", "can_override": false}, "values": {"name": "values", "group": "Ungrouped variables", "definition": "take(k,x,x,shuffle(zip(planes,rhs)))", "description": "<p>Three random keys (ie, three planes containing Q).</p>", "templateType": "anything", "can_override": false}, "keystrings": {"name": "keystrings", "group": "Ungrouped variables", "definition": "latex(join(map(\"k_{\"+i+\"}=[(\"+x[0][0..k-1]+\"),\"+(mod(-x[1],p))+\"]\",[i,x],enumerate(values)),\", \"))", "description": "", "templateType": "anything", "can_override": false}, "M": {"name": "M", "group": "Solution", "definition": "matrix(map(v[0],v,values))", "description": "", "templateType": "anything", "can_override": false}, "detm": {"name": "detm", "group": "Solution", "definition": "mod(det(M),p)", "description": "", "templateType": "anything", "can_override": false}, "invdetm": {"name": "invdetm", "group": "Solution", "definition": "invert(detm,p)", "description": "", "templateType": "anything", "can_override": false}, "adjm": {"name": "adjm", "group": "Solution", "definition": "matrix(map(map(cofactor(M,i,j),i,0..2),j,0..2))", "description": "", "templateType": "anything", "can_override": false}, "invm": {"name": "invm", "group": "Solution", "definition": "map(mod(x,p),x,invdetm*adjM)", "description": "", "templateType": "anything", "can_override": false}, "B": {"name": "B", "group": "Solution", "definition": "vector(map(v[1],v,values))", "description": "", "templateType": "anything", "can_override": false}, "sol": {"name": "sol", "group": "Solution", "definition": "map(mod(x,p),x,invm*B)", "description": "", "templateType": "anything", "can_override": false}, "eqn": {"name": "eqn", "group": "Text", "definition": "latex(join(map(\"a_\\{i,{j}\\}x_{j}\",j,0..k-2),\"+\"))", "description": "", "templateType": "anything", "can_override": false}, "a": {"name": "a", "group": "Text", "definition": "latex(join(map(\"a_\\{i,{j}\\}\",j,0..k-2),\",\"))", "description": "", "templateType": "anything", "can_override": false}, "xstring": {"name": "xstring", "group": "Text", "definition": "latex(\"y_0,z_0\")", "description": "<p>Julien wrote latex(join(map(\"x_\\{{j}\\}\",j,1..k-1),\",\"))</p>", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["s", "Q", "planes", "rhs", "values", "keystrings"], "variable_groups": [{"name": "parameters", "variables": ["k", "n", "p", "x"]}, {"name": "Solution", "variables": ["M", "B", "detm", "invdetm", "adjm", "invm", "sol"]}, {"name": "Text", "variables": ["eqn", "a", "xstring"]}], "functions": {"cofactor": {"parameters": [["M", "matrix"], ["i", "number"], ["j", "number"]], "type": "number", "language": "jme", "definition": "det(matrix(map(map(M[mod(i+l,3)][mod(j+r,3)],r,[1,2]),l,[1,2])))"}}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "gapfill", "useCustomName": true, "customName": "System", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Write the linear system $M\\textbf x=\\textbf{b}$ that Alice, Bob and Charles will need to solve. A row of the matrix $M$ has the form $a_i,b_i,-1$ per plane and the constant vector $\\textbf{b}$ has an entry per plane:</p>\n<p>$M&equiv;$[[0]]$\\textbf{b}&equiv;$[[1]]$\\pmod{\\var{p}}$</p>", "gaps": [{"type": "matrix", "useCustomName": true, "customName": "M", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "correctAnswer": "M", "correctAnswerFractions": false, "numRows": "3", "numColumns": "3", "allowResize": true, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0, "prefilledCells": ""}, {"type": "matrix", "useCustomName": true, "customName": "b", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "correctAnswer": "b", "correctAnswerFractions": false, "numRows": 1, "numColumns": 1, "allowResize": true, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": "1", "minRows": 1, "maxRows": 0, "prefilledCells": ""}], "sortAnswers": false}, {"type": "gapfill", "useCustomName": true, "customName": "Solving the system", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>The inverse $M^{-1}$ of the matrix $\\pmod{\\var{p}}$ is: [[0]].</p>\n<p>Therefore the solution $(x_0,y_0,z_0)$ of the system &nbsp;is [[1]].</p>", "gaps": [{"type": "matrix", "useCustomName": true, "customName": "inverse of M", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "correctAnswer": "invm", "correctAnswerFractions": false, "numRows": 1, "numColumns": 1, "allowResize": true, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0, "prefilledCells": ""}, {"type": "matrix", "useCustomName": true, "customName": "coefficients", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "correctAnswer": "sol", "correctAnswerFractions": false, "numRows": 1, "numColumns": 1, "allowResize": true, "tolerance": 0, "markPerCell": false, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0, "prefilledCells": ""}], "sortAnswers": false}, {"type": "numberentry", "useCustomName": true, "customName": "Original Message", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>What is the original message?</p>", "minValue": "s", "maxValue": "s", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "contributors": [{"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}, {"name": "Guillermo Pineda", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/20075/"}]}]}], "contributors": [{"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}, {"name": "Guillermo Pineda", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/20075/"}]}