// Numbas version: exam_results_page_options
{"name": "Discrete Logarithm with Pollard's rho", "extensions": ["numbertheory"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Discrete Logarithm with Pollard's rho", "tags": [], "metadata": {"description": "<p>This question asks students to solve a discrete logarithm problem with Pollard's rho algorithm as exposed in the book \"introduction to cryptography with open source software\" by McAndrew.</p>", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "<p>Apply Pollard's rho method, starting from $\\var{x0}$, to find a solution to the discrete logarithm $\\var{a}^x\\equiv \\var{y} \\pmod{\\var{n}}$.</p>", "advice": "<p>We need to find $\\var{a}^x\\equiv \\var{y}\\pmod{\\var{n}}$, then we would run the algorithm and find that the iterates are:</p>\n<p>$X=\\var{{map(x[0],x,iterates)}}$ and $Y=\\var{{map(x[1],x,iterates)}}$.</p>\n<p>At the last iterates, the first coordinate in the triplets {iterates[-1][0]} and {iterates[-1][1]} are equal. Therefore we stop. Letting $v \\equiv \\var{iterates[-1][1][2]}-\\var{iterates[-1][0][2]}\\equiv\\var{v} \\pmod{\\var{n-1}}$ and $u \\equiv \\var{iterates[-1][0][1]}-\\var{iterates[-1][1][1]}\\equiv \\var{u} \\pmod{\\var{n-1}}$, we find that $\\var{a}^{\\var{u}} \\equiv \\var{y}^{\\var{v}}\\pmod{\\var{n}} = \\var{a}^{x\\cdot \\var{v}}\\pmod{\\var{n}}$.</p>\n<p>To solve for $x$, we can solve the equation $\\var{v}x=\\var{u}\\pmod{\\var{n-1}}$, by Fermat's little theorem. Solving this equation gives us $x=\\var{w}$.</p>", "rulesets": {}, "extensions": ["numbertheory"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"factors": {"name": "factors", "group": "Ungrouped variables", "definition": "repeat(random(primelist(10,50)),nf)", "description": "", "templateType": "anything", "can_override": false}, "n": {"name": "n", "group": "Ungrouped variables", "definition": "random(primelist(50,120))", "description": "", "templateType": "anything", "can_override": false}, "x0": {"name": "x0", "group": "Ungrouped variables", "definition": "[1,0,0]", "description": "<p>Starting point for the iteration.</p>", "templateType": "anything", "can_override": false}, "iterates": {"name": "iterates", "group": "Ungrouped variables", "definition": "iterate_until([psi(x,y,a,n),psi(psi(z,y,a,n),y,a,n)],[x,z],[x1,y1],x[0]=z[0],n)", "description": "<p>iterates of the method.</p>", "templateType": "anything", "can_override": false}, "x1": {"name": "x1", "group": "Ungrouped variables", "definition": "psi(x0,y,a,n)", "description": "", "templateType": "anything", "can_override": false}, "y1": {"name": "y1", "group": "Ungrouped variables", "definition": "psi(x1,y,a,n)", "description": "", "templateType": "anything", "can_override": false}, "p": {"name": "p", "group": "Ungrouped variables", "definition": "iterates[-1]", "description": "<p>Prime factor found.</p>", "templateType": "anything", "can_override": false}, "nf": {"name": "nf", "group": "Ungrouped variables", "definition": "4", "description": "", "templateType": "anything", "can_override": false}, "a": {"name": "a", "group": "Ungrouped variables", "definition": "random(primitiveroots(n,100))", "description": "", "templateType": "anything", "can_override": false}, "y": {"name": "y", "group": "Ungrouped variables", "definition": "powmod(a,x,n)", "description": "", "templateType": "anything", "can_override": false}, "v": {"name": "v", "group": "Ungrouped variables", "definition": "mod(p[1][2]-p[0][2],n-1)", "description": "", "templateType": "anything", "can_override": false}, "u": {"name": "u", "group": "Ungrouped variables", "definition": "mod(p[0][1]-p[1][1],n-1)", "description": "", "templateType": "anything", "can_override": false}, "w": {"name": "w", "group": "Ungrouped variables", "definition": "mod(invert(v,n-1)*u,n-1)", "description": "", "templateType": "anything", "can_override": false}, "x": {"name": "x", "group": "Ungrouped variables", "definition": "random(2..n-2)", "description": "", "templateType": "anything", "can_override": false}, "bookiterates": {"name": "bookiterates", "group": "Ungrouped variables", "definition": "iterate_until([psibook(x,y,a,n),psibook(psi(z,y,a,n),y,a,n)],[x,z],[x1,y1],x[0]=z[0],n)", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "gcd(v,n-1)=1 and len(iterates)<7", "maxRuns": 100}, "ungrouped_variables": ["nf", "factors", "n", "a", "x", "y", "x0", "iterates", "x1", "y1", "p", "v", "u", "w", "bookiterates"], "variable_groups": [], "functions": {"f": {"parameters": [["x", "list of number"], ["n", "number"]], "type": "list", "language": "jme", "definition": "[powmod(x[0],2,n),mod(2*x[1],n-1),mod(2*x[2],n-1)]"}, "g": {"parameters": [["x", "list of number"], ["a", "number"], ["n", "number"]], "type": "list", "language": "jme", "definition": "[mod(a*x[0],n),mod(x[1]+1,n-1),mod(x[2],n-1)]"}, "h": {"parameters": [["x", "list of number"], ["y", "number"], ["n", "number"]], "type": "list", "language": "jme", "definition": "[mod(y*x[0],n),mod(x[1],n-1),mod(x[2]+1,n-1)]"}, "psi": {"parameters": [["x", "list of number"], ["y", "number"], ["a", "number"], ["n", "number"]], "type": "list", "language": "jme", "definition": "[f(x,n),g(x,a,n),h(x,y,n)][mod(x[0],3)]"}, "psibook": {"parameters": [["x", "list of number"], ["y", "number"], ["a", "number"], ["n", "number"]], "type": "list", "language": "jme", "definition": "if(x[0]<2*n/3 and x[0]>= n/3, f(x,n),\n  if(x[0]<2*n/3, g(x,a,n),\n    h(x,y,n))\n  )"}}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "jme", "useCustomName": true, "customName": "Iterates - first part", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Enter the list of iterates for the triples $X_i$, as follows: [{x0},$X_1$,...].</p>", "answer": "{map(x[0],x,iterates)}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": []}, {"type": "jme", "useCustomName": true, "customName": "Iterates - second part", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Enter the list of iterates for the triples $Y_i$, as follows: [{x0},$Y_1$,...].</p>", "answer": "{map(x[1],x,iterates)}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": []}, {"type": "numberentry", "useCustomName": true, "customName": "Discrete Logarithm", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Enter the solution that you found.</p>", "minValue": "w", "maxValue": "w", "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/"}]}]}], "contributors": [{"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}]}