saymrwulf/NTT-learning
1
0
Fork 0
mirror of https://github.com/saymrwulf/NTT-learning.git synced 2026-05-14 20:47:53 +00:00
Code Issues Projects Releases Packages Wiki Activity Actions
NTT-learning/notebooks/professional/06_debugging_ntt_failures/problems.ipynb

175 lines
14 KiB
Text
Raw Permalink Blame History

{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"pedagogy": {
"role": "meta",
"difficulty": 1,
"kind": "theme",
"title": "Notebook Theme"
}
},
"source": "<style>\n.jp-RenderedHTMLCommon .ntt-cell-head {\n position: relative;\n margin: 0 0 0.8rem 0;\n padding: 0.95rem 1rem 1rem 1rem;\n border-radius: 16px;\n border: 1px solid rgba(16,42,67,0.12);\n box-shadow: 0 8px 24px rgba(16,42,67,0.06);\n font-family: \"Avenir Next\", \"Trebuchet MS\", sans-serif;\n}\n\n.jp-RenderedHTMLCommon .ntt-cell-topline {\n display: flex;\n flex-wrap: wrap;\n gap: 0.5rem;\n align-items: center;\n margin-bottom: 0.55rem;\n}\n\n.jp-RenderedHTMLCommon .ntt-kind-pill,\n.jp-RenderedHTMLCommon .ntt-route-pill,\n.jp-RenderedHTMLCommon .ntt-difficulty-pill {\n display: inline-flex;\n align-items: center;\n padding: 0.18rem 0.58rem;\n border-radius: 999px;\n font-size: 0.72rem;\n font-weight: 800;\n letter-spacing: 0.04em;\n text-transform: uppercase;\n}\n\n.jp-RenderedHTMLCommon .ntt-role-meta {\n background: linear-gradient(135deg, #e2f3ff 0%, #f5fbff 100%);\n}\n\n.jp-RenderedHTMLCommon .ntt-role-mandatory {\n background: linear-gradient(135deg, #fff1b8 0%, #ffd980 100%);\n}\n\n.jp-RenderedHTMLCommon .ntt-role-facultative {\n background: linear-gradient(135deg, #ffe3d4 0%, #ffc3ae 100%);\n}\n\n.jp-RenderedHTMLCommon .ntt-kind-pill {\n color: #102a43;\n background: rgba(16,42,67,0.08);\n}\n\n.jp-RenderedHTMLCommon .ntt-route-pill {\n color: #102a43;\n background: rgba(255,255,255,0.82);\n}\n\n.jp-RenderedHTMLCommon .ntt-difficulty-pill {\n position: absolute;\n top: 0.95rem;\n right: 1rem;\n color: #102a43;\n background: rgba(255,255,255,0.88);\n border: 1px solid rgba(16,42,67,0.08);\n box-shadow: 0 4px 12px rgba(16,42,67,0.08);\n}\n\n.jp-RenderedHTMLCommon .ntt-cell-title {\n margin: 0;\n font-size: 1.25rem;\n line-height: 1.25;\n font-weight: 850;\n color: #102a43;\n padding-right: 5.3rem;\n}\n\n.jp-RenderedHTMLCommon .ntt-cell-body-hint {\n margin-top: 0.3rem;\n font-size: 0.84rem;\n color: #486581;\n}\n\n.jupyter-widgets.widget-container,\n.jupyter-widgets.widget-box,\n.jupyter-widgets.widget-vbox,\n.jupyter-widgets.widget-hbox {\n width: 100% !important;\n max-width: 100% !important;\n min-width: 0 !important;\n}\n\n.widget-html-content svg {\n display: block !important;\n width: 100% !important;\n max-width: 100% !important;\n height: auto !important;\n}\n</style>\n"
},
{
"cell_type": "markdown",
"metadata": {
"pedagogy": {
"role": "meta",
"difficulty": 1,
"kind": "route_nav",
"title": "Route Guardrails"
}
},
"source": "<div class=\"ntt-cell-head ntt-role-meta\">\n <span class=\"ntt-difficulty-pill\">Level 1</span>\n <div class=\"ntt-cell-topline\">\n <span class=\"ntt-kind-pill\">route map</span>\n <span class=\"ntt-route-pill\">route help</span>\n </div>\n <h2 class=\"ntt-cell-title\">Route Guardrails</h2>\n</div>\n\nYou are at **step 25 of 27** in the only supported route.\n\nNever choose the next notebook manually from the file tree. Use only the links in this cell and the final handoff cell.\n\n**Immediate navigation**\n- Next notebook: [Professional / 06 Debugging NTT Failures / Studio](studio.ipynb)\n- Previous notebook: [Professional / 06 Debugging NTT Failures / Lab](lab.ipynb)\n- Restart route: [Start Here](../../START_HERE.ipynb)\n\n**Official route chain**\n1. [Start Here](../../START_HERE.ipynb)\n2. [Course Blueprint](../../COURSE_BLUEPRINT.ipynb)\n3. [Foundations / 01 Convolution To Toy NTT / Lecture](../../foundations/01_convolution_to_toy_ntt/lecture.ipynb)\n4. [Foundations / 01 Convolution To Toy NTT / Lab](../../foundations/01_convolution_to_toy_ntt/lab.ipynb)\n5. [Foundations / 01 Convolution To Toy NTT / Problems](../../foundations/01_convolution_to_toy_ntt/problems.ipynb)\n6. [Foundations / 01 Convolution To Toy NTT / Studio](../../foundations/01_convolution_to_toy_ntt/studio.ipynb)\n7. [Foundations / 02 Negative Wrapped NTT / Lecture](../../foundations/02_negative_wrapped_ntt/lecture.ipynb)\n8. [Foundations / 02 Negative Wrapped NTT / Lab](../../foundations/02_negative_wrapped_ntt/lab.ipynb)\n9. [Foundations / 02 Negative Wrapped NTT / Problems](../../foundations/02_negative_wrapped_ntt/problems.ipynb)\n10. [Foundations / 02 Negative Wrapped NTT / Studio](../../foundations/02_negative_wrapped_ntt/studio.ipynb)\n11. [Butterfly Mechanics / 03 Fast Forward CT / Lecture](../../butterfly_mechanics/03_fast_forward_ct/lecture.ipynb)\n12. [Butterfly Mechanics / 03 Fast Forward CT / Lab](../../butterfly_mechanics/03_fast_forward_ct/lab.ipynb)\n13. [Butterfly Mechanics / 03 Fast Forward CT / Problems](../../butterfly_mechanics/03_fast_forward_ct/problems.ipynb)\n14. [Butterfly Mechanics / 03 Fast Forward CT / Studio](../../butterfly_mechanics/03_fast_forward_ct/studio.ipynb)\n15. [Butterfly Mechanics / 04 Fast Inverse GS / Lecture](../../butterfly_mechanics/04_fast_inverse_gs/lecture.ipynb)\n16. [Butterfly Mechanics / 04 Fast Inverse GS / Lab](../../butterfly_mechanics/04_fast_inverse_gs/lab.ipynb)\n17. [Butterfly Mechanics / 04 Fast Inverse GS / Problems](../../butterfly_mechanics/04_fast_inverse_gs/problems.ipynb)\n18. [Butterfly Mechanics / 04 Fast Inverse GS / Studio](../../butterfly_mechanics/04_fast_inverse_gs/studio.ipynb)\n19. [Kyber Mapping / 05 Kyber NTT And Base Multiplication / Lecture](../../kyber_mapping/05_kyber_ntt_and_base_multiplication/lecture.ipynb)\n20. [Kyber Mapping / 05 Kyber NTT And Base Multiplication / Lab](../../kyber_mapping/05_kyber_ntt_and_base_multiplication/lab.ipynb)\n21. [Kyber Mapping / 05 Kyber NTT And Base Multiplication / Problems](../../kyber_mapping/05_kyber_ntt_and_base_multiplication/problems.ipynb)\n22. [Kyber Mapping / 05 Kyber NTT And Base Multiplication / Studio](../../kyber_mapping/05_kyber_ntt_and_base_multiplication/studio.ipynb)\n23. [Professional / 06 Debugging NTT Failures / Lecture](lecture.ipynb)\n24. [Professional / 06 Debugging NTT Failures / Lab](lab.ipynb)\n25. **Professional / 06 Debugging NTT Failures / Problems** <- you are here\n26. [Professional / 06 Debugging NTT Failures / Studio](studio.ipynb)\n27. [Course Complete](../../COURSE_COMPLETE.ipynb)\n"
},
{
"cell_type": "markdown",
"metadata": {
"pedagogy": {
"role": "meta",
"difficulty": 1,
"kind": "orientation",
"title": "Problem Set Goals"
}
},
"source": "<div class=\"ntt-cell-head ntt-role-meta\">\n <span class=\"ntt-difficulty-pill\">Level 1</span>\n <div class=\"ntt-cell-topline\">\n <span class=\"ntt-kind-pill\">big picture</span>\n <span class=\"ntt-route-pill\">route help</span>\n </div>\n <h2 class=\"ntt-cell-title\">Problem Set Goals</h2>\n</div>\n\nThis notebook checks whether the main NTT bug classes are now distinct in memory.\n"
},
{
"cell_type": "markdown",
"metadata": {
"pedagogy": {
"role": "mandatory",
"difficulty": 2,
"kind": "quiz",
"title": "Multiple-Choice Retrieval"
}
},
"source": "<div class=\"ntt-cell-head ntt-role-mandatory\">\n <span class=\"ntt-difficulty-pill\">Level 2</span>\n <div class=\"ntt-cell-topline\">\n <span class=\"ntt-kind-pill\">quiz</span>\n <span class=\"ntt-route-pill\">core path</span>\n </div>\n <h2 class=\"ntt-cell-title\">Multiple-Choice Retrieval</h2>\n</div>\n\nChoose one answer for each:\n\n1. A shuffled but otherwise familiar forward result most strongly suggests:\n A. missing final scaling\n B. wrong BO / NO comparison\n C. wrong modulus\n\n2. An inverse output that looks like a clean multiple of the target most strongly suggests:\n A. missing `n^-1`\n B. wrong wraparound sign\n C. wrong bit-reversal map\n\n3. A local pair that already looks broken in stage 1 most strongly suggests:\n A. wrong zeta\n B. correct CT output\n C. harmless ordering noise\n"
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"pedagogy": {
"role": "mandatory",
"difficulty": 2,
"kind": "quiz",
"title": "Answer Key"
}
},
"outputs": [],
"source": "# Answer Key\n\nanswers = {1: \"B\", 2: \"A\", 3: \"A\"}\nprint(answers)\n"
},
{
"cell_type": "markdown",
"metadata": {
"pedagogy": {
"role": "mandatory",
"difficulty": 2,
"kind": "exercise",
"title": "Debug Priority Check"
}
},
"source": "<div class=\"ntt-cell-head ntt-role-mandatory\">\n <span class=\"ntt-difficulty-pill\">Level 2</span>\n <div class=\"ntt-cell-topline\">\n <span class=\"ntt-kind-pill\">exercise</span>\n <span class=\"ntt-route-pill\">core path</span>\n </div>\n <h2 class=\"ntt-cell-title\">Debug Priority Check</h2>\n</div>\n\nList the first four checks you would run on a suspicious iNTT output.\n"
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"pedagogy": {
"role": "mandatory",
"difficulty": 2,
"kind": "exercise",
"title": "One Good Ordering"
}
},
"outputs": [],
"source": "# One Good Ordering\n\ndebug_order = [\n \"check BO / NO assumption\",\n \"check root / zeta schedule\",\n \"check final n^-1 scaling\",\n \"check sign / wraparound conventions\",\n]\nprint(debug_order)\n"
},
{
"cell_type": "markdown",
"metadata": {
"pedagogy": {
"role": "mandatory",
"difficulty": 2,
"kind": "reflection",
"title": "Written Reflection"
}
},
"source": "<div class=\"ntt-cell-head ntt-role-mandatory\">\n <span class=\"ntt-difficulty-pill\">Level 2</span>\n <div class=\"ntt-cell-topline\">\n <span class=\"ntt-kind-pill\">reflection</span>\n <span class=\"ntt-route-pill\">core path</span>\n </div>\n <h2 class=\"ntt-cell-title\">Written Reflection</h2>\n</div>\n\nIn one paragraph, explain why visible traces are much better debugging tools than only comparing final vectors.\n"
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"pedagogy": {
"role": "facultative",
"difficulty": 4,
"kind": "exploration",
"title": "Optional Challenge"
}
},
"outputs": [],
"source": "# Optional Challenge\n\nmistakes = {\n \"wrong_order\": \"fix the permutation first\",\n \"missing_scale\": \"multiply by n^-1\",\n \"wrong_zeta\": \"rebuild the twiddle schedule\",\n \"wrong_sign\": \"inspect the quotient ring\",\n}\nfor key, value in mistakes.items():\n print(key, \"->\", value)\n"
},
{
"cell_type": "markdown",
"metadata": {
"pedagogy": {
"role": "meta",
"difficulty": 1,
"kind": "handoff",
"title": "Next Notebook"
}
},
"source": "<div class=\"ntt-cell-head ntt-role-meta\">\n <span class=\"ntt-difficulty-pill\">Level 1</span>\n <div class=\"ntt-cell-topline\">\n <span class=\"ntt-kind-pill\">next step</span>\n <span class=\"ntt-route-pill\">route help</span>\n </div>\n <h2 class=\"ntt-cell-title\">Next Notebook</h2>\n</div>\n\nYou finished **Professional / 06 Debugging NTT Failures / Problems**.\n\n**Primary next action**\n- Next notebook: [Step 26 of 27 - Professional / 06 Debugging NTT Failures / Studio](studio.ipynb)\n\n**Recovery links if you get lost**\n- Previous notebook: [Professional / 06 Debugging NTT Failures / Lab](lab.ipynb)\n- Restart route: [Start Here](../../START_HERE.ipynb)\n"
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"name": "python"
},
"ntt_learning": {
"title": "Problems: Debugging NTT Failures",
"contract_version": "0.2",
"sequence": [
"notebooks/START_HERE.ipynb",
"notebooks/COURSE_BLUEPRINT.ipynb",
"notebooks/foundations/01_convolution_to_toy_ntt/lecture.ipynb",
"notebooks/foundations/01_convolution_to_toy_ntt/lab.ipynb",
"notebooks/foundations/01_convolution_to_toy_ntt/problems.ipynb",
"notebooks/foundations/01_convolution_to_toy_ntt/studio.ipynb",
"notebooks/foundations/02_negative_wrapped_ntt/lecture.ipynb",
"notebooks/foundations/02_negative_wrapped_ntt/lab.ipynb",
"notebooks/foundations/02_negative_wrapped_ntt/problems.ipynb",
"notebooks/foundations/02_negative_wrapped_ntt/studio.ipynb",
"notebooks/butterfly_mechanics/03_fast_forward_ct/lecture.ipynb",
"notebooks/butterfly_mechanics/03_fast_forward_ct/lab.ipynb",
"notebooks/butterfly_mechanics/03_fast_forward_ct/problems.ipynb",
"notebooks/butterfly_mechanics/03_fast_forward_ct/studio.ipynb",
"notebooks/butterfly_mechanics/04_fast_inverse_gs/lecture.ipynb",
"notebooks/butterfly_mechanics/04_fast_inverse_gs/lab.ipynb",
"notebooks/butterfly_mechanics/04_fast_inverse_gs/problems.ipynb",
"notebooks/butterfly_mechanics/04_fast_inverse_gs/studio.ipynb",
"notebooks/kyber_mapping/05_kyber_ntt_and_base_multiplication/lecture.ipynb",
"notebooks/kyber_mapping/05_kyber_ntt_and_base_multiplication/lab.ipynb",
"notebooks/kyber_mapping/05_kyber_ntt_and_base_multiplication/problems.ipynb",
"notebooks/kyber_mapping/05_kyber_ntt_and_base_multiplication/studio.ipynb",
"notebooks/professional/06_debugging_ntt_failures/lecture.ipynb",
"notebooks/professional/06_debugging_ntt_failures/lab.ipynb",
"notebooks/professional/06_debugging_ntt_failures/problems.ipynb",
"notebooks/professional/06_debugging_ntt_failures/studio.ipynb",
"notebooks/COURSE_COMPLETE.ipynb"
]
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Reference in a new issue View git blame Copy permalink