cell_dependencies $d882afdd-eb85-467c-bf18-525c0c5da5e7precedence_heuristic cell_id$d882afdd-eb85-467c-bf18-525c0c5da5e7downstream_cells_mapupstream_cells_map @timeBase.===Base.GC_DiffBase.stringBase.time_printBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numBase.cumulative_compile_time_nsBasefib_diag$d830fffd-3781-40ca-85cb-c242f99667ceBase.time_nsBase./$1b1d5c9b-5fc7-480e-9649-e9c44a49c38dprecedence_heuristiccell_id$1b1d5c9b-5fc7-480e-9649-e9c44a49c38ddownstream_cells_mapupstream_cells_mapinclude$4cb070de-e8bf-4a1d-9625-043c19466c46precedence_heuristic cell_id$4cb070de-e8bf-4a1d-9625-043c19466c46downstream_cells_mapupstream_cells_map @timeBase.===Base.GC_DiffBase.stringBase.time_printfib_pow$38744170-9af6-44b5-a0be-46a83da3253eBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numBase.cumulative_compile_time_nsBaseBase.time_nsBase./$aee611f2-bc86-4e85-bbcb-add78c6a9175precedence_heuristic cell_id$aee611f2-bc86-4e85-bbcb-add78c6a9175downstream_cells_mapgcd_x$40b8e474-16e0-4a61-bb28-11d90beefeeagcd_ggcd_y$40b8e474-16e0-4a61-bb28-11d90beefeeaupstream_cells_mapgcd_b$f39cccac-5b24-46e4-8749-1b0a944542efgcd_a$1a4da418-147f-46f4-9b95-7955183aa5cfpgcdx$3f1af973-a02b-4e06-8e6e-eff414fcaf67$5c6c45b4-67e3-4ea8-bc09-0205ab24cbc3precedence_heuristic cell_id$5c6c45b4-67e3-4ea8-bc09-0205ab24cbc3downstream_cells_mapupstream_cells_mapmodb$18031ccb-657f-409a-9080-9a0ada3ae8b5*a$b57adc77-3783-4958-91a0-e90782338755n$256c8009-4d2b-42f8-adaa-6f238ef22c6d$6c3595d2-4f68-44da-90e7-dc9c68479bcfprecedence_heuristic cell_id$6c3595d2-4f68-44da-90e7-dc9c68479bcfdownstream_cells_mapcite$3df688c8-1c52-462d-88be-daa153333c60$a7afc0cb-a980-4f4f-b782-9791d932ee52$ed023033-1044-4d48-aab1-39e9300043f7$bcf73ad7-a08b-4cbb-bcd2-d0abc002e7e2$bc9a718f-4b97-4e15-acf8-d180abc5b6d5$1072a756-5026-4de9-93a8-f942d54c474a$35b7b8b7-bff6-4f64-91b9-b65035162365upstream_cells_mapbibcitebiblio$ba16d83d-21a5-4f0c-807b-674a167da4dc$cd481f6c-66f4-4ebf-9769-c3edc24f403bprecedence_heuristic cell_id$cd481f6c-66f4-4ebf-9769-c3edc24f403bdownstream_cells_mapupstream_cells_mapframetitle$37585789-bd43-4ce5-b550-ad712b70d226precedence_heuristic cell_id$37585789-bd43-4ce5-b550-ad712b70d226downstream_cells_mapupstream_cells_map@md_strgetindex$4a98507b-653e-4354-a825-7605f8fcb31bprecedence_heuristic cell_id$4a98507b-653e-4354-a825-7605f8fcb31bdownstream_cells_mapupstream_cells_mapfast_mod_power$8670abc2-63e6-496a-b20c-812197acd9ad:g$0e3fb524-bea1-4ef0-9589-36230a84e949mod^*adjointconj$bcf73ad7-a08b-4cbb-bcd2-d0abc002e7e2precedence_heuristic cell_id$bcf73ad7-a08b-4cbb-bcd2-d0abc002e7e2downstream_cells_mapupstream_cells_map@md_strcite$6c3595d2-4f68-44da-90e7-dc9c68479bcfqagetindex$b319619e-8f8d-4650-8fb4-76e5ba953470precedence_heuristic cell_id$b319619e-8f8d-4650-8fb4-76e5ba953470downstream_cells_mapupstream_cells_map@md_strgetindex$08dcbbd3-a531-4f74-a724-1cae8fae1636precedence_heuristic cell_id$08dcbbd3-a531-4f74-a724-1cae8fae1636downstream_cells_mapupstream_cells_map@md_strlengthg$0e3fb524-bea1-4ef0-9589-36230a84e949unique-sortall_powers$59ac02af-7b54-44d4-b5f4-a0f60d4458a1==p$57816e2c-a675-43e7-b674-2877ffcf1415getindex$ce07d5c5-90a3-4c12-bada-30e4da1b99fdprecedence_heuristic cell_id$ce07d5c5-90a3-4c12-bada-30e4da1b99fddownstream_cells_mapupstream_cells_mapfast_mod_power$8670abc2-63e6-496a-b20c-812197acd9ad:g$0e3fb524-bea1-4ef0-9589-36230a84e949$ec25ce2a-de8a-4b69-a3f3-b47cd58ec986precedence_heuristic cell_id$ec25ce2a-de8a-4b69-a3f3-b47cd58ec986downstream_cells_mapupstream_cells_mapchinese_remainder_theorem$821de132-559b-4420-b866-e97134c5bd9apow_1000$77093b36-c232-4477-be49-845f1a631829pow_999$65f4990f-1952-4682-8fa8-9e3dd4bf1ebf$821de132-559b-4420-b866-e97134c5bd9aprecedence_heuristic cell_id$821de132-559b-4420-b866-e97134c5bd9adownstream_cells_mapchinese_remainder_theorem$ec25ce2a-de8a-4b69-a3f3-b47cd58ec986$191f8429-cbbb-44aa-8beb-271a94293e4bupstream_cells_mapgcdsumeachindexmod!===errordivprodmodinv$21df1900-3954-4506-b759-aeeee664d1df*$bc58ba24-90f0-4913-8f66-10bb6cb54076precedence_heuristic cell_id$bc58ba24-90f0-4913-8f66-10bb6cb54076downstream_cells_mapupstream_cells_map@md_strgetindex$35b7b8b7-bff6-4f64-91b9-b65035162365precedence_heuristic cell_id$35b7b8b7-bff6-4f64-91b9-b65035162365downstream_cells_mapupstream_cells_map@md_strcite$6c3595d2-4f68-44da-90e7-dc9c68479bcfgetindex$59ac02af-7b54-44d4-b5f4-a0f60d4458a1precedence_heuristic cell_id$59ac02af-7b54-44d4-b5f4-a0f60d4458a1downstream_cells_mapall_powers$9f55cad1-b01a-45e3-93df-a4349e2dfbd3$e2a3842d-4e07-4703-ab47-a5140649dd6a$08dcbbd3-a531-4f74-a724-1cae8fae1636$4be6cea4-13a2-4bcb-b849-14eef57ab604upstream_cells_mapfast_mod_power$8670abc2-63e6-496a-b20c-812197acd9ad:g$0e3fb524-bea1-4ef0-9589-36230a84e949-p$57816e2c-a675-43e7-b674-2877ffcf1415$c2fab245-8a98-4b41-ade2-c5b16e9c39f9precedence_heuristic cell_id$c2fab245-8a98-4b41-ade2-c5b16e9c39f9downstream_cells_mapupstream_cells_mapframetitle$535f4bc1-e88c-47c7-990b-e3c8b5054accprecedence_heuristic cell_id$535f4bc1-e88c-47c7-990b-e3c8b5054accdownstream_cells_mapfib_closed$9b9fc5e6-1a41-43c5-ba43-2c93bc3ef66bupstream_cells_map-sqrt/^+√big$6107d03d-1e45-4eb9-b8e2-51e4a72485e6precedence_heuristic cell_id$6107d03d-1e45-4eb9-b8e2-51e4a72485e6downstream_cells_mapupstream_cells_mapframetitle$03e49669-cdee-4241-862d-33ee91214455precedence_heuristic cell_id$03e49669-cdee-4241-862d-33ee91214455downstream_cells_mapupstream_cells_map@md_strgetindex$ac5e1516-1574-4893-a965-f799947076cbprecedence_heuristic cell_id$ac5e1516-1574-4893-a965-f799947076cbdownstream_cells_mapupstream_cells_map @timeBase.===Base.GC_DiffBase.stringBase.time_printBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numBase.cumulative_compile_time_nsBasefib_diag$d830fffd-3781-40ca-85cb-c242f99667ceBase.time_nsBase./$a826d9d1-47db-4645-be6e-3ae0ed8d4e18precedence_heuristic cell_id$a826d9d1-47db-4645-be6e-3ae0ed8d4e18downstream_cells_mapupstream_cells_map@md_strgetindex$b5f3620d-0942-41bb-80b0-d2ddcfe65090precedence_heuristic cell_id$b5f3620d-0942-41bb-80b0-d2ddcfe65090downstream_cells_mapE$6cf004be-5205-429e-8131-ef607cebeaec$f6e22fc3-382e-4548-bc59-8f944e06d237$d830fffd-3781-40ca-85cb-c242f99667ceupstream_cells_mapeigen$bbc907b1-63f8-435a-badc-11ed88bd6cf5precedence_heuristic cell_id$bbc907b1-63f8-435a-badc-11ed88bd6cf5downstream_cells_mapupstream_cells_mapframetitle$ae89661a-2c0f-4752-adc2-023f09dc0e9fprecedence_heuristic cell_id$ae89661a-2c0f-4752-adc2-023f09dc0e9fdownstream_cells_mapupstream_cells_mapfast_mod_power$8670abc2-63e6-496a-b20c-812197acd9ad:g$0e3fb524-bea1-4ef0-9589-36230a84e949reshape$0c8ab02e-80b0-44d6-a4a8-c813aac38209precedence_heuristic cell_id$0c8ab02e-80b0-44d6-a4a8-c813aac38209downstream_cells_mapfib_n$708c442b-cbff-4e1a-b70d-e704453cfd3dfib_picker$708c442b-cbff-4e1a-b70d-e704453cfd3dupstream_cells_mapCoreBase:PlutoRunner.create_bondPlutoRunnerCore.applicable@bindBase.getSlider$f9f03579-5bfc-452d-bff9-9e7adfe095d3precedence_heuristic cell_id$f9f03579-5bfc-452d-bff9-9e7adfe095d3downstream_cells_mapupstream_cells_mapgcd$a1628317-7937-4316-85bf-2da860effce3precedence_heuristic cell_id$a1628317-7937-4316-85bf-2da860effce3downstream_cells_mapupstream_cells_mapmodb$18031ccb-657f-409a-9080-9a0ada3ae8b5*a$b57adc77-3783-4958-91a0-e90782338755n$256c8009-4d2b-42f8-adaa-6f238ef22c6d$a7985d16-500b-4024-aaa1-78e654b94be4precedence_heuristic cell_id$a7985d16-500b-4024-aaa1-78e654b94be4downstream_cells_mapupstream_cells_map@md_strqagetindex$4c2d45e3-56a2-467f-b87f-7b98cb873a05precedence_heuristic cell_id$4c2d45e3-56a2-467f-b87f-7b98cb873a05downstream_cells_mapupstream_cells_mapfast_mod_power$8670abc2-63e6-496a-b20c-812197acd9adprime_list$16b677e4-c467-462a-b770-b7a31160e129power$2381babe-0777-45db-acff-cc647a8a68d3$4cff1d10-422f-4b12-b790-a589c972fbb7precedence_heuristic cell_id$4cff1d10-422f-4b12-b790-a589c972fbb7downstream_cells_mapupstream_cells_mapgp_picker$0e3fb524-bea1-4ef0-9589-36230a84e949$087cbe82-b42a-4f80-a1af-97f3aa93aeebprecedence_heuristic cell_id$087cbe82-b42a-4f80-a1af-97f3aa93aeebdownstream_cells_mapupstream_cells_map@md_strpower_slider$2381babe-0777-45db-acff-cc647a8a68d3getindex$7db2060b-d69e-42e7-ae81-fd37ee793876precedence_heuristic cell_id$7db2060b-d69e-42e7-ae81-fd37ee793876downstream_cells_mapupstream_cells_map@md_strgetindex$a293bb0e-078d-4335-a446-3096a79c03bcprecedence_heuristic cell_id$a293bb0e-078d-4335-a446-3096a79c03bcdownstream_cells_mapupstream_cells_mapframetitle$2381babe-0777-45db-acff-cc647a8a68d3precedence_heuristic cell_id$2381babe-0777-45db-acff-cc647a8a68d3downstream_cells_mappower_slider$c8f85081-3659-4796-8550-2e708b09c8d7$087cbe82-b42a-4f80-a1af-97f3aa93aeebpower$7881bb75-3ef9-496e-860b-03ced6b593c5$9e8a61d9-a700-4851-b1cd-49ce042c3530$3c198d79-c46a-4781-8bd1-b6b68f06c31f$77093b36-c232-4477-be49-845f1a631829$65f4990f-1952-4682-8fa8-9e3dd4bf1ebf$9cef898e-192c-418a-bec6-511f8b6da179$4c2d45e3-56a2-467f-b87f-7b98cb873a05$191f8429-cbbb-44aa-8beb-271a94293e4b$e9633e3f-376d-413d-bc19-d015f6ce76e5upstream_cells_mapCoreBase:PlutoRunner.create_bondPlutoRunnerCore.applicable@bindBase.getSlider$e1aafab7-c4f3-45ac-81ee-7f875ac7c8c6precedence_heuristic cell_id$e1aafab7-c4f3-45ac-81ee-7f875ac7c8c6downstream_cells_mapupstream_cells_map@md_strgetindex$9f55cad1-b01a-45e3-93df-a4349e2dfbd3precedence_heuristic cell_id$9f55cad1-b01a-45e3-93df-a4349e2dfbd3downstream_cells_mapupstream_cells_mapsortall_powers$59ac02af-7b54-44d4-b5f4-a0f60d4458a1$4be6cea4-13a2-4bcb-b849-14eef57ab604precedence_heuristic cell_id$4be6cea4-13a2-4bcb-b849-14eef57ab604downstream_cells_mapupstream_cells_map@md_strlengthg$0e3fb524-bea1-4ef0-9589-36230a84e949unique-sortall_powers$59ac02af-7b54-44d4-b5f4-a0f60d4458a1==p$57816e2c-a675-43e7-b674-2877ffcf1415getindex$9d4858f8-e63d-46e0-a6cc-992d3cc4a9a4precedence_heuristic cell_id$9d4858f8-e63d-46e0-a6cc-992d3cc4a9a4downstream_cells_mapupstream_cells_map@md_strqagetindex$c8f85081-3659-4796-8550-2e708b09c8d7precedence_heuristic cell_id$c8f85081-3659-4796-8550-2e708b09c8d7downstream_cells_mapupstream_cells_map@md_strpower_slider$2381babe-0777-45db-acff-cc647a8a68d3getindex$0e3fb524-bea1-4ef0-9589-36230a84e949precedence_heuristic cell_id$0e3fb524-bea1-4ef0-9589-36230a84e949downstream_cells_mapg$59ac02af-7b54-44d4-b5f4-a0f60d4458a1$08dcbbd3-a531-4f74-a724-1cae8fae1636$4be6cea4-13a2-4bcb-b849-14eef57ab604$9efb7a71-9a03-4716-8d34-aae233e9b898$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253$ce07d5c5-90a3-4c12-bada-30e4da1b99fd$ae89661a-2c0f-4752-adc2-023f09dc0e9f$4a98507b-653e-4354-a825-7605f8fcb31b$59254bfd-48f2-4585-9ba5-e4c809421072$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fdgp_picker$4cff1d10-422f-4b12-b790-a589c972fbb7$059b0ada-2442-48e4-82dd-489cb97e5dccupstream_cells_map@md_strCorePlutoRunnerPlutoRunner.create_bondCore.applicableHAligngetindexp_picker$57816e2c-a675-43e7-b674-2877ffcf1415:Base.get@bindSliderBase-p$57816e2c-a675-43e7-b674-2877ffcf1415$a7d06375-e4dd-47b1-8aba-11dc4d62954bprecedence_heuristic cell_id$a7d06375-e4dd-47b1-8aba-11dc4d62954bdownstream_cells_mapupstream_cells_map@md_strqagetindex$bbb2793a-faa4-43bd-b2e8-e8d3ac93310fprecedence_heuristic cell_id$bbb2793a-faa4-43bd-b2e8-e8d3ac93310fdownstream_cells_mapupstream_cells_map@md_strgetindex$7330af43-bec3-460c-94f6-768ac2975b00precedence_heuristic cell_id$7330af43-bec3-460c-94f6-768ac2975b00downstream_cells_mapshanks_discrete_log$59254bfd-48f2-4585-9ba5-e4c809421072upstream_cells_mapgiant_steps$3026f9c5-81d3-443a-940a-f22fef9754afmodisqrtcollision$6e5e3ec6-c96a-4a4a-bf4d-4b115f9b0d82-+baby_steps$4853f4ef-fbb8-48c3-9523-13ab4969d097*$67093a35-8e1b-4cd3-b11b-c7ff601f802eprecedence_heuristic cell_id$67093a35-8e1b-4cd3-b11b-c7ff601f802edownstream_cells_mapprimes_upper$16b677e4-c467-462a-b770-b7a31160e129upstream_cells_map@md_strCorePlutoRunnerPlutoRunner.create_bondCore.applicablegetindex:Base.get@bindSliderBase$48eba223-6cce-4aa2-9977-4883ba7903fcprecedence_heuristic cell_id$48eba223-6cce-4aa2-9977-4883ba7903fcdownstream_cells_mapupstream_cells_map@md_strqagetindex$6f10de7b-ce05-4f82-82e7-4110be44e8ccprecedence_heuristic cell_id$6f10de7b-ce05-4f82-82e7-4110be44e8ccdownstream_cells_mapupstream_cells_mapmodmodinv$21df1900-3954-4506-b759-aeeee664d1df+pow_1000$77093b36-c232-4477-be49-845f1a631829pow_999$65f4990f-1952-4682-8fa8-9e3dd4bf1ebf*$1ca71c26-f98c-4126-a1c5-98786fde7e9bprecedence_heuristic cell_id$1ca71c26-f98c-4126-a1c5-98786fde7e9bdownstream_cells_mapupstream_cells_map@md_strgetindex$82ba8fe1-435e-422b-abb7-cb50a7a85e1eprecedence_heuristic cell_id$82ba8fe1-435e-422b-abb7-cb50a7a85e1edownstream_cells_mapupstream_cells_mapframetitle$61462af5-69bd-42be-8918-7992c79ee00dprecedence_heuristic cell_id$61462af5-69bd-42be-8918-7992c79ee00ddownstream_cells_mapupstream_cells_map@md_strqagetindex$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fdprecedence_heuristic cell_id$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fddownstream_cells_mapupstream_cells_mapfast_mod_power$8670abc2-63e6-496a-b20c-812197acd9adg$0e3fb524-bea1-4ef0-9589-36230a84e949shanks_x$59254bfd-48f2-4585-9ba5-e4c809421072p$57816e2c-a675-43e7-b674-2877ffcf1415$57816e2c-a675-43e7-b674-2877ffcf1415precedence_heuristic cell_id$57816e2c-a675-43e7-b674-2877ffcf1415downstream_cells_mapp_picker$0e3fb524-bea1-4ef0-9589-36230a84e949p$59ac02af-7b54-44d4-b5f4-a0f60d4458a1$08dcbbd3-a531-4f74-a724-1cae8fae1636$4be6cea4-13a2-4bcb-b849-14eef57ab604$9efb7a71-9a03-4716-8d34-aae233e9b898$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253$59254bfd-48f2-4585-9ba5-e4c809421072$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fd$0e3fb524-bea1-4ef0-9589-36230a84e949upstream_cells_mapCoreBasePlutoRunner.create_bondPlutoRunnerCore.applicableprimes@bindBase.getSlider$16b677e4-c467-462a-b770-b7a31160e129precedence_heuristic cell_id$16b677e4-c467-462a-b770-b7a31160e129downstream_cells_mapprime_list$4c2d45e3-56a2-467f-b87f-7b98cb873a05$191f8429-cbbb-44aa-8beb-271a94293e4bupstream_cells_mapprimes_upper$67093a35-8e1b-4cd3-b11b-c7ff601f802eprimes$6e5e3ec6-c96a-4a4a-bf4d-4b115f9b0d82precedence_heuristic cell_id$6e5e3ec6-c96a-4a4a-bf4d-4b115f9b0d82downstream_cells_mapcollision$7330af43-bec3-460c-94f6-768ac2975b00upstream_cells_mapDicteachindexhaskey=>$6332b2f2-ed2f-448a-b1df-247b110e335bprecedence_heuristic cell_id$6332b2f2-ed2f-448a-b1df-247b110e335bdownstream_cells_mapupstream_cells_map@md_strqagetindex$3c198d79-c46a-4781-8bd1-b6b68f06c31fprecedence_heuristic cell_id$3c198d79-c46a-4781-8bd1-b6b68f06c31fdownstream_cells_mapupstream_cells_map @timebigBase.GC_DiffBase.===Base.stringBase.time_printBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numfast_power$58da5ba4-c858-4684-a9f4-5a39fdc4fb03Base.cumulative_compile_time_nspower$2381babe-0777-45db-acff-cc647a8a68d3Base*Base.time_nsBase./$d830fffd-3781-40ca-85cb-c242f99667ceprecedence_heuristic cell_id$d830fffd-3781-40ca-85cb-c242f99667cedownstream_cells_mapfib_diag$ac5e1516-1574-4893-a965-f799947076cb$d882afdd-eb85-467c-bf18-525c0c5da5e7upstream_cells_map\-^*D$19ef447f-9fdf-49e1-8d1a-7860b4d4e9baE$b5f3620d-0942-41bb-80b0-d2ddcfe65090$8b16a522-9be4-4286-b64d-3d1bbdef7142precedence_heuristic cell_id$8b16a522-9be4-4286-b64d-3d1bbdef7142downstream_cells_mapupstream_cells_map@md_strgetindex$2c34c17e-12de-43ea-870c-818c97647836precedence_heuristic cell_id$2c34c17e-12de-43ea-870c-818c97647836downstream_cells_mapupstream_cells_mapframetitle$ca8905ef-97a3-424c-bb2e-559f7151585bprecedence_heuristic cell_id$ca8905ef-97a3-424c-bb2e-559f7151585bdownstream_cells_mapupstream_cells_map@md_strgetindex$97736c6a-3f5d-4978-8dd2-0a11c09ba9f0precedence_heuristic cell_id$97736c6a-3f5d-4978-8dd2-0a11c09ba9f0downstream_cells_mappgcd$fe2af566-4a8b-4052-9915-85266ee5ce98upstream_cells_mapmod==println$192f608c-0563-4179-903f-49fad2db4c74precedence_heuristic cell_id$192f608c-0563-4179-903f-49fad2db4c74downstream_cells_mapupstream_cells_map @timeBase.===Base.GC_DiffBase.stringBase.time_printfib_pow$38744170-9af6-44b5-a0be-46a83da3253eBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numBase.cumulative_compile_time_nsBaseBase.time_nsBase./$f39cccac-5b24-46e4-8749-1b0a944542efprecedence_heuristic cell_id$f39cccac-5b24-46e4-8749-1b0a944542efdownstream_cells_mapgcd_b$fe2af566-4a8b-4052-9915-85266ee5ce98$aee611f2-bc86-4e85-bbcb-add78c6a9175$40b8e474-16e0-4a61-bb28-11d90beefeea$eeaec4f4-71bd-43df-b9c9-a00bc3b1864bupstream_cells_map@md_strCorePlutoRunnerPlutoRunner.create_bondCore.applicablegetindex:Base.get@bindSlidertypemaxBaseInt32$909b8a36-79bb-4c1a-9dd7-4acaffc0434eprecedence_heuristic cell_id$909b8a36-79bb-4c1a-9dd7-4acaffc0434edownstream_cells_mapupstream_cells_mapframetitle$e1b5733f-a7a8-458f-a345-b358b9a03fcfprecedence_heuristic cell_id$e1b5733f-a7a8-458f-a345-b358b9a03fcfdownstream_cells_mapupstream_cells_map@md_strgetindex$d8a28762-8aab-49e9-b9ac-38901d34abffprecedence_heuristic cell_id$d8a28762-8aab-49e9-b9ac-38901d34abffdownstream_cells_mapupstream_cells_mapframetitle$64eb4b52-4946-467c-867a-a6fc437b15f6precedence_heuristic cell_id$64eb4b52-4946-467c-867a-a6fc437b15f6downstream_cells_mapupstream_cells_mapframetitle$6c3bca1a-3109-4e48-97e1-e0ed4599ffb2precedence_heuristic cell_id$6c3bca1a-3109-4e48-97e1-e0ed4599ffb2downstream_cells_mapupstream_cells_mapframetitle$a59a20e2-a7c7-48a9-ad8d-8094e03a749dprecedence_heuristic cell_id$a59a20e2-a7c7-48a9-ad8d-8094e03a749ddownstream_cells_mapupstream_cells_map:modmodinv$21df1900-3954-4506-b759-aeeee664d1dfcollect*$06679a09-47d7-4024-8232-4954c08747a0precedence_heuristiccell_id$06679a09-47d7-4024-8232-4954c08747a0downstream_cells_mapLinearAlgebraPlutoUIDataFramesPrimes$7f9bd301-355b-43f5-b168-22fac9e52511ColorsLuxor$8315b53f-abca-483d-bbf6-7e9193e751c9upstream_cells_map$58da5ba4-c858-4684-a9f4-5a39fdc4fb03precedence_heuristic cell_id$58da5ba4-c858-4684-a9f4-5a39fdc4fb03downstream_cells_mapfast_power$3c198d79-c46a-4781-8bd1-b6b68f06c31f$8670abc2-63e6-496a-b20c-812197acd9adupstream_cells_mapmod-divone==Function$a7afc0cb-a980-4f4f-b782-9791d932ee52precedence_heuristic cell_id$a7afc0cb-a980-4f4f-b782-9791d932ee52downstream_cells_mapupstream_cells_map@md_strcite$6c3595d2-4f68-44da-90e7-dc9c68479bcfgetindex$6ed7c73d-60da-4908-85cb-958745d81ebcprecedence_heuristic cell_id$6ed7c73d-60da-4908-85cb-958745d81ebcdownstream_cells_mapupstream_cells_map@md_strgetindex$bc9a718f-4b97-4e15-acf8-d180abc5b6d5precedence_heuristic cell_id$bc9a718f-4b97-4e15-acf8-d180abc5b6d5downstream_cells_mapupstream_cells_map@md_strcite$6c3595d2-4f68-44da-90e7-dc9c68479bcfqagetindex$ec14d629-b720-47cd-bc08-ff96f49271abprecedence_heuristic cell_id$ec14d629-b720-47cd-bc08-ff96f49271abdownstream_cells_mapdiscrete_log$9efb7a71-9a03-4716-8d34-aae233e9b898upstream_cells_map:mod-*one==$d1b260fb-7500-47fb-bb48-21b5857ab55aprecedence_heuristic cell_id$d1b260fb-7500-47fb-bb48-21b5857ab55adownstream_cells_mapupstream_cells_map@md_strgetindex$09f44611-ba21-4982-ba1b-0691124642fcprecedence_heuristic cell_id$09f44611-ba21-4982-ba1b-0691124642fcdownstream_cells_mapupstream_cells_mapframetitle$256c8009-4d2b-42f8-adaa-6f238ef22c6dprecedence_heuristic cell_id$256c8009-4d2b-42f8-adaa-6f238ef22c6ddownstream_cells_mapslider_n$4e35d650-b9a6-4668-90f0-f27a50af29adn$31388128-33a3-4443-835e-74b91bf48268$87fdefa1-3bbd-4b69-ad3a-72baca6e55ee$a1628317-7937-4316-85bf-2da860effce3$5c6c45b4-67e3-4ea8-bc09-0205ab24cbc3$4e35d650-b9a6-4668-90f0-f27a50af29adupstream_cells_mapCoreBase:PlutoRunner.create_bondPlutoRunnerCore.applicable@bindBase.getSlider$c5e906c8-0f73-4955-baa7-337195329e04precedence_heuristic cell_id$c5e906c8-0f73-4955-baa7-337195329e04downstream_cells_mapupstream_cells_map@md_strgetindex$08b18315-c28e-44ed-beb2-5b17421b0224precedence_heuristic cell_id$08b18315-c28e-44ed-beb2-5b17421b0224downstream_cells_mapupstream_cells_map@md_strgetindex$8670abc2-63e6-496a-b20c-812197acd9adprecedence_heuristic cell_id$8670abc2-63e6-496a-b20c-812197acd9addownstream_cells_mapfast_mod_power$77093b36-c232-4477-be49-845f1a631829$65f4990f-1952-4682-8fa8-9e3dd4bf1ebf$9cef898e-192c-418a-bec6-511f8b6da179$4c2d45e3-56a2-467f-b87f-7b98cb873a05$191f8429-cbbb-44aa-8beb-271a94293e4b$59ac02af-7b54-44d4-b5f4-a0f60d4458a1$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253$ce07d5c5-90a3-4c12-bada-30e4da1b99fd$ae89661a-2c0f-4752-adc2-023f09dc0e9f$4a98507b-653e-4354-a825-7605f8fcb31b$3026f9c5-81d3-443a-940a-f22fef9754af$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fdupstream_cells_mapmod*fast_power$58da5ba4-c858-4684-a9f4-5a39fdc4fb03$18031ccb-657f-409a-9080-9a0ada3ae8b5precedence_heuristic cell_id$18031ccb-657f-409a-9080-9a0ada3ae8b5downstream_cells_mapb$31388128-33a3-4443-835e-74b91bf48268$87fdefa1-3bbd-4b69-ad3a-72baca6e55ee$a1628317-7937-4316-85bf-2da860effce3$5c6c45b4-67e3-4ea8-bc09-0205ab24cbc3$4e35d650-b9a6-4668-90f0-f27a50af29adslider_b$4e35d650-b9a6-4668-90f0-f27a50af29adupstream_cells_mapCoreBase:PlutoRunner.create_bondPlutoRunnerCore.applicable@bindBase.getSlider$4714b7d7-32ee-42a1-bfa5-93eafda739d3precedence_heuristic cell_id$4714b7d7-32ee-42a1-bfa5-93eafda739d3downstream_cells_mapupstream_cells_mapframetitle$2cb5c6e0-b431-4d2e-b023-cd2131112ecaprecedence_heuristic cell_id$2cb5c6e0-b431-4d2e-b023-cd2131112ecadownstream_cells_mapupstream_cells_mapframetitle$b57adc77-3783-4958-91a0-e90782338755precedence_heuristic cell_id$b57adc77-3783-4958-91a0-e90782338755downstream_cells_mapslider_a$4e35d650-b9a6-4668-90f0-f27a50af29ada$31388128-33a3-4443-835e-74b91bf48268$87fdefa1-3bbd-4b69-ad3a-72baca6e55ee$a1628317-7937-4316-85bf-2da860effce3$5c6c45b4-67e3-4ea8-bc09-0205ab24cbc3$4e35d650-b9a6-4668-90f0-f27a50af29adupstream_cells_mapCoreBase:PlutoRunner.create_bondPlutoRunnerCore.applicable@bindBase.getSlider$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253precedence_heuristic cell_id$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253downstream_cells_mapupstream_cells_mapfast_mod_power$8670abc2-63e6-496a-b20c-812197acd9adg$0e3fb524-bea1-4ef0-9589-36230a84e949x$9efb7a71-9a03-4716-8d34-aae233e9b898p$57816e2c-a675-43e7-b674-2877ffcf1415$a41722b8-8c21-4d3c-a38b-4d248a79e80aprecedence_heuristic cell_id$a41722b8-8c21-4d3c-a38b-4d248a79e80adownstream_cells_mapupstream_cells_map@md_strgetindex$40b8e474-16e0-4a61-bb28-11d90beefeeaprecedence_heuristic cell_id$40b8e474-16e0-4a61-bb28-11d90beefeeadownstream_cells_mapupstream_cells_mapgcd_b$f39cccac-5b24-46e4-8749-1b0a944542efgcd_x$aee611f2-bc86-4e85-bbcb-add78c6a9175gcd_a$1a4da418-147f-46f4-9b95-7955183aa5cf+*gcd_y$aee611f2-bc86-4e85-bbcb-add78c6a9175$7da0705e-c925-4f8d-9ca4-8d8a0f859feaprecedence_heuristic cell_id$7da0705e-c925-4f8d-9ca4-8d8a0f859feadownstream_cells_mapupstream_cells_map@md_strgetindex$227e415e-ab17-4f3a-b695-9573c9ee2b57precedence_heuristic cell_id$227e415e-ab17-4f3a-b695-9573c9ee2b57downstream_cells_mapupstream_cells_map@md_strqagetindex$15367f3b-c7e4-4004-a018-5422a7f22024precedence_heuristic cell_id$15367f3b-c7e4-4004-a018-5422a7f22024downstream_cells_mapupstream_cells_map@md_strgetindex$594829e2-585b-4d48-bb6e-b35d9543cfbeprecedence_heuristic cell_id$594829e2-585b-4d48-bb6e-b35d9543cfbedownstream_cells_mapupstream_cells_mapframetitle$c3411941-d77f-46cb-8378-23998a1a4828precedence_heuristic cell_id$c3411941-d77f-46cb-8378-23998a1a4828downstream_cells_mapupstream_cells_mapframetitle$4e35d650-b9a6-4668-90f0-f27a50af29adprecedence_heuristic cell_id$4e35d650-b9a6-4668-90f0-f27a50af29addownstream_cells_mapabn_picker$d81bbd74-42df-4bb2-a045-9c2642cc19e5$4ef2c7e9-fb37-4e38-a252-b9c3f83d2a82upstream_cells_map@md_strn$256c8009-4d2b-42f8-adaa-6f238ef22c6dslider_a$b57adc77-3783-4958-91a0-e90782338755modb$18031ccb-657f-409a-9080-9a0ada3ae8b5slider_n$256c8009-4d2b-42f8-adaa-6f238ef22c6da$b57adc77-3783-4958-91a0-e90782338755slider_b$18031ccb-657f-409a-9080-9a0ada3ae8b5getindex$e52d25b3-65bf-4617-ae8d-fae0d0c8d041precedence_heuristic cell_id$e52d25b3-65bf-4617-ae8d-fae0d0c8d041downstream_cells_mapupstream_cells_map@md_strgetindex$bd0c0258-7040-42e7-a20e-532b55af3a62precedence_heuristic cell_id$bd0c0258-7040-42e7-a20e-532b55af3a62downstream_cells_mapupstream_cells_mapframetitle$191f8429-cbbb-44aa-8beb-271a94293e4bprecedence_heuristic cell_id$191f8429-cbbb-44aa-8beb-271a94293e4bdownstream_cells_mapupstream_cells_mapfast_mod_power$8670abc2-63e6-496a-b20c-812197acd9adchinese_remainder_theorem$821de132-559b-4420-b866-e97134c5bd9aprime_list$16b677e4-c467-462a-b770-b7a31160e129bigpower$2381babe-0777-45db-acff-cc647a8a68d3$e505716d-af01-455f-a55a-a9c225822ad5precedence_heuristic cell_id$e505716d-af01-455f-a55a-a9c225822ad5downstream_cells_mapupstream_cells_map@md_strgetindex$ed3d6ea6-08c9-45d0-8b77-3389a557bfd1precedence_heuristic cell_id$ed3d6ea6-08c9-45d0-8b77-3389a557bfd1downstream_cells_mapupstream_cells_map:modmodinv$21df1900-3954-4506-b759-aeeee664d1dfcollect*$642d545f-b1b9-49da-8a03-ad63e3214f59precedence_heuristic cell_id$642d545f-b1b9-49da-8a03-ad63e3214f59downstream_cells_mapupstream_cells_map@md_strgetindex$bafc9870-3823-4d1d-b0b7-94c69ee764d5precedence_heuristic cell_id$bafc9870-3823-4d1d-b0b7-94c69ee764d5downstream_cells_mapDocumenterCitationsupstream_cells_map$19ef447f-9fdf-49e1-8d1a-7860b4d4e9baprecedence_heuristic cell_id$19ef447f-9fdf-49e1-8d1a-7860b4d4e9badownstream_cells_mapD$d830fffd-3781-40ca-85cb-c242f99667ceupstream_cells_mapDiagonal-sqrt/√+big$7f9bd301-355b-43f5-b168-22fac9e52511precedence_heuristic cell_id$7f9bd301-355b-43f5-b168-22fac9e52511downstream_cells_mapupstream_cells_mapPrimes.primesPrimes$06679a09-47d7-4024-8232-4954c08747a0$d81bbd74-42df-4bb2-a045-9c2642cc19e5precedence_heuristic cell_id$d81bbd74-42df-4bb2-a045-9c2642cc19e5downstream_cells_mapupstream_cells_mapabn_picker$4e35d650-b9a6-4668-90f0-f27a50af29ad$1e27eedc-5308-4608-863f-fb81d60acdf0precedence_heuristic cell_id$1e27eedc-5308-4608-863f-fb81d60acdf0downstream_cells_mapupstream_cells_map@md_strqagetindex$ee43c389-55f4-4cf9-a8db-ce37d1b89db4precedence_heuristic cell_id$ee43c389-55f4-4cf9-a8db-ce37d1b89db4downstream_cells_mapupstream_cells_mapframetitle$f6e22fc3-382e-4548-bc59-8f944e06d237precedence_heuristic cell_id$f6e22fc3-382e-4548-bc59-8f944e06d237downstream_cells_mapupstream_cells_mapDiagonal*E$b5f3620d-0942-41bb-80b0-d2ddcfe65090inv$8315b53f-abca-483d-bbf6-7e9193e751c9precedence_heuristic cell_id$8315b53f-abca-483d-bbf6-7e9193e751c9downstream_cells_mapdraw_fib$708c442b-cbff-4e1a-b70d-e704453cfd3dupstream_cells_map Luxor.Drawingstringsumisoddislessmodmin/@drawLuxor.originLuxor$06679a09-47d7-4024-8232-4954c08747a0==distinguishable_colors:rectdivendfontsizeLuxor.finishLuxor.backgroundsetopacitypush!Point-Luxor.sethue+*isevenLuxor.previewtextsethuemaximum$3026f9c5-81d3-443a-940a-f22fef9754afprecedence_heuristic cell_id$3026f9c5-81d3-443a-940a-f22fef9754afdownstream_cells_mapgiant_steps$7330af43-bec3-460c-94f6-768ac2975b00upstream_cells_mapfast_mod_power$8670abc2-63e6-496a-b20c-812197acd9admodinv$21df1900-3954-4506-b759-aeeee664d1dfbaby_steps$4853f4ef-fbb8-48c3-9523-13ab4969d097$87fdefa1-3bbd-4b69-ad3a-72baca6e55eeprecedence_heuristic cell_id$87fdefa1-3bbd-4b69-ad3a-72baca6e55eedownstream_cells_mapupstream_cells_mapmodb$18031ccb-657f-409a-9080-9a0ada3ae8b5+a$b57adc77-3783-4958-91a0-e90782338755n$256c8009-4d2b-42f8-adaa-6f238ef22c6d$0ee6972c-5069-4ba0-887f-be64c7d000d0precedence_heuristic cell_id$0ee6972c-5069-4ba0-887f-be64c7d000d0downstream_cells_mapupstream_cells_mapframetitle$592ae01b-2819-402d-9538-17018df5c34bprecedence_heuristic cell_id$592ae01b-2819-402d-9538-17018df5c34bdownstream_cells_mapupstream_cells_mapframetitle$59817f59-429b-4f17-a46a-185571fd1e5aprecedence_heuristic cell_id$59817f59-429b-4f17-a46a-185571fd1e5adownstream_cells_mapupstream_cells_mapframetitle$a4698418-ebf7-4992-a3ba-a15ff282bf87precedence_heuristic cell_id$a4698418-ebf7-4992-a3ba-a15ff282bf87downstream_cells_mapupstream_cells_map@md_strqagetindex$3da58487-192f-458a-9d47-7a4ce98b6da3precedence_heuristic cell_id$3da58487-192f-458a-9d47-7a4ce98b6da3downstream_cells_mapupstream_cells_mapsection$736307ec-a2a4-11ef-0f85-ad1a0093e06aprecedence_heuristic cell_id$736307ec-a2a4-11ef-0f85-ad1a0093e06adownstream_cells_mapupstream_cells_map@md_strgetindex$9207b107-e1b0-4328-a004-f4b8152b423fprecedence_heuristic cell_id$9207b107-e1b0-4328-a004-f4b8152b423fdownstream_cells_mapupstream_cells_map@md_strqagetindex$65f4990f-1952-4682-8fa8-9e3dd4bf1ebfprecedence_heuristic cell_id$65f4990f-1952-4682-8fa8-9e3dd4bf1ebfdownstream_cells_mappow_999$6f10de7b-ce05-4f82-82e7-4110be44e8cc$ec25ce2a-de8a-4b69-a3f3-b47cd58ec986upstream_cells_map @timefast_mod_power$8670abc2-63e6-496a-b20c-812197acd9adBase.===Base.GC_DiffBase.stringBase.time_printBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numpower$2381babe-0777-45db-acff-cc647a8a68d3Base.cumulative_compile_time_nsBaseBase.time_nsBase./$1b2245f8-2f02-4c4d-b6d2-e65af1f2a21eprecedence_heuristic cell_id$1b2245f8-2f02-4c4d-b6d2-e65af1f2a21edownstream_cells_mapupstream_cells_map@md_strgetindex$eeaec4f4-71bd-43df-b9c9-a00bc3b1864bprecedence_heuristic cell_id$eeaec4f4-71bd-43df-b9c9-a00bc3b1864bdownstream_cells_mapupstream_cells_mapgcdxgcd_b$f39cccac-5b24-46e4-8749-1b0a944542efgcd_a$1a4da418-147f-46f4-9b95-7955183aa5cf$ba16d83d-21a5-4f0c-807b-674a167da4dcprecedence_heuristic cell_id$ba16d83d-21a5-4f0c-807b-674a167da4dcdownstream_cells_mapbiblio$6c3595d2-4f68-44da-90e7-dc9c68479bcf$8a5a251f-5373-445a-97b1-4d652c6b7ba8upstream_cells_mapload_biblio!$7bad8c6c-45c7-402f-ad59-6857e9268901precedence_heuristic cell_id$7bad8c6c-45c7-402f-ad59-6857e9268901downstream_cells_mapupstream_cells_map@md_strqagetindex$21df1900-3954-4506-b759-aeeee664d1dfprecedence_heuristic cell_id$21df1900-3954-4506-b759-aeeee664d1dfdownstream_cells_mapmodinv$93aa2719-f962-497b-9fda-30f54fd848eb$a59a20e2-a7c7-48a9-ad8d-8094e03a749d$ed3d6ea6-08c9-45d0-8b77-3389a557bfd1$6f10de7b-ce05-4f82-82e7-4110be44e8cc$821de132-559b-4420-b866-e97134c5bd9a$3026f9c5-81d3-443a-940a-f22fef9754afupstream_cells_mapgcdxmod$1072a756-5026-4de9-93a8-f942d54c474aprecedence_heuristic cell_id$1072a756-5026-4de9-93a8-f942d54c474adownstream_cells_mapupstream_cells_map@md_strcite$6c3595d2-4f68-44da-90e7-dc9c68479bcfgetindex$59254bfd-48f2-4585-9ba5-e4c809421072precedence_heuristic cell_id$59254bfd-48f2-4585-9ba5-e4c809421072downstream_cells_mapshanks_x$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fdupstream_cells_mapg$0e3fb524-bea1-4ef0-9589-36230a84e949shanks_discrete_log$7330af43-bec3-460c-94f6-768ac2975b00p$57816e2c-a675-43e7-b674-2877ffcf1415$f4f49568-dcf2-4c76-ba66-065d2fda7a4aprecedence_heuristic cell_id$f4f49568-dcf2-4c76-ba66-065d2fda7a4adownstream_cells_mapupstream_cells_map@md_strgetindex$9752afbb-96e6-4f96-92cb-09654cf46155precedence_heuristic cell_id$9752afbb-96e6-4f96-92cb-09654cf46155downstream_cells_mapupstream_cells_map@md_strqagetindex$e2a3842d-4e07-4703-ab47-a5140649dd6aprecedence_heuristic cell_id$e2a3842d-4e07-4703-ab47-a5140649dd6adownstream_cells_mapupstream_cells_mapuniquesortall_powers$59ac02af-7b54-44d4-b5f4-a0f60d4458a1$cbabee34-2ca2-4ad4-93ba-2ec3c941da5eprecedence_heuristic cell_id$cbabee34-2ca2-4ad4-93ba-2ec3c941da5edownstream_cells_mapupstream_cells_map@md_strgetindex$059b0ada-2442-48e4-82dd-489cb97e5dccprecedence_heuristic cell_id$059b0ada-2442-48e4-82dd-489cb97e5dccdownstream_cells_mapupstream_cells_mapgp_picker$0e3fb524-bea1-4ef0-9589-36230a84e949$027fe67c-d2f0-49f6-b894-959795551d27precedence_heuristic cell_id$027fe67c-d2f0-49f6-b894-959795551d27downstream_cells_mapupstream_cells_map @timeBase.===Base.GC_DiffBase.stringBase.time_printfib_rec$72ec8410-05d9-475a-93d4-47153cc0ce31Base.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numBase.cumulative_compile_time_nsBaseBase.time_nsBase./$83852dd5-3546-45af-a845-b01dab0aa2a6precedence_heuristic cell_id$83852dd5-3546-45af-a845-b01dab0aa2a6downstream_cells_mapupstream_cells_mapframetitle$3df688c8-1c52-462d-88be-daa153333c60precedence_heuristic cell_id$3df688c8-1c52-462d-88be-daa153333c60downstream_cells_mapupstream_cells_map@md_strcite$6c3595d2-4f68-44da-90e7-dc9c68479bcfgetindex$e9633e3f-376d-413d-bc19-d015f6ce76e5precedence_heuristic cell_id$e9633e3f-376d-413d-bc19-d015f6ce76e5downstream_cells_mapupstream_cells_map^power$2381babe-0777-45db-acff-cc647a8a68d3big$819f15ef-31d0-44b6-837a-e3e67f2667b9precedence_heuristic cell_id$819f15ef-31d0-44b6-837a-e3e67f2667b9downstream_cells_mapupstream_cells_map@md_strgetindex$3f1af973-a02b-4e06-8e6e-eff414fcaf67precedence_heuristic cell_id$3f1af973-a02b-4e06-8e6e-eff414fcaf67downstream_cells_mappgcdx$aee611f2-bc86-4e85-bbcb-add78c6a9175upstream_cells_mapzero-divrem*one==$4853f4ef-fbb8-48c3-9523-13ab4969d097precedence_heuristic cell_id$4853f4ef-fbb8-48c3-9523-13ab4969d097downstream_cells_mapbaby_steps$3026f9c5-81d3-443a-940a-f22fef9754af$7330af43-bec3-460c-94f6-768ac2975b00upstream_cells_map:modpush!*oneend$9722971a-16f1-4f28-ba31-c12b673b8a30precedence_heuristic cell_id$9722971a-16f1-4f28-ba31-c12b673b8a30downstream_cells_mapupstream_cells_map@md_strgetindex$462fa407-d973-4e9e-8512-b7cd3bb98b7bprecedence_heuristic cell_id$462fa407-d973-4e9e-8512-b7cd3bb98b7bdownstream_cells_mapfib_seq$3cd40d9e-fcea-427d-9877-cea65e7ea413upstream_cells_mapBigInt:-zeros+end$6e59ee60-ef73-45ca-86eb-4d8a44c73771precedence_heuristic cell_id$6e59ee60-ef73-45ca-86eb-4d8a44c73771downstream_cells_mapupstream_cells_map@md_strqagetindex$9efb7a71-9a03-4716-8d34-aae233e9b898precedence_heuristic cell_id$9efb7a71-9a03-4716-8d34-aae233e9b898downstream_cells_mapx$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253upstream_cells_mapg$0e3fb524-bea1-4ef0-9589-36230a84e949discrete_log$ec14d629-b720-47cd-bc08-ff96f49271abp$57816e2c-a675-43e7-b674-2877ffcf1415$9b9fc5e6-1a41-43c5-ba43-2c93bc3ef66bprecedence_heuristic cell_id$9b9fc5e6-1a41-43c5-ba43-2c93bc3ef66bdownstream_cells_mapupstream_cells_map @timeBase.===Base.GC_DiffBase.stringBase.time_printBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numBase.cumulative_compile_time_nsBasefib_closed$535f4bc1-e88c-47c7-990b-e3c8b5054accBase.time_nsBase./$9cef898e-192c-418a-bec6-511f8b6da179precedence_heuristic cell_id$9cef898e-192c-418a-bec6-511f8b6da179downstream_cells_mapupstream_cells_mapfast_mod_power$8670abc2-63e6-496a-b20c-812197acd9adpower$2381babe-0777-45db-acff-cc647a8a68d3$78df9410-5ea4-4d9f-bbe5-862f76a100fcprecedence_heuristic cell_id$78df9410-5ea4-4d9f-bbe5-862f76a100fcdownstream_cells_mapupstream_cells_map@md_strgetindex$31388128-33a3-4443-835e-74b91bf48268precedence_heuristic cell_id$31388128-33a3-4443-835e-74b91bf48268downstream_cells_mapupstream_cells_mapmodb$18031ccb-657f-409a-9080-9a0ada3ae8b5+a$b57adc77-3783-4958-91a0-e90782338755n$256c8009-4d2b-42f8-adaa-6f238ef22c6d$3cd40d9e-fcea-427d-9877-cea65e7ea413precedence_heuristic cell_id$3cd40d9e-fcea-427d-9877-cea65e7ea413downstream_cells_mapupstream_cells_map @timeBase.===Base.GC_DiffBase.stringBase.time_printBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-fib_seq$462fa407-d973-4e9e-8512-b7cd3bb98b7bBase.gc_numBase.cumulative_compile_time_nsBaseBase.time_nsBase./$7881bb75-3ef9-496e-860b-03ced6b593c5precedence_heuristic cell_id$7881bb75-3ef9-496e-860b-03ced6b593c5downstream_cells_mapupstream_cells_map @timebigBase.GC_DiffBase.===Base.string^Base.time_printBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numpower$2381babe-0777-45db-acff-cc647a8a68d3Base.cumulative_compile_time_nsBaseBase.time_nsBase./$72ec8410-05d9-475a-93d4-47153cc0ce31precedence_heuristic cell_id$72ec8410-05d9-475a-93d4-47153cc0ce31downstream_cells_mapfib_rec$027fe67c-d2f0-49f6-b894-959795551d27upstream_cells_map-+==$41cf9efd-65e5-4abb-94d3-e824780e659cprecedence_heuristic cell_id$41cf9efd-65e5-4abb-94d3-e824780e659cdownstream_cells_mapupstream_cells_maprefs$8a5a251f-5373-445a-97b1-4d652c6b7ba8$6cf004be-5205-429e-8131-ef607cebeaecprecedence_heuristic cell_id$6cf004be-5205-429e-8131-ef607cebeaecdownstream_cells_mapupstream_cells_mapE$b5f3620d-0942-41bb-80b0-d2ddcfe65090$8f6ba1c4-a971-4dc4-ac5d-2f30790aecdeprecedence_heuristic cell_id$8f6ba1c4-a971-4dc4-ac5d-2f30790aecdedownstream_cells_mapupstream_cells_mapframetitle$fe2af566-4a8b-4052-9915-85266ee5ce98precedence_heuristic cell_id$fe2af566-4a8b-4052-9915-85266ee5ce98downstream_cells_mapupstream_cells_mappgcd$97736c6a-3f5d-4978-8dd2-0a11c09ba9f0gcd_b$f39cccac-5b24-46e4-8749-1b0a944542efgcd_a$1a4da418-147f-46f4-9b95-7955183aa5cf$8a5a251f-5373-445a-97b1-4d652c6b7ba8precedence_heuristic cell_id$8a5a251f-5373-445a-97b1-4d652c6b7ba8downstream_cells_maprefs$41cf9efd-65e5-4abb-94d3-e824780e659cupstream_cells_mapbibrefsbiblio$ba16d83d-21a5-4f0c-807b-674a167da4dc$708c442b-cbff-4e1a-b70d-e704453cfd3dprecedence_heuristic cell_id$708c442b-cbff-4e1a-b70d-e704453cfd3ddownstream_cells_mapupstream_cells_map@md_strfib_n$0c8ab02e-80b0-44d6-a4a8-c813aac38209draw_fib$8315b53f-abca-483d-bbf6-7e9193e751c9HAlignfib_picker$0c8ab02e-80b0-44d6-a4a8-c813aac38209getindex$1a4da418-147f-46f4-9b95-7955183aa5cfprecedence_heuristic cell_id$1a4da418-147f-46f4-9b95-7955183aa5cfdownstream_cells_mapgcd_a$fe2af566-4a8b-4052-9915-85266ee5ce98$aee611f2-bc86-4e85-bbcb-add78c6a9175$40b8e474-16e0-4a61-bb28-11d90beefeea$eeaec4f4-71bd-43df-b9c9-a00bc3b1864bupstream_cells_map@md_strCorePlutoRunnerPlutoRunner.create_bondCore.applicablegetindex:Base.get@bindSlidertypemaxBaseInt32$ed023033-1044-4d48-aab1-39e9300043f7precedence_heuristic cell_id$ed023033-1044-4d48-aab1-39e9300043f7downstream_cells_mapupstream_cells_map@md_strcite$6c3595d2-4f68-44da-90e7-dc9c68479bcfgetindex$eb311761-ace2-4632-9ebf-9c7c166659f7precedence_heuristic cell_id$eb311761-ace2-4632-9ebf-9c7c166659f7downstream_cells_mapupstream_cells_map@md_strgetindex$f86a5efc-d31e-4e88-b81f-ebdbbeba11ecprecedence_heuristic cell_id$f86a5efc-d31e-4e88-b81f-ebdbbeba11ecdownstream_cells_mapupstream_cells_map@md_strgetindex$a7d9703a-5121-4b43-8cd4-2acf9a0d91efprecedence_heuristic cell_id$a7d9703a-5121-4b43-8cd4-2acf9a0d91efdownstream_cells_mapupstream_cells_map@md_strgetindex$9e8a61d9-a700-4851-b1cd-49ce042c3530precedence_heuristic cell_id$9e8a61d9-a700-4851-b1cd-49ce042c3530downstream_cells_mapupstream_cells_map @timebigBase.GC_DiffBase.===Base.string^Base.time_printBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numpower$2381babe-0777-45db-acff-cc647a8a68d3Base.cumulative_compile_time_nsBaseBase.time_nsBase./$c376513c-6553-4cd6-8384-ae6ff9d472d7precedence_heuristic cell_id$c376513c-6553-4cd6-8384-ae6ff9d472d7downstream_cells_mapupstream_cells_map@md_strgetindex$38744170-9af6-44b5-a0be-46a83da3253eprecedence_heuristic cell_id$38744170-9af6-44b5-a0be-46a83da3253edownstream_cells_mapfib_pow$a1081bb2-2186-4b19-b667-0c246155f360$4cb070de-e8bf-4a1d-9625-043c19466c46$192f608c-0563-4179-903f-49fad2db4c74upstream_cells_mapBigInt-^*$a1081bb2-2186-4b19-b667-0c246155f360precedence_heuristic cell_id$a1081bb2-2186-4b19-b667-0c246155f360downstream_cells_mapupstream_cells_map @timeBase.===Base.GC_DiffBase.stringBase.time_printfib_pow$38744170-9af6-44b5-a0be-46a83da3253eBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numBase.cumulative_compile_time_nsBaseBase.time_nsBase./$4ef2c7e9-fb37-4e38-a252-b9c3f83d2a82precedence_heuristic cell_id$4ef2c7e9-fb37-4e38-a252-b9c3f83d2a82downstream_cells_mapupstream_cells_mapabn_picker$4e35d650-b9a6-4668-90f0-f27a50af29ad$93aa2719-f962-497b-9fda-30f54fd848ebprecedence_heuristic cell_id$93aa2719-f962-497b-9fda-30f54fd848ebdownstream_cells_mapupstream_cells_map:modmodinv$21df1900-3954-4506-b759-aeeee664d1dfcollect*$77093b36-c232-4477-be49-845f1a631829precedence_heuristic cell_id$77093b36-c232-4477-be49-845f1a631829downstream_cells_mappow_1000$6f10de7b-ce05-4f82-82e7-4110be44e8cc$ec25ce2a-de8a-4b69-a3f3-b47cd58ec986upstream_cells_map @timefast_mod_power$8670abc2-63e6-496a-b20c-812197acd9adBase.===Base.GC_DiffBase.stringBase.time_printBase.Threads.lock_profilingBase.cumulative_compile_timingBase.gc_alloc_countBase.*Base.-Base.gc_numpower$2381babe-0777-45db-acff-cc647a8a68d3Base.cumulative_compile_time_nsBaseBase.time_nsBase./$d6b89fda-308f-43da-8028-1a812b4516cfprecedence_heuristic cell_id$d6b89fda-308f-43da-8028-1a812b4516cfdownstream_cells_mapupstream_cells_map@md_strqagetindexcell_execution_order $06679a09-47d7-4024-8232-4954c08747a0$1b1d5c9b-5fc7-480e-9649-e9c44a49c38d$736307ec-a2a4-11ef-0f85-ad1a0093e06a$bbc907b1-63f8-435a-badc-11ed88bd6cf5$cbabee34-2ca2-4ad4-93ba-2ec3c941da5e$909b8a36-79bb-4c1a-9dd7-4acaffc0434e$08b18315-c28e-44ed-beb2-5b17421b0224$7bad8c6c-45c7-402f-ad59-6857e9268901$cd481f6c-66f4-4ebf-9769-c3edc24f403b$37585789-bd43-4ce5-b550-ad712b70d226$6e59ee60-ef73-45ca-86eb-4d8a44c73771$d6b89fda-308f-43da-8028-1a812b4516cf$d1b260fb-7500-47fb-bb48-21b5857ab55a$9207b107-e1b0-4328-a004-f4b8152b423f$48eba223-6cce-4aa2-9977-4883ba7903fc$bd0c0258-7040-42e7-a20e-532b55af3a62$97736c6a-3f5d-4978-8dd2-0a11c09ba9f0$1a4da418-147f-46f4-9b95-7955183aa5cf$f39cccac-5b24-46e4-8749-1b0a944542ef$fe2af566-4a8b-4052-9915-85266ee5ce98$03e49669-cdee-4241-862d-33ee91214455$0ee6972c-5069-4ba0-887f-be64c7d000d0$f4f49568-dcf2-4c76-ba66-065d2fda7a4a$09f44611-ba21-4982-ba1b-0691124642fc$642d545f-b1b9-49da-8a03-ad63e3214f59$7db2060b-d69e-42e7-ae81-fd37ee793876$c3411941-d77f-46cb-8378-23998a1a4828$a826d9d1-47db-4645-be6e-3ae0ed8d4e18$83852dd5-3546-45af-a845-b01dab0aa2a6$e1aafab7-c4f3-45ac-81ee-7f875ac7c8c6$9752afbb-96e6-4f96-92cb-09654cf46155$a7985d16-500b-4024-aaa1-78e654b94be4$2cb5c6e0-b431-4d2e-b023-cd2131112eca$b319619e-8f8d-4650-8fb4-76e5ba953470$3f1af973-a02b-4e06-8e6e-eff414fcaf67$aee611f2-bc86-4e85-bbcb-add78c6a9175$40b8e474-16e0-4a61-bb28-11d90beefeea$a41722b8-8c21-4d3c-a38b-4d248a79e80a$eeaec4f4-71bd-43df-b9c9-a00bc3b1864b$2c34c17e-12de-43ea-870c-818c97647836$ca8905ef-97a3-424c-bb2e-559f7151585b$21df1900-3954-4506-b759-aeeee664d1df$819f15ef-31d0-44b6-837a-e3e67f2667b9$78df9410-5ea4-4d9f-bbe5-862f76a100fc$93aa2719-f962-497b-9fda-30f54fd848eb$7da0705e-c925-4f8d-9ca4-8d8a0f859fea$a59a20e2-a7c7-48a9-ad8d-8094e03a749d$e52d25b3-65bf-4617-ae8d-fae0d0c8d041$ed3d6ea6-08c9-45d0-8b77-3389a557bfd1$bbb2793a-faa4-43bd-b2e8-e8d3ac93310f$f9f03579-5bfc-452d-bff9-9e7adfe095d3$d8a28762-8aab-49e9-b9ac-38901d34abff$e505716d-af01-455f-a55a-a9c225822ad5$a7d06375-e4dd-47b1-8aba-11dc4d62954b$6332b2f2-ed2f-448a-b1df-247b110e335b$6107d03d-1e45-4eb9-b8e2-51e4a72485e6$58da5ba4-c858-4684-a9f4-5a39fdc4fb03$a4698418-ebf7-4992-a3ba-a15ff282bf87$59817f59-429b-4f17-a46a-185571fd1e5a$8670abc2-63e6-496a-b20c-812197acd9ad$1b2245f8-2f02-4c4d-b6d2-e65af1f2a21e$9722971a-16f1-4f28-ba31-c12b673b8a30$6ed7c73d-60da-4908-85cb-958745d81ebc$9d4858f8-e63d-46e0-a6cc-992d3cc4a9a4$c2fab245-8a98-4b41-ade2-c5b16e9c39f9$821de132-559b-4420-b866-e97134c5bd9a$67093a35-8e1b-4cd3-b11b-c7ff601f802e$16b677e4-c467-462a-b770-b7a31160e129$61462af5-69bd-42be-8918-7992c79ee00d$592ae01b-2819-402d-9538-17018df5c34b$594829e2-585b-4d48-bb6e-b35d9543cfbe$72ec8410-05d9-475a-93d4-47153cc0ce31$027fe67c-d2f0-49f6-b894-959795551d27$462fa407-d973-4e9e-8512-b7cd3bb98b7b$3cd40d9e-fcea-427d-9877-cea65e7ea413$38744170-9af6-44b5-a0be-46a83da3253e$a1081bb2-2186-4b19-b667-0c246155f360$4714b7d7-32ee-42a1-bfa5-93eafda739d3$b5f3620d-0942-41bb-80b0-d2ddcfe65090$19ef447f-9fdf-49e1-8d1a-7860b4d4e9ba$6cf004be-5205-429e-8131-ef607cebeaec$f6e22fc3-382e-4548-bc59-8f944e06d237$d830fffd-3781-40ca-85cb-c242f99667ce$ac5e1516-1574-4893-a965-f799947076cb$4cb070de-e8bf-4a1d-9625-043c19466c46$6c3bca1a-3109-4e48-97e1-e0ed4599ffb2$1ca71c26-f98c-4126-a1c5-98786fde7e9b$535f4bc1-e88c-47c7-990b-e3c8b5054acc$9b9fc5e6-1a41-43c5-ba43-2c93bc3ef66b$d882afdd-eb85-467c-bf18-525c0c5da5e7$192f608c-0563-4179-903f-49fad2db4c74$8f6ba1c4-a971-4dc4-ac5d-2f30790aecde$bc58ba24-90f0-4913-8f66-10bb6cb54076$82ba8fe1-435e-422b-abb7-cb50a7a85e1e$8b16a522-9be4-4286-b64d-3d1bbdef7142$ec14d629-b720-47cd-bc08-ff96f49271ab$64eb4b52-4946-467c-867a-a6fc437b15f6$a7d9703a-5121-4b43-8cd4-2acf9a0d91ef$15367f3b-c7e4-4004-a018-5422a7f22024$e1b5733f-a7a8-458f-a345-b358b9a03fcf$f86a5efc-d31e-4e88-b81f-ebdbbeba11ec$ee43c389-55f4-4cf9-a8db-ce37d1b89db4$4853f4ef-fbb8-48c3-9523-13ab4969d097$3026f9c5-81d3-443a-940a-f22fef9754af$6e5e3ec6-c96a-4a4a-bf4d-4b115f9b0d82$7330af43-bec3-460c-94f6-768ac2975b00$1e27eedc-5308-4608-863f-fb81d60acdf0$a293bb0e-078d-4335-a446-3096a79c03bc$c5e906c8-0f73-4955-baa7-337195329e04$c376513c-6553-4cd6-8384-ae6ff9d472d7$eb311761-ace2-4632-9ebf-9c7c166659f7$227e415e-ab17-4f3a-b695-9573c9ee2b57$3da58487-192f-458a-9d47-7a4ce98b6da3$7f9bd301-355b-43f5-b168-22fac9e52511$bafc9870-3823-4d1d-b0b7-94c69ee764d5$b57adc77-3783-4958-91a0-e90782338755$18031ccb-657f-409a-9080-9a0ada3ae8b5$256c8009-4d2b-42f8-adaa-6f238ef22c6d$31388128-33a3-4443-835e-74b91bf48268$87fdefa1-3bbd-4b69-ad3a-72baca6e55ee$a1628317-7937-4316-85bf-2da860effce3$5c6c45b4-67e3-4ea8-bc09-0205ab24cbc3$4e35d650-b9a6-4668-90f0-f27a50af29ad$d81bbd74-42df-4bb2-a045-9c2642cc19e5$4ef2c7e9-fb37-4e38-a252-b9c3f83d2a82$2381babe-0777-45db-acff-cc647a8a68d3$c8f85081-3659-4796-8550-2e708b09c8d7$7881bb75-3ef9-496e-860b-03ced6b593c5$087cbe82-b42a-4f80-a1af-97f3aa93aeeb$9e8a61d9-a700-4851-b1cd-49ce042c3530$3c198d79-c46a-4781-8bd1-b6b68f06c31f$77093b36-c232-4477-be49-845f1a631829$65f4990f-1952-4682-8fa8-9e3dd4bf1ebf$6f10de7b-ce05-4f82-82e7-4110be44e8cc$ec25ce2a-de8a-4b69-a3f3-b47cd58ec986$9cef898e-192c-418a-bec6-511f8b6da179$4c2d45e3-56a2-467f-b87f-7b98cb873a05$191f8429-cbbb-44aa-8beb-271a94293e4b$e9633e3f-376d-413d-bc19-d015f6ce76e5$8315b53f-abca-483d-bbf6-7e9193e751c9$0c8ab02e-80b0-44d6-a4a8-c813aac38209$708c442b-cbff-4e1a-b70d-e704453cfd3d$57816e2c-a675-43e7-b674-2877ffcf1415$0e3fb524-bea1-4ef0-9589-36230a84e949$4cff1d10-422f-4b12-b790-a589c972fbb7$59ac02af-7b54-44d4-b5f4-a0f60d4458a1$9f55cad1-b01a-45e3-93df-a4349e2dfbd3$e2a3842d-4e07-4703-ab47-a5140649dd6a$08dcbbd3-a531-4f74-a724-1cae8fae1636$059b0ada-2442-48e4-82dd-489cb97e5dcc$4be6cea4-13a2-4bcb-b849-14eef57ab604$9efb7a71-9a03-4716-8d34-aae233e9b898$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253$ce07d5c5-90a3-4c12-bada-30e4da1b99fd$ae89661a-2c0f-4752-adc2-023f09dc0e9f$4a98507b-653e-4354-a825-7605f8fcb31b$59254bfd-48f2-4585-9ba5-e4c809421072$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fd$ba16d83d-21a5-4f0c-807b-674a167da4dc$6c3595d2-4f68-44da-90e7-dc9c68479bcf$3df688c8-1c52-462d-88be-daa153333c60$a7afc0cb-a980-4f4f-b782-9791d932ee52$ed023033-1044-4d48-aab1-39e9300043f7$bcf73ad7-a08b-4cbb-bcd2-d0abc002e7e2$bc9a718f-4b97-4e15-acf8-d180abc5b6d5$1072a756-5026-4de9-93a8-f942d54c474a$35b7b8b7-bff6-4f64-91b9-b65035162365$8a5a251f-5373-445a-97b1-4d652c6b7ba8$41cf9efd-65e5-4abb-94d3-e824780e659clast_hot_reload_time process_statusreadypath:/home/runner/work/LSINC1113/LSINC1113/Lectures/2_number.jlpluto_versionv0.20.21cell_order $736307ec-a2a4-11ef-0f85-ad1a0093e06a$3df688c8-1c52-462d-88be-daa153333c60$41cf9efd-65e5-4abb-94d3-e824780e659c$bbc907b1-63f8-435a-badc-11ed88bd6cf5$cbabee34-2ca2-4ad4-93ba-2ec3c941da5e$909b8a36-79bb-4c1a-9dd7-4acaffc0434e$08b18315-c28e-44ed-beb2-5b17421b0224$7bad8c6c-45c7-402f-ad59-6857e9268901$cd481f6c-66f4-4ebf-9769-c3edc24f403b$37585789-bd43-4ce5-b550-ad712b70d226$6e59ee60-ef73-45ca-86eb-4d8a44c73771$d6b89fda-308f-43da-8028-1a812b4516cf$d1b260fb-7500-47fb-bb48-21b5857ab55a$9207b107-e1b0-4328-a004-f4b8152b423f$48eba223-6cce-4aa2-9977-4883ba7903fc$bd0c0258-7040-42e7-a20e-532b55af3a62$97736c6a-3f5d-4978-8dd2-0a11c09ba9f0$1a4da418-147f-46f4-9b95-7955183aa5cf$f39cccac-5b24-46e4-8749-1b0a944542ef$fe2af566-4a8b-4052-9915-85266ee5ce98$03e49669-cdee-4241-862d-33ee91214455$0ee6972c-5069-4ba0-887f-be64c7d000d0$f4f49568-dcf2-4c76-ba66-065d2fda7a4a$d81bbd74-42df-4bb2-a045-9c2642cc19e5$31388128-33a3-4443-835e-74b91bf48268$87fdefa1-3bbd-4b69-ad3a-72baca6e55ee$09f44611-ba21-4982-ba1b-0691124642fc$642d545f-b1b9-49da-8a03-ad63e3214f59$4ef2c7e9-fb37-4e38-a252-b9c3f83d2a82$a1628317-7937-4316-85bf-2da860effce3$5c6c45b4-67e3-4ea8-bc09-0205ab24cbc3$7db2060b-d69e-42e7-ae81-fd37ee793876$c3411941-d77f-46cb-8378-23998a1a4828$a826d9d1-47db-4645-be6e-3ae0ed8d4e18$83852dd5-3546-45af-a845-b01dab0aa2a6$e1aafab7-c4f3-45ac-81ee-7f875ac7c8c6$9752afbb-96e6-4f96-92cb-09654cf46155$a7985d16-500b-4024-aaa1-78e654b94be4$2cb5c6e0-b431-4d2e-b023-cd2131112eca$b319619e-8f8d-4650-8fb4-76e5ba953470$3f1af973-a02b-4e06-8e6e-eff414fcaf67$aee611f2-bc86-4e85-bbcb-add78c6a9175$40b8e474-16e0-4a61-bb28-11d90beefeea$a41722b8-8c21-4d3c-a38b-4d248a79e80a$eeaec4f4-71bd-43df-b9c9-a00bc3b1864b$2c34c17e-12de-43ea-870c-818c97647836$ca8905ef-97a3-424c-bb2e-559f7151585b$21df1900-3954-4506-b759-aeeee664d1df$819f15ef-31d0-44b6-837a-e3e67f2667b9$78df9410-5ea4-4d9f-bbe5-862f76a100fc$93aa2719-f962-497b-9fda-30f54fd848eb$7da0705e-c925-4f8d-9ca4-8d8a0f859fea$a59a20e2-a7c7-48a9-ad8d-8094e03a749d$e52d25b3-65bf-4617-ae8d-fae0d0c8d041$ed3d6ea6-08c9-45d0-8b77-3389a557bfd1$bbb2793a-faa4-43bd-b2e8-e8d3ac93310f$f9f03579-5bfc-452d-bff9-9e7adfe095d3$d8a28762-8aab-49e9-b9ac-38901d34abff$e505716d-af01-455f-a55a-a9c225822ad5$c8f85081-3659-4796-8550-2e708b09c8d7$7881bb75-3ef9-496e-860b-03ced6b593c5$a7d06375-e4dd-47b1-8aba-11dc4d62954b$6332b2f2-ed2f-448a-b1df-247b110e335b$6107d03d-1e45-4eb9-b8e2-51e4a72485e6$58da5ba4-c858-4684-a9f4-5a39fdc4fb03$087cbe82-b42a-4f80-a1af-97f3aa93aeeb$9e8a61d9-a700-4851-b1cd-49ce042c3530$3c198d79-c46a-4781-8bd1-b6b68f06c31f$a4698418-ebf7-4992-a3ba-a15ff282bf87$59817f59-429b-4f17-a46a-185571fd1e5a$8670abc2-63e6-496a-b20c-812197acd9ad$1b2245f8-2f02-4c4d-b6d2-e65af1f2a21e$77093b36-c232-4477-be49-845f1a631829$9722971a-16f1-4f28-ba31-c12b673b8a30$65f4990f-1952-4682-8fa8-9e3dd4bf1ebf$6ed7c73d-60da-4908-85cb-958745d81ebc$9d4858f8-e63d-46e0-a6cc-992d3cc4a9a4$9cef898e-192c-418a-bec6-511f8b6da179$6f10de7b-ce05-4f82-82e7-4110be44e8cc$c2fab245-8a98-4b41-ade2-c5b16e9c39f9$a7afc0cb-a980-4f4f-b782-9791d932ee52$821de132-559b-4420-b866-e97134c5bd9a$ec25ce2a-de8a-4b69-a3f3-b47cd58ec986$67093a35-8e1b-4cd3-b11b-c7ff601f802e$16b677e4-c467-462a-b770-b7a31160e129$4c2d45e3-56a2-467f-b87f-7b98cb873a05$191f8429-cbbb-44aa-8beb-271a94293e4b$e9633e3f-376d-413d-bc19-d015f6ce76e5$61462af5-69bd-42be-8918-7992c79ee00d$592ae01b-2819-402d-9538-17018df5c34b$708c442b-cbff-4e1a-b70d-e704453cfd3d$594829e2-585b-4d48-bb6e-b35d9543cfbe$72ec8410-05d9-475a-93d4-47153cc0ce31$027fe67c-d2f0-49f6-b894-959795551d27$462fa407-d973-4e9e-8512-b7cd3bb98b7b$3cd40d9e-fcea-427d-9877-cea65e7ea413$38744170-9af6-44b5-a0be-46a83da3253e$a1081bb2-2186-4b19-b667-0c246155f360$4714b7d7-32ee-42a1-bfa5-93eafda739d3$b5f3620d-0942-41bb-80b0-d2ddcfe65090$19ef447f-9fdf-49e1-8d1a-7860b4d4e9ba$6cf004be-5205-429e-8131-ef607cebeaec$f6e22fc3-382e-4548-bc59-8f944e06d237$d830fffd-3781-40ca-85cb-c242f99667ce$ac5e1516-1574-4893-a965-f799947076cb$4cb070de-e8bf-4a1d-9625-043c19466c46$6c3bca1a-3109-4e48-97e1-e0ed4599ffb2$1ca71c26-f98c-4126-a1c5-98786fde7e9b$535f4bc1-e88c-47c7-990b-e3c8b5054acc$9b9fc5e6-1a41-43c5-ba43-2c93bc3ef66b$d882afdd-eb85-467c-bf18-525c0c5da5e7$192f608c-0563-4179-903f-49fad2db4c74$8f6ba1c4-a971-4dc4-ac5d-2f30790aecde$ed023033-1044-4d48-aab1-39e9300043f7$bc58ba24-90f0-4913-8f66-10bb6cb54076$4cff1d10-422f-4b12-b790-a589c972fbb7$59ac02af-7b54-44d4-b5f4-a0f60d4458a1$9f55cad1-b01a-45e3-93df-a4349e2dfbd3$e2a3842d-4e07-4703-ab47-a5140649dd6a$08dcbbd3-a531-4f74-a724-1cae8fae1636$82ba8fe1-435e-422b-abb7-cb50a7a85e1e$8b16a522-9be4-4286-b64d-3d1bbdef7142$ec14d629-b720-47cd-bc08-ff96f49271ab$059b0ada-2442-48e4-82dd-489cb97e5dcc$4be6cea4-13a2-4bcb-b849-14eef57ab604$9efb7a71-9a03-4716-8d34-aae233e9b898$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253$bcf73ad7-a08b-4cbb-bcd2-d0abc002e7e2$bc9a718f-4b97-4e15-acf8-d180abc5b6d5$64eb4b52-4946-467c-867a-a6fc437b15f6$a7d9703a-5121-4b43-8cd4-2acf9a0d91ef$ce07d5c5-90a3-4c12-bada-30e4da1b99fd$15367f3b-c7e4-4004-a018-5422a7f22024$ae89661a-2c0f-4752-adc2-023f09dc0e9f$e1b5733f-a7a8-458f-a345-b358b9a03fcf$4a98507b-653e-4354-a825-7605f8fcb31b$f86a5efc-d31e-4e88-b81f-ebdbbeba11ec$ee43c389-55f4-4cf9-a8db-ce37d1b89db4$1072a756-5026-4de9-93a8-f942d54c474a$3026f9c5-81d3-443a-940a-f22fef9754af$4853f4ef-fbb8-48c3-9523-13ab4969d097$6e5e3ec6-c96a-4a4a-bf4d-4b115f9b0d82$7330af43-bec3-460c-94f6-768ac2975b00$59254bfd-48f2-4585-9ba5-e4c809421072$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fd$1e27eedc-5308-4608-863f-fb81d60acdf0$a293bb0e-078d-4335-a446-3096a79c03bc$c5e906c8-0f73-4955-baa7-337195329e04$c376513c-6553-4cd6-8384-ae6ff9d472d7$eb311761-ace2-4632-9ebf-9c7c166659f7$227e415e-ab17-4f3a-b695-9573c9ee2b57$35b7b8b7-bff6-4f64-91b9-b65035162365$3da58487-192f-458a-9d47-7a4ce98b6da3$7f9bd301-355b-43f5-b168-22fac9e52511$06679a09-47d7-4024-8232-4954c08747a0$bafc9870-3823-4d1d-b0b7-94c69ee764d5$b57adc77-3783-4958-91a0-e90782338755$18031ccb-657f-409a-9080-9a0ada3ae8b5$256c8009-4d2b-42f8-adaa-6f238ef22c6d$4e35d650-b9a6-4668-90f0-f27a50af29ad$0e3fb524-bea1-4ef0-9589-36230a84e949$2381babe-0777-45db-acff-cc647a8a68d3$8315b53f-abca-483d-bbf6-7e9193e751c9$0c8ab02e-80b0-44d6-a4a8-c813aac38209$57816e2c-a675-43e7-b674-2877ffcf1415$1b1d5c9b-5fc7-480e-9649-e9c44a49c38d$ba16d83d-21a5-4f0c-807b-674a167da4dc$6c3595d2-4f68-44da-90e7-dc9c68479bcf$8a5a251f-5373-445a-97b1-4d652c6b7ba8published_objectsnbpkgwaiting_for_permission,waiting_for_permission_but_probably_disabled²installed_versionsDocumenterCitations1.3.5LinearAlgebrastdlibPlutoUI0.7.60DataFrames1.7.0Primes0.5.6Colors0.12.11Luxor4.1.0terminal_outputsDocumenterCitations+
[0m[1mResolving...[22m
[90m===[39m
[33m[1m┌ [22m[39m[33m[1mWarning: [22m[39mPkg operation failed. Fixing stdlib dependencies and trying again...
[33m[1m└ [22m[39m[90m@ GracefulPkg ~/.julia/packages/GracefulPkg/0dFzV/src/apply strategies.jl:96[39m
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...nbpkg_sync+
[0m[1mResolving...[22m
[90m===[39m
[33m[1m┌ [22m[39m[33m[1mWarning: [22m[39mPkg operation failed. Fixing stdlib dependencies and trying again...
[33m[1m└ [22m[39m[90m@ GracefulPkg ~/.julia/packages/GracefulPkg/0dFzV/src/apply strategies.jl:96[39m
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...LinearAlgebra+
[0m[1mResolving...[22m
[90m===[39m
[33m[1m┌ [22m[39m[33m[1mWarning: [22m[39mPkg operation failed. Fixing stdlib dependencies and trying again...
[33m[1m└ [22m[39m[90m@ GracefulPkg ~/.julia/packages/GracefulPkg/0dFzV/src/apply strategies.jl:96[39m
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...PlutoUI+
[0m[1mResolving...[22m
[90m===[39m
[33m[1m┌ [22m[39m[33m[1mWarning: [22m[39mPkg operation failed. Fixing stdlib dependencies and trying again...
[33m[1m└ [22m[39m[90m@ GracefulPkg ~/.julia/packages/GracefulPkg/0dFzV/src/apply strategies.jl:96[39m
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...DataFrames+
[0m[1mResolving...[22m
[90m===[39m
[33m[1m┌ [22m[39m[33m[1mWarning: [22m[39mPkg operation failed. Fixing stdlib dependencies and trying again...
[33m[1m└ [22m[39m[90m@ GracefulPkg ~/.julia/packages/GracefulPkg/0dFzV/src/apply strategies.jl:96[39m
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...Primes+
[0m[1mResolving...[22m
[90m===[39m
[33m[1m┌ [22m[39m[33m[1mWarning: [22m[39mPkg operation failed. Fixing stdlib dependencies and trying again...
[33m[1m└ [22m[39m[90m@ GracefulPkg ~/.julia/packages/GracefulPkg/0dFzV/src/apply strategies.jl:96[39m
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...Colors+
[0m[1mResolving...[22m
[90m===[39m
[33m[1m┌ [22m[39m[33m[1mWarning: [22m[39mPkg operation failed. Fixing stdlib dependencies and trying again...
[33m[1m└ [22m[39m[90m@ GracefulPkg ~/.julia/packages/GracefulPkg/0dFzV/src/apply strategies.jl:96[39m
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...Luxor+
[0m[1mResolving...[22m
[90m===[39m
[33m[1m┌ [22m[39m[33m[1mWarning: [22m[39mPkg operation failed. Fixing stdlib dependencies and trying again...
[33m[1m└ [22m[39m[90m@ GracefulPkg ~/.julia/packages/GracefulPkg/0dFzV/src/apply strategies.jl:96[39m
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_slhtocoicf/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...enabledìinstantiated÷restart_recommended_msgrestart_required_msginstall_time_nsμ_
busy_packagescell_inputs $d882afdd-eb85-467c-bf18-525c0c5da5e7cell_id$d882afdd-eb85-467c-bf18-525c0c5da5e7code@time fib_diag(20000)metadatashow_logsèdisabled®skip_as_script«code_folded$1b1d5c9b-5fc7-480e-9649-e9c44a49c38dcell_id$1b1d5c9b-5fc7-480e-9649-e9c44a49c38dcodeinclude("utils.jl")metadatashow_logsèdisabled®skip_as_script«code_folded$4cb070de-e8bf-4a1d-9625-043c19466c46cell_id$4cb070de-e8bf-4a1d-9625-043c19466c46code@time fib_pow(20000)metadatashow_logsèdisabled®skip_as_script«code_folded$aee611f2-bc86-4e85-bbcb-add78c6a9175cell_id$aee611f2-bc86-4e85-bbcb-add78c6a9175code)gcd_g, gcd_x, gcd_y = pgcdx(gcd_a, gcd_b)metadatashow_logsèdisabled®skip_as_script«code_folded$5c6c45b4-67e3-4ea8-bc09-0205ab24cbc3cell_id$5c6c45b4-67e3-4ea8-bc09-0205ab24cbc3codemod(mod(a, n) * mod(b, n), n)metadatashow_logsèdisabled®skip_as_script«code_folded$6c3595d2-4f68-44da-90e7-dc9c68479bcfcell_id$6c3595d2-4f68-44da-90e7-dc9c68479bcfcode(cite(args...) = bibcite(biblio, args...)metadatashow_logsèdisabled®skip_as_script«code_folded$cd481f6c-66f4-4ebf-9769-c3edc24f403bcell_id$cd481f6c-66f4-4ebf-9769-c3edc24f403bcode1frametitle("Algorithme d'Euclide : élaboration")metadatashow_logsèdisabled®skip_as_script«code_folded$37585789-bd43-4ce5-b550-ad712b70d226cell_id$37585789-bd43-4ce5-b550-ad712b70d226codemd"""
> **Définition** Le résultat de la *division Euclidienne* de ``a`` par un diviseur ``d`` est un quotient ``q`` et un reste ``0 \le r < d`` tels que ``a = qd + r``. En notation modulaire ``a \equiv r \pmod{d}``.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$4a98507b-653e-4354-a825-7605f8fcb31bcell_id$4a98507b-653e-4354-a825-7605f8fcb31bcodeFmod.(fast_mod_power.(g, 0:3, 17) * fast_mod_power.(g^4, 0:3, 17)', 17)metadatashow_logsèdisabled®skip_as_script«code_folded$bcf73ad7-a08b-4cbb-bcd2-d0abc002e7e2cell_id$bcf73ad7-a08b-4cbb-bcd2-d0abc002e7e2codeqa(md"Quelle est la complexité spatiale et temporelle de `discrete_log` ?", md"""
``\mathcal{O}(p)`` temporelle et ``\Omega(1)`` spatiale. Voir $(cite("hoffstein2014Introduction", "Proposition 2.19")).
""")metadatashow_logsèdisabled®skip_as_script«code_folded$b319619e-8f8d-4650-8fb4-76e5ba953470cell_id$b319619e-8f8d-4650-8fb4-76e5ba953470codemd"""
```math
xb + yr = g \quad \text{et} \quad r = a - qb \quad \Rightarrow \quad (x - yq)b + ya = g
```
Solution *homogène* ``x = b``, ``y = -a`` → ``ba - ab = 0``.
Donc si ``(x, y)`` est solution, ``(x + b, y - a)`` aussi.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$08dcbbd3-a531-4f74-a724-1cae8fae1636cell_id$08dcbbd3-a531-4f74-a724-1cae8fae1636codeٳif length(unique(sort(all_powers))) == p - 1
md"Le nombre $g **est** une racine primitive modulo $p"
else
md"Le nombre $g **n'est pas** une racine primitive modulo $p"
endmetadatashow_logsèdisabled®skip_as_script«code_folded$ce07d5c5-90a3-4c12-bada-30e4da1b99fdcell_id$ce07d5c5-90a3-4c12-bada-30e4da1b99fdcodefast_mod_power.(g, 0:15, 17)metadatashow_logsèdisabled®skip_as_script«code_folded$ec25ce2a-de8a-4b69-a3f3-b47cd58ec986cell_id$ec25ce2a-de8a-4b69-a3f3-b47cd58ec986code;chinese_remainder_theorem([pow_1000, pow_999], [1000, 999])metadatashow_logsèdisabled®skip_as_script«code_folded$821de132-559b-4420-b866-e97134c5bd9acell_id$821de132-559b-4420-b866-e97134c5bd9acode`function chinese_remainder_theorem(r, n)
for i in eachindex(n)
for j in eachindex(n)
if i != j && gcd(n[i], n[j]) != 1
error("`$(n[i])` and `$(n[j])` are not coprime")
end
end
end
prod_n = prod(n)
return mod(sum(eachindex(n)) do i
m = div(prod_n, n[i])
return mod(r[i] * mod(m * modinv(m, n[i]), prod_n), prod_n)
end, prod_n)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$bc58ba24-90f0-4913-8f66-10bb6cb54076cell_id$bc58ba24-90f0-4913-8f66-10bb6cb54076codemd"""
**Définition** ``g`` est une *racine primitive* modulo ``p`` si ``g^k`` prend toutes les valeurs ``1, 2, ..., p - 1``.
```math
\text{Si } \quad p \nmid b,\quad \text{ alors } \quad
b^{p - 1} \equiv 1 \pmod{p}
```
"""metadatashow_logsèdisabled®skip_as_script«code_folded$35b7b8b7-bff6-4f64-91b9-b65035162365cell_id$35b7b8b7-bff6-4f64-91b9-b65035162365code@md"""Voir $(cite("hoffstein2014Introduction", "Section 2.3"))"""metadatashow_logsèdisabled®skip_as_script«code_folded$59ac02af-7b54-44d4-b5f4-a0f60d4458a1cell_id$59ac02af-7b54-44d4-b5f4-a0f60d4458a1code+all_powers = fast_mod_power.(g, 1:(p-1), p)metadatashow_logsèdisabled®skip_as_script«code_folded$c2fab245-8a98-4b41-ade2-c5b16e9c39f9cell_id$c2fab245-8a98-4b41-ade2-c5b16e9c39f9code'frametitle("Chinese remainder theorem")metadatashow_logsèdisabled®skip_as_script«code_folded$535f4bc1-e88c-47c7-990b-e3c8b5054acccell_id$535f4bc1-e88c-47c7-990b-e3c8b5054acccodeOfib_closed(n) = (((1 + √big(5)) / 2)^n - ((1 - √big(5)) / 2)^n) / √big(5)metadatashow_logsèdisabled®skip_as_script«code_folded$6107d03d-1e45-4eb9-b8e2-51e4a72485e6cell_id$6107d03d-1e45-4eb9-b8e2-51e4a72485e6code&frametitle("Recursive implementation")metadatashow_logsèdisabled®skip_as_script«code_folded$03e49669-cdee-4241-862d-33ee91214455cell_id$03e49669-cdee-4241-862d-33ee91214455code[md"The complexity is difficult to evaluate but can be shown to be ``O(\log(\min(a, b)))``."metadatashow_logsèdisabled®skip_as_script«code_folded$ac5e1516-1574-4893-a965-f799947076cbcell_id$ac5e1516-1574-4893-a965-f799947076cbcode@time fib_diag(20000)metadatashow_logsèdisabled®skip_as_script«code_folded$a826d9d1-47db-4645-be6e-3ae0ed8d4e18cell_id$a826d9d1-47db-4645-be6e-3ae0ed8d4e18codemd"""
Est-ce que 2345 est divisible par 3 ou 9?
```math
\begin{align}
2 \cdot 10^3 + 3 \cdot 10^2 + 4 \cdot 10 + 5 & \equiv \,\, ? \pmod{9}\\
2 \cdot 1^3 + 3 \cdot 1^2 + 4 \cdot 1 + 5 & \equiv \,\, ? \pmod{9}\\
2 + 3 + 4 + 5 & \equiv 14 \pmod{9}\\
\end{align}
```
Est-ce que 2345 est divisible par 11?
```math
\begin{align}
2 \cdot (10)^3 + 3 \cdot 10^2 + 4 \cdot 10 + 5 & \equiv \,\, ? \pmod{11}\\
2 \cdot (-1)^3 + 3 \cdot (-1)^2 + 4 \cdot (-1) + 5 & \equiv \,\, ? \pmod{11}\\
-2 + 3 - 4 + 5 & \equiv 2 \pmod{11}\\
\end{align}
```
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b5f3620d-0942-41bb-80b0-d2ddcfe65090cell_id$b5f3620d-0942-41bb-80b0-d2ddcfe65090codeE = eigen([1 1; 1 0])metadatashow_logsèdisabled®skip_as_script«code_folded$bbc907b1-63f8-435a-badc-11ed88bd6cf5cell_id$bbc907b1-63f8-435a-badc-11ed88bd6cf5codeframetitle("Exemples")metadatashow_logsèdisabled®skip_as_script«code_folded$ae89661a-2c0f-4752-adc2-023f09dc0e9fcell_id$ae89661a-2c0f-4752-adc2-023f09dc0e9fcode+reshape(fast_mod_power.(g, 0:15, 17), 4, 4)metadatashow_logsèdisabled®skip_as_script«code_folded$0c8ab02e-80b0-44d6-a4a8-c813aac38209cell_id$0c8ab02e-80b0-44d6-a4a8-c813aac38209codeFfib_picker = @bind fib_n Slider(1:12, default = 10, show_value = true)metadatashow_logsèdisabled®skip_as_script«code_folded$f9f03579-5bfc-452d-bff9-9e7adfe095d3cell_id$f9f03579-5bfc-452d-bff9-9e7adfe095d3codegcd(364, 7)metadatashow_logsèdisabled®skip_as_script«code_folded$a1628317-7937-4316-85bf-2da860effce3cell_id$a1628317-7937-4316-85bf-2da860effce3codemod(a * b, n)metadatashow_logsèdisabled®skip_as_script«code_folded$a7985d16-500b-4024-aaa1-78e654b94be4cell_id$a7985d16-500b-4024-aaa1-78e654b94be4codeBqa(md"Comment trouver l'inverse modulaire ?",
md"""
Si on avait les coefficients ``x`` et ``y`` tels que ``xa + yn = 1``, l'inverse serait ``x``. Dans l'algorithme d'Euclide, on ne garde que le **reste** et on oublie le **quotient**. Il faudrait combiner les quotients des différentes opérations pour trouver ``x``.
""")metadatashow_logsèdisabled®skip_as_script«code_folded$4c2d45e3-56a2-467f-b87f-7b98cb873a05cell_id$4c2d45e3-56a2-467f-b87f-7b98cb873a05code%fast_mod_power.(2, power, prime_list)metadatashow_logsèdisabled®skip_as_script«code_folded$4cff1d10-422f-4b12-b790-a589c972fbb7cell_id$4cff1d10-422f-4b12-b790-a589c972fbb7codegp_pickermetadatashow_logsèdisabled®skip_as_script«code_folded$087cbe82-b42a-4f80-a1af-97f3aa93aeebcell_id$087cbe82-b42a-4f80-a1af-97f3aa93aeebcodemd"`power` = $power_slider"metadatashow_logsèdisabled®skip_as_script«code_folded$7db2060b-d69e-42e7-ae81-fd37ee793876cell_id$7db2060b-d69e-42e7-ae81-fd37ee793876codemd"""
Corollaire
```math
n \mid a \quad \text{et} \quad n \mid b \quad \Rightarrow \quad n \mid (ab)
```
À ne pas confondre avec
```math
a \mid n \quad \text{et} \quad b \mid n \quad \Rightarrow \quad (ab/\text{gcd}(a,b)) \mid n
```
"""metadatashow_logsèdisabled®skip_as_script«code_folded$a293bb0e-078d-4335-a446-3096a79c03bccell_id$a293bb0e-078d-4335-a446-3096a79c03bccodeframetitle("Diffie-Hellman")metadatashow_logsèdisabled®skip_as_script«code_folded$2381babe-0777-45db-acff-cc647a8a68d3cell_id$2381babe-0777-45db-acff-cc647a8a68d3codeLpower_slider = @bind power Slider(1:10000, default = 256, show_value = true)metadatashow_logsèdisabled®skip_as_script«code_folded$e1aafab7-c4f3-45ac-81ee-7f875ac7c8c6cell_id$e1aafab7-c4f3-45ac-81ee-7f875ac7c8c6codemd"""
* **Inverse modulaire** : étant donné ``a, n``, trouver ``x`` (noté ``a^{-1}``) tel que ``xa \equiv 1 \pmod{n}``
* **Division modulaire** : étant donné ``a, b, n``, trouver ``x`` tel que ``xa \equiv b \pmod{n}`` → ``x \equiv a^{-1}b \pmod{n}``.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$9f55cad1-b01a-45e3-93df-a4349e2dfbd3cell_id$9f55cad1-b01a-45e3-93df-a4349e2dfbd3codesort(all_powers)metadatashow_logsèdisabled®skip_as_script«code_folded$4be6cea4-13a2-4bcb-b849-14eef57ab604cell_id$4be6cea4-13a2-4bcb-b849-14eef57ab604codeٳif length(unique(sort(all_powers))) == p - 1
md"Le nombre $g **est** une racine primitive modulo $p"
else
md"Le nombre $g **n'est pas** une racine primitive modulo $p"
endmetadatashow_logsèdisabled®skip_as_script«code_folded$9d4858f8-e63d-46e0-a6cc-992d3cc4a9a4cell_id$9d4858f8-e63d-46e0-a6cc-992d3cc4a9a4codeqa(md"Comment trouver `mod(2^power, 999000)` en utilisant `pow_1000` et `pow_999` ?", md"
On peut utiliser une astuce similaire à l'interpolation Lagrangienne.
On veut trouver ``x`` et ``y`` tels que
```math
\texttt{pow\_1000}x + \texttt{pow\_999}y \equiv 2^\texttt{power} \pmod{999000}
```
On veut que ``x \equiv 0 \pmod{999}`` et ``x \equiv 1 \pmod{1000}``.
On utilise donc ``x = 999x'`` avec ``x' \equiv (999)^{-1} \pmod{1000}``.
")metadatashow_logsèdisabled®skip_as_script«code_folded$c8f85081-3659-4796-8550-2e708b09c8d7cell_id$c8f85081-3659-4796-8550-2e708b09c8d7codemd"`power` = $power_slider"metadatashow_logsèdisabled®skip_as_script«code_folded$0e3fb524-bea1-4ef0-9589-36230a84e949cell_id$0e3fb524-bea1-4ef0-9589-36230a84e949codergp_picker = HAlign(
md"`g` = $(@bind g Slider(2:(p-1), default = 2, show_value = true))",
md"`p` = $p_picker",
)metadatashow_logsèdisabled®skip_as_script«code_folded$a7d06375-e4dd-47b1-8aba-11dc4d62954bcell_id$a7d06375-e4dd-47b1-8aba-11dc4d62954bcodeٝqa(md"Supposons que ``m`` est pair, c'est à dire ``m = 2k``...",
md"""
On a ``a^(2k) = (a^k)^2``. Si ``b = a^k``, on calcule le produit ``b \times b``.
""")metadatashow_logsèdisabled®skip_as_script«code_folded$bbb2793a-faa4-43bd-b2e8-e8d3ac93310fcell_id$bbb2793a-faa4-43bd-b2e8-e8d3ac93310fcode]md"S'il y avait 364 jours par ans, les fêtes seraient toujours le même jour de la semaine!"metadatashow_logsèdisabled®skip_as_script«code_folded$7330af43-bec3-460c-94f6-768ac2975b00cell_id$7330af43-bec3-460c-94f6-768ac2975b00code٢function shanks_discrete_log(a, g, p)
n = isqrt(p) + 1
i, j = collision(baby_steps(g, n, p), mod.(a .* giant_steps(g, n, p), p))
return i - 1 + (j - 1) * n
endmetadatashow_logsèdisabled®skip_as_script«code_folded$67093a35-8e1b-4cd3-b11b-c7ff601f802ecell_id$67093a35-8e1b-4cd3-b11b-c7ff601f802ecode[md"`primes_upper` = $(@bind primes_upper Slider(50:300, default = 100, show_value = true))"metadatashow_logsèdisabled®skip_as_script«code_folded$48eba223-6cce-4aa2-9977-4883ba7903fccell_id$48eba223-6cce-4aa2-9977-4883ba7903fccodeqa(md"**Observation finale** Si ``a`` et ``b`` sont positifs et qu'on effectue la substitution ``(a, b) \to (b, r)`` récursivement, le mono-variant impose qu'on ne puisse itérer qu'un nombre fini de fois, que va-t-il se passer ?",
md"""
La paire ``(a, b)`` va diminuer strictement (c'est à dire d'au moins 1) à chaque itération. Pourtant, ce sont des nombres entier positifs donc ils ne peuvent diminuer strictement qu'un nombre fini de fois. C'est une contradiction, comme cela se fait-il ?
À un moment ``b`` vaudra 0, on ne pourra alors plus faire de division Euclidienne. On utilisera alors le fait que ``\text{gcd}(a, 0) = a``.
""")metadatashow_logsèdisabled®skip_as_script«code_folded$6f10de7b-ce05-4f82-82e7-4110be44e8cccell_id$6f10de7b-ce05-4f82-82e7-4110be44e8cccodeTmod(pow_1000 * 999 * modinv(999, 1000) + pow_999 * 1000 * modinv(1000, 999), 999000)metadatashow_logsèdisabled®skip_as_script«code_folded$1ca71c26-f98c-4126-a1c5-98786fde7e9bcell_id$1ca71c26-f98c-4126-a1c5-98786fde7e9bcodemd"""
Trouver ``b`` tel que ``x_k`` est solution:
```math
x_k = b^k
\quad \to \quad b^{k+1} = b^k + b^{k-1}
\quad \to \quad b^2 - b - 1 = 0
\quad \to \quad b = \frac{1 \pm \sqrt{5}}{2}
```
On a donc une famille de solutions:
```math
x_k = a_1
\left(\frac{1 - \sqrt5}{2}\right)^k +
a_2
\left(\frac{1 + \sqrt5}{2}\right)^k
```
Il reste à trouver ``a_1`` et ``a_2`` tels que ``x_0 = 0`` et ``x_1 = 1``. Ça correspond à calculer `E.vectors \ [1, 0]`, etc...
```math
\begin{align}
x_0 & = 0 & a_1 + a_2 & = 0\\
x_1 & = 1 & a_1 \frac{1 - \sqrt5}{2} + a_2 \frac{1 + \sqrt5}{2} & = 1
\end{align}
```
Donc ``a_1 = -1/\sqrt5`` et ``a_2 = 1/\sqrt5``.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$82ba8fe1-435e-422b-abb7-cb50a7a85e1ecell_id$82ba8fe1-435e-422b-abb7-cb50a7a85e1ecodeframetitle("Dicrete logarithm")metadatashow_logsèdisabled®skip_as_script«code_folded$61462af5-69bd-42be-8918-7992c79ee00dcell_id$61462af5-69bd-42be-8918-7992c79ee00dcodeqa(md"Comment savoir si `prime_list` contient assez de nombres pour avoir la bonne réponse ?", md"On a la bonne réponse modulo `prod(prime_list)` donc si `prod(prime_list) > 2^power`, on a la bonne réponse.")metadatashow_logsèdisabled®skip_as_script«code_folded$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fdcell_id$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fdcodefast_mod_power(g, shanks_x, p)metadatashow_logsèdisabled®skip_as_script«code_folded$57816e2c-a675-43e7-b674-2877ffcf1415cell_id$57816e2c-a675-43e7-b674-2877ffcf1415codeFp_picker = @bind p Slider(primes(20), default = 11, show_value = true)metadatashow_logsèdisabled®skip_as_script«code_folded$16b677e4-c467-462a-b770-b7a31160e129cell_id$16b677e4-c467-462a-b770-b7a31160e129code$prime_list = primes(3, primes_upper)metadatashow_logsèdisabled®skip_as_script«code_folded$6e5e3ec6-c96a-4a4a-bf4d-4b115f9b0d82cell_id$6e5e3ec6-c96a-4a4a-bf4d-4b115f9b0d82codeٓfunction collision(a, b)
d = Dict(a[i] => i for i in eachindex(a))
for j in eachindex(b)
if haskey(d, b[j])
return d[b[j]], j
end
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$6332b2f2-ed2f-448a-b1df-247b110e335bcell_id$6332b2f2-ed2f-448a-b1df-247b110e335bcodeًqa(md"Que faire si que ``m`` est impair, c'est à dire ``m = 2k + 1``...",
md"""
Si ``b = a^(2k)``, calcule le produit ``b \times a``.
""")metadatashow_logsèdisabled®skip_as_script«code_folded$3c198d79-c46a-4781-8bd1-b6b68f06c31fcell_id$3c198d79-c46a-4781-8bd1-b6b68f06c31fcode"@time fast_power(*, big(2), power)metadatashow_logsèdisabled®skip_as_script«code_folded$d830fffd-3781-40ca-85cb-c242f99667cecell_id$d830fffd-3781-40ca-85cb-c242f99667cecodeWfunction fib_diag(n)
x = E.vectors * D^(n - 1) * (E.vectors \ [1, 0])
return x[1]
endmetadatashow_logsèdisabled®skip_as_script«code_folded$8b16a522-9be4-4286-b64d-3d1bbdef7142cell_id$8b16a522-9be4-4286-b64d-3d1bbdef7142codemd"""
Étant donné un nombre premier ``p`` et une racine primitive ``g`` modulo ``p`` et un entier ``a`` tel que ``p \nmid a``, le *Discrete logarithme problem* consiste à retrouver ``x`` tel que ``g^x \equiv a \pmod{p}``.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$2c34c17e-12de-43ea-870c-818c97647836cell_id$2c34c17e-12de-43ea-870c-818c97647836code5frametitle("Inversion modulaire par Euclide étendu")metadatashow_logsèdisabled®skip_as_script«code_folded$ca8905ef-97a3-424c-bb2e-559f7151585bcell_id$ca8905ef-97a3-424c-bb2e-559f7151585bcodeٕmd"""
Ensemble de solutions: ``(x + kb, y - ka)`` pour un ``k \in \mathbb{Z}`` arbitraire.
Prenons ``k`` tel que ``0 \le x + kb < b`` avec `mod`.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$97736c6a-3f5d-4978-8dd2-0a11c09ba9f0cell_id$97736c6a-3f5d-4978-8dd2-0a11c09ba9f0codefunction pgcd(a, b)
println("gcd($a, $b) = ")
if b == 0
println(a)
return a
else
return pgcd(b, mod(a, b))
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$192f608c-0563-4179-903f-49fad2db4c74cell_id$192f608c-0563-4179-903f-49fad2db4c74code@time fib_pow(20000)metadatashow_logsèdisabled®skip_as_script«code_folded$f39cccac-5b24-46e4-8749-1b0a944542efcell_id$f39cccac-5b24-46e4-8749-1b0a944542efcode[md"`gcd_b` = $(@bind gcd_b Slider(1:typemax(Int32), default=249357461, show_value = true))"metadatashow_logsèdisabled®skip_as_script«code_folded$909b8a36-79bb-4c1a-9dd7-4acaffc0434ecell_id$909b8a36-79bb-4c1a-9dd7-4acaffc0434ecode#frametitle("Théorème de Bézout")metadatashow_logsèdisabled®skip_as_script«code_folded$e1b5733f-a7a8-458f-a345-b358b9a03fcfcell_id$e1b5733f-a7a8-458f-a345-b358b9a03fcfcodemd"""
On remarque que la matrice est de rang 1. Elle vaut
```math
\begin{bmatrix}
1 & g^n & \cdots & g^{n^2-n}\\
g & g^{n+1} & \ddots & g^{n^2-n+1}\\
\vdots & \ddots & \ddots & \vdots\\
g^{n-1} & g^{2n-1} & \cdots & g^{n^2 - 1}
\end{bmatrix}
\equiv
\begin{bmatrix}
1\\
g\\
g^2\\
\vdots\\
g^{n-1}
\end{bmatrix}
\begin{bmatrix}
1 &
g^{n} &
g^{2n} &
\cdots &
g^{n^2-n}
\end{bmatrix}
\pmod{p}
```
"""metadatashow_logsèdisabled®skip_as_script«code_folded$d8a28762-8aab-49e9-b9ac-38901d34abffcell_id$d8a28762-8aab-49e9-b9ac-38901d34abffcodeframetitle("Fast powering")metadatashow_logsèdisabled®skip_as_script«code_folded$64eb4b52-4946-467c-867a-a6fc437b15f6cell_id$64eb4b52-4946-467c-867a-a6fc437b15f6code)frametitle("Meet in the middle approach")metadatashow_logsèdisabled®skip_as_script«code_folded$6c3bca1a-3109-4e48-97e1-e0ed4599ffb2cell_id$6c3bca1a-3109-4e48-97e1-e0ed4599ffb2code"frametitle("Closed form solution")metadatashow_logsèdisabled®skip_as_script«code_folded$a59a20e2-a7c7-48a9-ad8d-8094e03a749dcell_id$a59a20e2-a7c7-48a9-ad8d-8094e03a749dcode)collect(mod.(modinv(365, 7) .* (0:6), 7))metadatashow_logsèdisabled®skip_as_script«code_folded$06679a09-47d7-4024-8232-4954c08747a0cell_id$06679a09-47d7-4024-8232-4954c08747a0code?using PlutoUI, Primes, DataFrames, Luxor, Colors, LinearAlgebrametadatashow_logsèdisabled®skip_as_script«code_folded$58da5ba4-c858-4684-a9f4-5a39fdc4fb03cell_id$58da5ba4-c858-4684-a9f4-5a39fdc4fb03codefunction fast_power(prod_func::Function, a, power)
if power == 0
return one(a)
elseif mod(power, 2) == 1
return prod_func(fast_power(prod_func, a, power - 1), a)
else
b = fast_power(prod_func, a, div(power, 2))
return prod_func(b, b)
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$a7afc0cb-a980-4f4f-b782-9791d932ee52cell_id$a7afc0cb-a980-4f4f-b782-9791d932ee52codeCmd"""
Voir $(cite("hoffstein2014Introduction", "Section 2.8")).
"""metadatashow_logsèdisabled®skip_as_script«code_folded$6ed7c73d-60da-4908-85cb-958745d81ebccell_id$6ed7c73d-60da-4908-85cb-958745d81ebccodeZmd"Par l'algo d'Euclide, ``\text{gcd}(n, n - 1) = 1`` donc ``\text{gcd}(1000, 999) = 1``."metadatashow_logsèdisabled®skip_as_script«code_folded$bc9a718f-4b97-4e15-acf8-d180abc5b6d5cell_id$bc9a718f-4b97-4e15-acf8-d180abc5b6d5code^qa(md"Est-ce une complexité linéaire ou exponentielle en fonction de la taille de l'input",
md"""
La taille est proportionnelle à ``\log_2(p)`` donc on être linéaire en ``p`` c'est être proportionnel à ``2^{\log_2(p)}`` et donc la complexité est exponentielle en la taille de l'input ! $(cite("hoffstein2014Introduction", "Section 2.6"))
""")metadatashow_logsèdisabled®skip_as_script«code_folded$ec14d629-b720-47cd-bc08-ff96f49271abcell_id$ec14d629-b720-47cd-bc08-ff96f49271abcodezfunction discrete_log(a, g, p)
gx = one(a)
for x = 0:(p-2)
if a == gx
return x
end
gx = mod(gx * g, p)
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$d1b260fb-7500-47fb-bb48-21b5857ab55acell_id$d1b260fb-7500-47fb-bb48-21b5857ab55acode^md"""
**Lemme**: Si ``a \equiv r \pmod{b}`` alors ``\text{gcd}(a, b) = \text{gcd}(b, r)``.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$09f44611-ba21-4982-ba1b-0691124642fccell_id$09f44611-ba21-4982-ba1b-0691124642fccode/frametitle("Arithmétique modulaire : produit")metadatashow_logsèdisabled®skip_as_script«code_folded$256c8009-4d2b-42f8-adaa-6f238ef22c6dcell_id$256c8009-4d2b-42f8-adaa-6f238ef22c6dcode>slider_n = @bind n Slider(1:100, default=5, show_value = true)metadatashow_logsèdisabled®skip_as_script«code_folded$c5e906c8-0f73-4955-baa7-337195329e04cell_id$c5e906c8-0f73-4955-baa7-337195329e04codemd"""
Étant donné un nombre premier ``p`` et une racine primitive ``g`` modulo ``p``, Alice (resp. Bob) génère un nombre secret ``a`` (resp. ``b``). Ils communique ensuite publiquement ``A`` et ``B``.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$08b18315-c28e-44ed-beb2-5b17421b0224cell_id$08b18315-c28e-44ed-beb2-5b17421b0224codemd"""
> **Définition** Le *Greatest Common Divisor (GCD)* de deux nombres ``a \in \mathbb{Z}`` et ``b \in \mathbb{Z}``, noté ``\text{gcd}(a, b)`` est le plus grand nombre ``g \in \mathbb{Z}`` qui divise ``a`` (noté ``g \mid a``) et ``b`` (noté ``g \mid b``). C'est à dire qu'il existe ``x \in \mathbb{Z}`` tel que ``a = gx`` et ``y \in \mathbb{Z}`` tel que ``b = gy``. En notation modulaire, ``a \equiv 0 \pmod{g}`` et ``b \equiv 0 \pmod{g}``.
> **Théorème de Bézout** Il existe ``x, y \in \mathbb{Z}`` tels que ``ax + by = c`` si et seulement si ``\text{gcd}(a, b)`` divise ``c``. En notation modulaire ``ax \equiv c \pmod{b}`` et ``by \equiv c \pmod{a}``.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$8670abc2-63e6-496a-b20c-812197acd9adcell_id$8670abc2-63e6-496a-b20c-812197acd9adcodeKfast_mod_power(a, power, n) = fast_power((a, b) -> mod(a * b, n), a, power)metadatashow_logsèdisabled®skip_as_script«code_folded$18031ccb-657f-409a-9080-9a0ada3ae8b5cell_id$18031ccb-657f-409a-9080-9a0ada3ae8b5code?slider_b = @bind b Slider(1:100, default=13, show_value = true)metadatashow_logsèdisabled®skip_as_script«code_folded$4714b7d7-32ee-42a1-bfa5-93eafda739d3cell_id$4714b7d7-32ee-42a1-bfa5-93eafda739d3code2frametitle("Diagonalization to speed up powering")metadatashow_logsèdisabled®skip_as_script«code_folded$2cb5c6e0-b431-4d2e-b023-cd2131112ecacell_id$2cb5c6e0-b431-4d2e-b023-cd2131112ecacode*frametitle("Algorithme d'Euclide étendu")metadatashow_logsèdisabled®skip_as_script«code_folded$b57adc77-3783-4958-91a0-e90782338755cell_id$b57adc77-3783-4958-91a0-e90782338755code?slider_a = @bind a Slider(1:100, default=11, show_value = true)metadatashow_logsèdisabled®skip_as_script«code_folded$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253cell_id$9bdb30ba-48a7-4e1b-96c2-ea0e059d5253codefast_mod_power(g, x, p)metadatashow_logsèdisabled®skip_as_script«code_folded$a41722b8-8c21-4d3c-a38b-4d248a79e80acell_id$a41722b8-8c21-4d3c-a38b-4d248a79e80acodemd"Pas une solution unique:"metadatashow_logsèdisabled®skip_as_script«code_folded$40b8e474-16e0-4a61-bb28-11d90beefeeacell_id$40b8e474-16e0-4a61-bb28-11d90beefeeacodegcd_x * gcd_a + gcd_y * gcd_bmetadatashow_logsèdisabled®skip_as_script«code_folded$7da0705e-c925-4f8d-9ca4-8d8a0f859feacell_id$7da0705e-c925-4f8d-9ca4-8d8a0f859feacodeTmd"``365x \equiv j \pmod{7} \quad \Rightarrow \quad x \equiv (365)^{-1} j\pmod{7}``"metadatashow_logsèdisabled®skip_as_script«code_folded$227e415e-ab17-4f3a-b695-9573c9ee2b57cell_id$227e415e-ab17-4f3a-b695-9573c9ee2b57code`qa(md"What is the relation between ``A'`` and ``B'`` ?",
md"""
```math
A' \equiv (g^b)^a \equiv g^{ab} \equiv (g^{a})^b \equiv B' \pmod{p}
```
Alice et Bob ont donc maintenant la même clef! Il est cependant difficile de trouver ``A'`` depuis ``A`` et ``B`` sans connaitre les secrets ``a`` ou ``b`` si le Discrete Logarithm Problem est difficile.
""")metadatashow_logsèdisabled®skip_as_script«code_folded$15367f3b-c7e4-4004-a018-5422a7f22024cell_id$15367f3b-c7e4-4004-a018-5422a7f22024code^md"On peut mettre le vecteur de taille ``n^2`` sous forme de matrice de taille ``n \times n``"metadatashow_logsèdisabled®skip_as_script«code_folded$594829e2-585b-4d48-bb6e-b35d9543cfbecell_id$594829e2-585b-4d48-bb6e-b35d9543cfbecode(frametitle("Fast powering for matrices")metadatashow_logsèdisabled®skip_as_script«code_folded$c3411941-d77f-46cb-8378-23998a1a4828cell_id$c3411941-d77f-46cb-8378-23998a1a4828code!frametitle("Division par 3 et 9")metadatashow_logsèdisabled®skip_as_script«code_folded$4e35d650-b9a6-4668-90f0-f27a50af29adcell_id$4e35d650-b9a6-4668-90f0-f27a50af29adcode٤abn_picker = md"""
| `a` | ``\alpha`` | `b` | ``\beta`` | `n` |
|------|-----|-----|---|---|
| $slider_a | $(mod(a, n)) | $slider_b | $(mod(b, n)) | $slider_n |
"""metadatashow_logsèdisabled®skip_as_script«code_folded$e52d25b3-65bf-4617-ae8d-fae0d0c8d041cell_id$e52d25b3-65bf-4617-ae8d-fae0d0c8d041codeTmd"``366x \equiv j \pmod{7} \quad \Rightarrow \quad x \equiv (366)^{-1} j\pmod{7}``"metadatashow_logsèdisabled®skip_as_script«code_folded$bd0c0258-7040-42e7-a20e-532b55af3a62cell_id$bd0c0258-7040-42e7-a20e-532b55af3a62code4frametitle("Algorithme d'Euclide : implémentation")metadatashow_logsèdisabled®skip_as_script«code_folded$191f8429-cbbb-44aa-8beb-271a94293e4bcell_id$191f8429-cbbb-44aa-8beb-271a94293e4bcodeXchinese_remainder_theorem(big.(fast_mod_power.(2, power, prime_list)), big.(prime_list))metadatashow_logsèdisabled®skip_as_script«code_folded$e505716d-af01-455f-a55a-a9c225822ad5cell_id$e505716d-af01-455f-a55a-a9c225822ad5code8md"""
Comment calculer ``a^m`` pour un large ``m`` ?
"""metadatashow_logsèdisabled®skip_as_script«code_folded$ed3d6ea6-08c9-45d0-8b77-3389a557bfd1cell_id$ed3d6ea6-08c9-45d0-8b77-3389a557bfd1code)collect(mod.(modinv(366, 7) .* (0:6), 7))metadatashow_logsèdisabled®skip_as_script«code_folded$642d545f-b1b9-49da-8a03-ad63e3214f59cell_id$642d545f-b1b9-49da-8a03-ad63e3214f59codeٕmd"""
```math
a \equiv \alpha \pmod{n} \quad \text{et} \quad b \equiv \beta \pmod{n}
\quad \Rightarrow \quad a b \equiv \alpha \beta \pmod{n}
```
"""metadatashow_logsèdisabled®skip_as_script«code_folded$bafc9870-3823-4d1d-b0b7-94c69ee764d5cell_id$bafc9870-3823-4d1d-b0b7-94c69ee764d5codeimport DocumenterCitationsmetadatashow_logsèdisabled®skip_as_script«code_folded$19ef447f-9fdf-49e1-8d1a-7860b4d4e9bacell_id$19ef447f-9fdf-49e1-8d1a-7860b4d4e9bacode8D = Diagonal([(1 - √big(5)) / 2, (1 + √big(5)) / 2])metadatashow_logsèdisabled®skip_as_script«code_folded$7f9bd301-355b-43f5-b168-22fac9e52511cell_id$7f9bd301-355b-43f5-b168-22fac9e52511codePrimes.primes(10)metadatashow_logsèdisabled®skip_as_script«code_folded$d81bbd74-42df-4bb2-a045-9c2642cc19e5cell_id$d81bbd74-42df-4bb2-a045-9c2642cc19e5codeabn_pickermetadatashow_logsèdisabled®skip_as_script«code_folded$1e27eedc-5308-4608-863f-fb81d60acdf0cell_id$1e27eedc-5308-4608-863f-fb81d60acdf0codeHqa(md"Quelle est la complexité?", md"``\mathcal{O}(\sqrt{p}\log(p))``")metadatashow_logsèdisabled®skip_as_script«code_folded$ee43c389-55f4-4cf9-a8db-ce37d1b89db4cell_id$ee43c389-55f4-4cf9-a8db-ce37d1b89db4code5frametitle("Shanks's Babystep–Giantstep Algorithm")metadatashow_logsèdisabled®skip_as_script«code_folded$f6e22fc3-382e-4548-bc59-8f944e06d237cell_id$f6e22fc3-382e-4548-bc59-8f944e06d237code/E.vectors * Diagonal(E.values) * inv(E.vectors)metadatashow_logsèdisabled®skip_as_script«code_folded$8315b53f-abca-483d-bbf6-7e9193e751c9cell_id$8315b53f-abca-483d-bbf6-7e9193e751c9codefunction draw_fib(n, size = 400)
f = [0, 1, 1]
for i in 3:(n+1)
push!(f, f[end] + f[end - 1])
end
scale = div(size, 2maximum(f[end-1]))
#Luxor.scale(scale)
colors = distinguishable_colors(n)
if iseven(n)
Δx = f[end]
Δy = f[end - 1]
else
Δx = f[end - 1]
Δy = f[end]
end
left_most = sum(f[i] for i in 1:(n+1) if mod(i, 4) == 1; init = 0)
up_most = sum(f[i] for i in 1:(n+1) if mod(i, 4) == 0; init = 0)
shift = Point(left_most - Δx / 2, up_most - Δy / 2)
pos(x, y) = scale * (Point(x, y) + shift)
@draw begin
x = 0
y = 0
j = 1
for i in 2:(n+1)
left = x
if isodd(i)
if iseven(div(i - 1, 2))
left -= f[i]
else
left += f[i - 1]
end
end
up = y
if iseven(i)
if iseven(div(i, 2))
up -= f[i]
else
up += f[i-1]
end
end
sethue(colors[i - 1])
setopacity(0.6)
rect(pos(left, up), scale * f[i], scale * f[i], action=:fill)
setopacity(1)
sethue("black")
fontsize(div(scale * f[i], 2))
text(string(f[i]), pos(left + f[i] / 2, up + f[i] / 2), halign = :center, valign = :middle)
x = min(x, left)
y = min(y, up)
end
end Δx * scale Δy * scale
endmetadatashow_logsèdisabled®skip_as_script«code_folded$3026f9c5-81d3-443a-940a-f22fef9754afcell_id$3026f9c5-81d3-443a-940a-f22fef9754afcodehfunction giant_steps(g, n, p)
gn = fast_mod_power(g, n, p)
return baby_steps.(modinv(gn, p), n, p)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$87fdefa1-3bbd-4b69-ad3a-72baca6e55eecell_id$87fdefa1-3bbd-4b69-ad3a-72baca6e55eecodemod(mod(a, n) + mod(b, n), n)metadatashow_logsèdisabled®skip_as_script«code_folded$0ee6972c-5069-4ba0-887f-be64c7d000d0cell_id$0ee6972c-5069-4ba0-887f-be64c7d000d0code-frametitle("Arithmétique modulaire : somme")metadatashow_logsèdisabled®skip_as_script«code_folded$592ae01b-2819-402d-9538-17018df5c34bcell_id$592ae01b-2819-402d-9538-17018df5c34bcode frametitle("Fibonacci sequence")metadatashow_logsèdisabled®skip_as_script«code_folded$59817f59-429b-4f17-a46a-185571fd1e5acell_id$59817f59-429b-4f17-a46a-185571fd1e5acode#frametitle("Fast modular powering")metadatashow_logsèdisabled®skip_as_script«code_folded$a4698418-ebf7-4992-a3ba-a15ff282bf87cell_id$a4698418-ebf7-4992-a3ba-a15ff282bf87codeUqa(md"Quelle est la complexité temporelle ?", md"Si ``n`` est impair, au coup suivant, il est pair donc il n'est impair qu'au pire une fois sur deux. En ``l`` multiplication, on divise ``m`` au moins par ``2^{l/2}`` donc on a une complexité logarithmique ``\Theta(\log(m))`` en supposant que `prod_func` a une complexité ``\Theta(1)``.")metadatashow_logsèdisabled®skip_as_script«code_folded$3da58487-192f-458a-9d47-7a4ce98b6da3cell_id$3da58487-192f-458a-9d47-7a4ce98b6da3codesection("Utils")metadatashow_logsèdisabled®skip_as_script«code_folded$736307ec-a2a4-11ef-0f85-ad1a0093e06acell_id$736307ec-a2a4-11ef-0f85-ad1a0093e06acodemd"# La théorie des nombres"metadatashow_logsèdisabled®skip_as_script«code_folded$9207b107-e1b0-4328-a004-f4b8152b423fcell_id$9207b107-e1b0-4328-a004-f4b8152b423fcode-qa(md"**Observation clé** Si ``a > b``, trouver un mono-variant.",
md"""
On a ``(a, b) > (b, r)``. En effet, ``a > b`` par supposition et ``b > r`` par définition de l'algorithme d'Euclide.
Notons que même si la supposition ``a > b`` n'est pas vraie, elle le devient pour ``\text{gcd}(b, r)``.
""")metadatashow_logsèdisabled®skip_as_script«code_folded$65f4990f-1952-4682-8fa8-9e3dd4bf1ebfcell_id$65f4990f-1952-4682-8fa8-9e3dd4bf1ebfcode-@time pow_999 = fast_mod_power(2, power, 999)metadatashow_logsèdisabled®skip_as_script«code_folded$1b2245f8-2f02-4c4d-b6d2-e65af1f2a21ecell_id$1b2245f8-2f02-4c4d-b6d2-e65af1f2a21ecodemd"Last 3 digit:"metadatashow_logsèdisabled®skip_as_script«code_folded$eeaec4f4-71bd-43df-b9c9-a00bc3b1864bcell_id$eeaec4f4-71bd-43df-b9c9-a00bc3b1864bcodegcdx(gcd_a, gcd_b)metadatashow_logsèdisabled®skip_as_script«code_folded$ba16d83d-21a5-4f0c-807b-674a167da4dccell_id$ba16d83d-21a5-4f0c-807b-674a167da4dccodebiblio = load_biblio!()metadatashow_logsèdisabled®skip_as_script«code_folded$7bad8c6c-45c7-402f-ad59-6857e9268901cell_id$7bad8c6c-45c7-402f-ad59-6857e9268901codeVqa(md"Comment prouver que l'égalité ``ax + by = c`` implique que ``\text{gcd}(a, b)`` divise ``c`` ?",
md"""
Soit ``g = \text{gcd}(a, b)``. Par définition, il existe ``\alpha, \beta`` tels que ``a = \alpha g`` et ``b = \beta g``.
On a alors ``c = ax + by = (\alpha x + \beta y) g`` ce qui implique que ``c`` est un multiple de ``g``.
""",)metadatashow_logsèdisabled®skip_as_script«code_folded$21df1900-3954-4506-b759-aeeee664d1dfcell_id$21df1900-3954-4506-b759-aeeee664d1dfcodeAfunction modinv(a, n)
g, x, y = gcdx(a, n)
return mod(x, n)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$1072a756-5026-4de9-93a8-f942d54c474acell_id$1072a756-5026-4de9-93a8-f942d54c474acode@md"""Voir $(cite("hoffstein2014Introduction", "Section 2.7"))"""metadatashow_logsèdisabled®skip_as_script«code_folded$59254bfd-48f2-4585-9ba5-e4c809421072cell_id$59254bfd-48f2-4585-9ba5-e4c809421072code'shanks_x = shanks_discrete_log(3, g, p)metadatashow_logsèdisabled®skip_as_script«code_folded$f4f49568-dcf2-4c76-ba66-065d2fda7a4acell_id$f4f49568-dcf2-4c76-ba66-065d2fda7a4acodeٙmd"""
```math
a \equiv \alpha \pmod{n} \quad \text{et} \quad b \equiv \beta \pmod{n}
\quad \Rightarrow \quad a + b \equiv \alpha + \beta \pmod{n}
```
"""metadatashow_logsèdisabled®skip_as_script«code_folded$9752afbb-96e6-4f96-92cb-09654cf46155cell_id$9752afbb-96e6-4f96-92cb-09654cf46155codeqa(md"Est-ce que l'inverse modulaire existe toujours ?",
md"""
Par le théorème de Bézout, il existe si et seulement si ``\text{gcd}(a, n) \mid 1``, c'est à dire que ``\text{gcd}(a, n) = 1``.
""")metadatashow_logsèdisabled®skip_as_script«code_folded$e2a3842d-4e07-4703-ab47-a5140649dd6acell_id$e2a3842d-4e07-4703-ab47-a5140649dd6acodeunique(sort(all_powers))metadatashow_logsèdisabled®skip_as_script«code_folded$cbabee34-2ca2-4ad4-93ba-2ec3c941da5ecell_id$cbabee34-2ca2-4ad4-93ba-2ec3c941da5ecodedmd"""
Si tous les mois avaient 30 jours, est-ce qu'il y a des jours de la semaine qui ne seront jamais le premier du mois ?
Reformulation: pour tout nombre ``0 \le j < 7``, existe-t-il ``x`` et ``y`` tels que ``30x = j + 7y``. Notation modulo : ``30x \equiv j \pmod{7}``.
Si tous les ans avaient 365 jours, est-ce qu'il y a des jours de la semaine qui ne seront jamais le 25 Décembre ? Est si tous les ans avaient 366 jours ? Et s'ils avaient 364 jours ?
Reformulation: pour tout nombre ``0 \le j < 7``, existe-t-il ``x`` et ``y`` tels que ``365x = j + 7y``. Notation modulo : ``365x \equiv j \pmod{7}``.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$059b0ada-2442-48e4-82dd-489cb97e5dcccell_id$059b0ada-2442-48e4-82dd-489cb97e5dcccodegp_pickermetadatashow_logsèdisabled®skip_as_script«code_folded$027fe67c-d2f0-49f6-b894-959795551d27cell_id$027fe67c-d2f0-49f6-b894-959795551d27code@time fib_rec(42)metadatashow_logsèdisabled®skip_as_script«code_folded$83852dd5-3546-45af-a845-b01dab0aa2a6cell_id$83852dd5-3546-45af-a845-b01dab0aa2a6code+frametitle("Inverse et division modulaire")metadatashow_logsèdisabled®skip_as_script«code_folded$3df688c8-1c52-462d-88be-daa153333c60cell_id$3df688c8-1c52-462d-88be-daa153333c60codemd"""
* Théorie des nombres: $(cite("hoffstein2014Introduction", "1.2, 1.3, 1.4, 1.5, 2.2, 2.3"))
* Discrete Logarithme Problem et Diffie-Hellman: $(cite("hoffstein2014Introduction", "2.2, 2.3, 2.6, 2.7, 2.8"))
"""metadatashow_logsèdisabled®skip_as_script«code_folded$e9633e3f-376d-413d-bc19-d015f6ce76e5cell_id$e9633e3f-376d-413d-bc19-d015f6ce76e5codebig(2)^powermetadatashow_logsèdisabled®skip_as_script«code_folded$819f15ef-31d0-44b6-837a-e3e67f2667b9cell_id$819f15ef-31d0-44b6-837a-e3e67f2667b9codemd"Revenons aux exemples:"metadatashow_logsèdisabled®skip_as_script«code_folded$3f1af973-a02b-4e06-8e6e-eff414fcaf67cell_id$3f1af973-a02b-4e06-8e6e-eff414fcaf67codeٔfunction pgcdx(a, b)
if b == 0
return a, one(a), zero(a)
else
q, r = divrem(a, b)
g, x, y = pgcdx(b, r)
return g, y, x - y * q
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$4853f4ef-fbb8-48c3-9523-13ab4969d097cell_id$4853f4ef-fbb8-48c3-9523-13ab4969d097codezfunction baby_steps(g, n, p)
steps = [one(g)]
for i in 1:n
push!(steps, mod(steps[end] * g, p))
end
return steps
endmetadatashow_logsèdisabled®skip_as_script«code_folded$9722971a-16f1-4f28-ba31-c12b673b8a30cell_id$9722971a-16f1-4f28-ba31-c12b673b8a30codemd"Et modulo 999 ?"metadatashow_logsèdisabled®skip_as_script«code_folded$462fa407-d973-4e9e-8512-b7cd3bb98b7bcell_id$462fa407-d973-4e9e-8512-b7cd3bb98b7bcodezfunction fib_seq(n)
f = zeros(BigInt, n + 1)
f[2] = 1
for k in 2:n
f[k + 1] = f[k] + f[k - 1]
end
return f[end]
endmetadatashow_logsèdisabled®skip_as_script«code_folded$6e59ee60-ef73-45ca-86eb-4d8a44c73771cell_id$6e59ee60-ef73-45ca-86eb-4d8a44c73771code5qa(md"**Observation clé** Que dit le théorème de Bézout par rapport à ``\text{gcd}(a, d)`` et ``r``.",
md"""
Le reste ``r`` est **divisible** par ``\text{gcd}(a, d)``.
Le nombre ``\text{gcd}(a, d)`` divise donc les 3 nombres, ``a``, ``d`` et ``r`` et donc ``\text{gcd}(a, d) = \text{gcd}(a, d, r)``.
""")metadatashow_logsèdisabled®skip_as_script«code_folded$9efb7a71-9a03-4716-8d34-aae233e9b898cell_id$9efb7a71-9a03-4716-8d34-aae233e9b898codex = discrete_log(3, g, p)metadatashow_logsèdisabled®skip_as_script«code_folded$9b9fc5e6-1a41-43c5-ba43-2c93bc3ef66bcell_id$9b9fc5e6-1a41-43c5-ba43-2c93bc3ef66bcode@time fib_closed(20000)metadatashow_logsèdisabled®skip_as_script«code_folded$9cef898e-192c-418a-bec6-511f8b6da179cell_id$9cef898e-192c-418a-bec6-511f8b6da179code fast_mod_power(2, power, 999000)metadatashow_logsèdisabled®skip_as_script«code_folded$78df9410-5ea4-4d9f-bbe5-862f76a100fccell_id$78df9410-5ea4-4d9f-bbe5-862f76a100fccodeRmd"``30x \equiv j \pmod{7} \quad \Rightarrow \quad x \equiv (30)^{-1} j\pmod{7}``"metadatashow_logsèdisabled®skip_as_script«code_folded$31388128-33a3-4443-835e-74b91bf48268cell_id$31388128-33a3-4443-835e-74b91bf48268codemod(a + b, n)metadatashow_logsèdisabled®skip_as_script«code_folded$3cd40d9e-fcea-427d-9877-cea65e7ea413cell_id$3cd40d9e-fcea-427d-9877-cea65e7ea413code@time fib_seq(20000)metadatashow_logsèdisabled®skip_as_script«code_folded$7881bb75-3ef9-496e-860b-03ced6b593c5cell_id$7881bb75-3ef9-496e-860b-03ced6b593c5code@time big(2)^powermetadatashow_logsèdisabled®skip_as_script«code_folded$72ec8410-05d9-475a-93d4-47153cc0ce31cell_id$72ec8410-05d9-475a-93d4-47153cc0ce31codeJfib_rec(n) = (n == 0 ? 0 : (n == 1 ? 1 : fib_rec(n - 1) + fib_rec(n - 2)))metadatashow_logsèdisabled®skip_as_script«code_folded$41cf9efd-65e5-4abb-94d3-e824780e659ccell_id$41cf9efd-65e5-4abb-94d3-e824780e659ccode#refs(["hoffstein2014Introduction"])metadatashow_logsèdisabled®skip_as_script«code_folded$6cf004be-5205-429e-8131-ef607cebeaeccell_id$6cf004be-5205-429e-8131-ef607cebeaeccodeE.vectorsmetadatashow_logsèdisabled®skip_as_script«code_folded$8f6ba1c4-a971-4dc4-ac5d-2f30790aecdecell_id$8f6ba1c4-a971-4dc4-ac5d-2f30790aecdecode'frametitle("Fermat’s Little Theorem")metadatashow_logsèdisabled®skip_as_script«code_folded$fe2af566-4a8b-4052-9915-85266ee5ce98cell_id$fe2af566-4a8b-4052-9915-85266ee5ce98codepgcd(gcd_a, gcd_b)metadatashow_logsèdisabled®skip_as_script«code_folded$8a5a251f-5373-445a-97b1-4d652c6b7ba8cell_id$8a5a251f-5373-445a-97b1-4d652c6b7ba8code"refs(keys) = bibrefs(biblio, keys)metadatashow_logsèdisabled®skip_as_script«code_folded$708c442b-cbff-4e1a-b70d-e704453cfd3dcell_id$708c442b-cbff-4e1a-b70d-e704453cfd3dcode6HAlign(
md"""
Équation de récurrence:
```math
x_{k+1} = x_k + x_{k-1}
```
Reformulation sans ``(k-1)``
```math
\begin{align}
x_{k+1} & = x_k + y_{k}\\
y_{k+1} & = x_k
\end{align}
```
Forme matricielle:
```math
\begin{bmatrix}
x_{k+1}\\
y_{k+1}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
x_{k}\\
y_{k}
\end{bmatrix}
```
Matrix power:
```math
\begin{bmatrix}
x_n\\
y_n
\end{bmatrix}
=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
x_0\\
y_0
\end{bmatrix}
```
""",
md"""
`n` = $(fib_picker)\
$(draw_fib(fib_n))
""",
)metadatashow_logsèdisabled®skip_as_script«code_folded$1a4da418-147f-46f4-9b95-7955183aa5cfcell_id$1a4da418-147f-46f4-9b95-7955183aa5cfcodeZmd"`gcd_a` = $(@bind gcd_a Slider(1:typemax(Int32), default=90284599, show_value = true))"metadatashow_logsèdisabled®skip_as_script«code_folded$ed023033-1044-4d48-aab1-39e9300043f7cell_id$ed023033-1044-4d48-aab1-39e9300043f7codemd"""
**Fermat's little theorem** $(cite("hoffstein2014Introduction", "Theorem 1.24"))
```math
\text{Si} \quad p \text{ est premier}\quad \text{et} \quad p \nmid g,\quad \text{alors} \quad
g^{p - 1} \equiv 1 \pmod{p}.
```
"""metadatashow_logsèdisabled®skip_as_script«code_folded$eb311761-ace2-4632-9ebf-9c7c166659f7cell_id$eb311761-ace2-4632-9ebf-9c7c166659f7codeJmd"""
```math
A' \equiv B^a \pmod{p} \qquad B' \equiv A^b \pmod{p}
```
"""metadatashow_logsèdisabled®skip_as_script«code_folded$f86a5efc-d31e-4e88-b81f-ebdbbeba11eccell_id$f86a5efc-d31e-4e88-b81f-ebdbbeba11eccodemd"""
On doit donc trouver la ligne ``i`` et la ligne et ``j`` tels que
```math
\begin{align}
g^{i-1}g^{(j-1)n} & \equiv a & \pmod{p}\\
g^{i-1} & \equiv a(g^{-n})^{j-1} & \pmod{p}
\end{align}
```
Ils ne reste plus qu'à chercher une collision entre les listes de restes modulo ``p`` pour ``g^{i-1}`` et ``a(g^{-n})^{j-1}``.
L'identification des collision peut se faire en ``\mathcal{O}(\sqrt{n}\log(n))`` avec une recherche dichotomique our en ``\mathcal{O}(\sqrt{n})`` amorti avec un dictionaire.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$a7d9703a-5121-4b43-8cd4-2acf9a0d91efcell_id$a7d9703a-5121-4b43-8cd4-2acf9a0d91efcode٢md"""
La méthode *meet in the middle* est une méthode générique permettant de passer d'une complexité de ``\mathcal{O}(N)`` à ``\mathcal{O}(\sqrt{N})``.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$9e8a61d9-a700-4851-b1cd-49ce042c3530cell_id$9e8a61d9-a700-4851-b1cd-49ce042c3530code@time big(2)^powermetadatashow_logsèdisabled®skip_as_script«code_folded$c376513c-6553-4cd6-8384-ae6ff9d472d7cell_id$c376513c-6553-4cd6-8384-ae6ff9d472d7codeHmd"""
```math
A \equiv g^a \pmod{p} \qquad B \equiv g^b \pmod{p}
```
"""metadatashow_logsèdisabled®skip_as_script«code_folded$38744170-9af6-44b5-a0be-46a83da3253ecell_id$38744170-9af6-44b5-a0be-46a83da3253ecodeRfunction fib_pow(n)
A = BigInt[1 1
1 0]
x = A^(n-1) * [1, 0]
return x[1]
endmetadatashow_logsèdisabled®skip_as_script«code_folded$a1081bb2-2186-4b19-b667-0c246155f360cell_id$a1081bb2-2186-4b19-b667-0c246155f360code@time fib_pow(20000)metadatashow_logsèdisabled®skip_as_script«code_folded$4ef2c7e9-fb37-4e38-a252-b9c3f83d2a82cell_id$4ef2c7e9-fb37-4e38-a252-b9c3f83d2a82codeabn_pickermetadatashow_logsèdisabled®skip_as_script«code_folded$93aa2719-f962-497b-9fda-30f54fd848ebcell_id$93aa2719-f962-497b-9fda-30f54fd848ebcode(collect(mod.(modinv(30, 7) .* (0:6), 7))metadatashow_logsèdisabled®skip_as_script«code_folded$77093b36-c232-4477-be49-845f1a631829cell_id$77093b36-c232-4477-be49-845f1a631829code/@time pow_1000 = fast_mod_power(2, power, 1000)metadatashow_logsèdisabled®skip_as_script«code_folded$d6b89fda-308f-43da-8028-1a812b4516cfcell_id$d6b89fda-308f-43da-8028-1a812b4516cfcodeqa(md"**Observation clé** Que dit le théorème de Bézout par rapport à ``\text{gcd}(d, r)`` et ``a``.",
md"""
Le nombre ``a`` est **divisible** par ``\text{gcd}(d, r)``.
Le nombre ``\text{gcd}(d, r)`` divise donc les 3 nombres, ``a``, ``d`` et ``r`` et donc ``\text{gcd}(d, r) = \text{gcd}(a, d, r)``.
En combinant ça avec l'observation précédente, on a ``\text{gcd}(a, d) = \text{gcd}(d, r)``. On peut généraliser cela en le lemme suivant:
""")metadatashow_logsèdisabled®skip_as_script«code_foldedënotebook_id$63242826-d9c7-11f0-9e6a-e7ac83805cf9bondscell_results $d882afdd-eb85-467c-bf18-525c0c5da5e7queued¤logslinemsg/ 0.000065 seconds (39 allocations: 2.609 KiB)
text/plaincell_id$d882afdd-eb85-467c-bf18-525c0c5da5e7kwargsidPlutoRunner_d1acb81efileP/home/runner/.julia/packages/Pluto/CBqeh/src/runner/PlutoRunner/src/io/stdout.jlgroupstdoutlevelLogLevel(-555)running¦outputbodyV2.531162323732361578998428490601662084769270923897910687031954402219719762339543e+4179persist_js_state¤mimetext/plainlast_run_timestampAPܷhas_pluto_hook_features¬rootassigneecell_id$d882afdd-eb85-467c-bf18-525c0c5da5e7depends_on_disabled_cells§runtime #.published_object_keysdepends_on_skipped_cells§errored$1b1d5c9b-5fc7-480e-9649-e9c44a49c38dqueued¤logsrunning¦outputbody$qa (generic function with 2 methods)persist_js_state¤mimetext/plainlast_run_timestampAPYhas_pluto_hook_features¬rootassigneecell_id$1b1d5c9b-5fc7-480e-9649-e9c44a49c38ddepends_on_disabled_cells§runtime 6published_object_keysdepends_on_skipped_cells§errored$4cb070de-e8bf-4a1d-9625-043c19466c46queued¤logslinemsg5 0.000295 seconds (1.93 k allocations: 208.766 KiB)
text/plaincell_id$4cb070de-e8bf-4a1d-9625-043c19466c46kwargsidPlutoRunner_d1acb81efileP/home/runner/.julia/packages/Pluto/CBqeh/src/runner/PlutoRunner/src/io/stdout.jlgroupstdoutlevelLogLevel(-555)running¦outputbodyT2531162323732361242240155003520607291766356485802485278951929841991312781760541315230153423463758831637443488219211037689033673531462742885329724071555187618026931630449193158922771331642302030331971098689235780843478258502779200293635651897483309686042860996364443514558772156043691404155819572984971754278513112487985892718229593329483578531419148805380281624260900362993556916638613939977074685016188258584312329139526393558096840812970422952418558991855772306882442574855589237165219912238201311184749075137322987656049866305366913734924425822681338966507463855180236283582409861199212323835947891143765414913345008456022009455704210891637791911265475167769704477334859109822590053774932978465651023851447920601310106288957894301592502061560528131203072778677491443420921822590709910448617329156135355464620891788459566081572824889514296350670950824208245170667601726417091127999999941149913010424532046881958285409468463211897582215075436515584016297874572183907949257286261608612401379639484713101138120404671732190451327881433201025184027541696124114463488665359385870910331476156665889459832092710304159637019707297988417848767011085425271875588008671422491434005115288334343837778792282383576736341414410248994081564830202363820504190074504566612515965134665683289356188727549463732830075811851574961558669278847363279870595320099844676879457196432535973357128305390290471349480258751812890314779723508104229525161740643984423978659638233074463100366500571977234508464710078102581304823235436518145074482824812996511614161933313389889630935320139507075992100561077534028207257574257706278201308302642634678112591091843082665721697117838726431766741158743554298864560993255547608496686850185804659790217122426535133253371422250684486113457341827911625517128815447325958547912113242367201990672230681308819195941016156001961954700241576553750737681552256845421159386858399433450045903975167084252876848848085910156941603293424067793097271128806817514906531652407763118308162377033463203514657531210413149191213595455280387631030665594589183601575340027172997222489081631144728873621805528648768511368948639522975539046995395707688938978847084621586473529546678958226255042389998718141303055036060772003887773038422366913820397748550793178167220193346017430024134496141145991896227741842515718997898627269918236920453493946658273870473264523119133765447653295022886429174942653014656521909469613184983671431465934965489425515981067546087342348350724207583544436107294087637975025147846254526938442435644928231027868701394819091132912397475713787593612758364812687556725146456646878912169274219209708166678668152184941578590201953144030519381922273252666652671717526318606676754556170379350956342095455612780202199922615392785572481747913435560866995432578680971243966868110016581395696310922519803685837460795358384618017215468122880442252343684547233668502313239328352671318130604247460452134121833305284398726438573787798499612760939462427922917659263046333084007208056631996856315539698234022953452211505675629153637867252695056925345220084020071611220575700841268302638995272842160994219632684575364180160991884885091858259996299627148614456696661412745040519981575543804847463997422326563897043803732970397488471644906183310144691243649149542394691524972023935190633672827306116525712882959108434211652465621144702015336657459532134026915214509960877430595844287585350290234547564574848753110281101545931547225811763441710217452979668178025286460158324658852904105792472468108996135476637212057508192176910900422826969523438985332067597093454021924077101784215936539638808624420121459718286059401823614213214326004270471752802725625810953787713898846144256909835116371235019527013180204030167601567064268573820697948868982630904164685161783088076506964317303709708574052747204405282785965604677674192569851918643651835755242670293612851920696732320545562286110332140065912751551110134916256237884844001366366654055079721985816714803952429301558096968202261698837096090377863017797020488044826628817462866854321356787305635653577619877987998113667928954840972022833505708587561902023411398915823487627297968947621416912816367516125096563705174220460639857683971213093125persist_js_state¤mimetext/plainlast_run_timestampAP8ڷhas_pluto_hook_features¬rootassigneecell_id$4cb070de-e8bf-4a1d-9625-043c19466c46depends_on_disabled_cells§runtime Mpublished_object_keysdepends_on_skipped_cells§errored$aee611f2-bc86-4e85-bbcb-add78c6a9175queued¤logsrunning¦outputbodyelements1text/plain89932200text/plain-32561659text/plainobjectid54a1c5b46a9f8dc9typeTuplepersist_js_state¤mime!application/vnd.pluto.tree+objectlast_run_timestampAP\has_pluto_hook_features¬rootassigneecell_id$aee611f2-bc86-4e85-bbcb-add78c6a9175depends_on_disabled_cells§runtime3ʵpublished_object_keysdepends_on_skipped_cells§errored$5c6c45b4-67e3-4ea8-bc09-0205ab24cbc3queued¤logsrunning¦outputbody3persist_js_state¤mimetext/plainlast_run_timestampAPF4has_pluto_hook_features¬rootassigneecell_id$5c6c45b4-67e3-4ea8-bc09-0205ab24cbc3depends_on_disabled_cells§runtime;ĵpublished_object_keysdepends_on_skipped_cells§errored$6c3595d2-4f68-44da-90e7-dc9c68479bcfqueued¤logsrunning¦outputbody%cite (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAP˷has_pluto_hook_features¬rootassigneecell_id$6c3595d2-4f68-44da-90e7-dc9c68479bcfdepends_on_disabled_cells§runtime }published_object_keysdepends_on_skipped_cells§errored$cd481f6c-66f4-4ebf-9769-c3edc24f403bqueued¤logsrunning¦outputbodyz
Définition Le résultat de la division Euclidienne de $a$ par un diviseur $d$ est un quotient $q$ et un reste $0 \le r < d$ tels que $a = qd + r$. En notation modulaire $a \equiv r \pmod{d}$.
persist_js_state¤mimetext/htmllast_run_timestampAPhas_pluto_hook_features¬rootassigneecell_id$37585789-bd43-4ce5-b550-ad712b70d226depends_on_disabled_cells§runtime $2published_object_keysdepends_on_skipped_cells§errored$4a98507b-653e-4354-a825-7605f8fcb31bqueued¤logsrunning¦outputbodyK4×4 Matrix{Int64}:
1 16 1 16
2 15 2 15
4 13 4 13
8 9 8 9persist_js_state¤mimetext/plainlast_run_timestampAP;has_pluto_hook_features¬rootassigneecell_id$4a98507b-653e-4354-a825-7605f8fcb31bdepends_on_disabled_cells§runtime
еpublished_object_keysdepends_on_skipped_cells§errored$bcf73ad7-a08b-4cbb-bcd2-d0abc002e7e2queued¤logsrunning¦outputbodyAQuelle est la complexité spatiale et temporelle de discrete_log ?
$\mathcal{O}(p)$ temporelle et $\Omega(1)$ spatiale. Voir [HPS14; Proposition 2.19].
persist_js_state¤mimetext/htmllast_run_timestampAP9has_pluto_hook_features¬rootassigneecell_id$c2fab245-8a98-4b41-ade2-c5b16e9c39f9depends_on_disabled_cells§runtime&
published_object_keysdepends_on_skipped_cells§errored$535f4bc1-e88c-47c7-990b-e3c8b5054accqueued¤logsrunning¦outputbody+fib_closed (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAPۍ
has_pluto_hook_features¬rootassigneecell_id$535f4bc1-e88c-47c7-990b-e3c8b5054accdepends_on_disabled_cells§runtime Mxpublished_object_keysdepends_on_skipped_cells§errored$6107d03d-1e45-4eb9-b8e2-51e4a72485e6queued¤logsrunning¦outputbody\
Si on avait les coefficients $x$ et $y$ tels que $xa + yn = 1$, l'inverse serait $x$. Dans l'algorithme d'Euclide, on ne garde que le reste et on oublie le quotient. Il faudrait combiner les quotients des différentes opérations pour trouver $x$.
persist_js_state¤mimetext/htmllast_run_timestampAP'has_pluto_hook_features¬rootassigneegp_pickercell_id$0e3fb524-bea1-4ef0-9589-36230a84e949depends_on_disabled_cells§runtime ʳpublished_object_keysdepends_on_skipped_cells§errored$a7d06375-e4dd-47b1-8aba-11dc4d62954bqueued¤logsrunning¦outputbodyfSupposons que $m$ est pair, c'est à dire $m = 2k$...
On a $a^(2k) = (a^k)^2$. Si $b = a^k$, on calcule le produit $b \times b$.
S'il y avait 364 jours par ans, les fêtes seraient toujours le même jour de la semaine!
persist_js_state¤mimetext/htmllast_run_timestampAPhas_pluto_hook_features¬rootassigneecell_id$bbb2793a-faa4-43bd-b2e8-e8d3ac93310fdepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$7330af43-bec3-460c-94f6-768ac2975b00queued¤logsrunning¦outputbody4shanks_discrete_log (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAP
.Ihas_pluto_hook_features¬rootassigneecell_id$7330af43-bec3-460c-94f6-768ac2975b00depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$67093a35-8e1b-4cd3-b11b-c7ff601f802equeued¤logsrunning¦outputbody
primes_upper =
persist_js_state¤mimetext/htmllast_run_timestampAPEffhas_pluto_hook_features¬rootassigneecell_id$67093a35-8e1b-4cd3-b11b-c7ff601f802edepends_on_disabled_cells§runtime Lpublished_object_keysdepends_on_skipped_cells§errored$48eba223-6cce-4aa2-9977-4883ba7903fcqueued¤logsrunning¦outputbodyObservation finale Si $a$ et $b$ sont positifs et qu'on effectue la substitution $(a, b) \to (b, r)$ récursivement, le mono-variant impose qu'on ne puisse itérer qu'un nombre fini de fois, que va-t-il se passer ?
La paire $(a, b)$ va diminuer strictement (c'est à dire d'au moins 1) à chaque itération. Pourtant, ce sont des nombres entier positifs donc ils ne peuvent diminuer strictement qu'un nombre fini de fois. C'est une contradiction, comme cela se fait-il ? À un moment $b$ vaudra 0, on ne pourra alors plus faire de division Euclidienne. On utilisera alors le fait que $\text{gcd}(a, 0) = a$.
persist_js_state¤mimetext/htmllast_run_timestampAPhas_pluto_hook_features¬rootassigneecell_id$82ba8fe1-435e-422b-abb7-cb50a7a85e1edepends_on_disabled_cells§runtime2̵published_object_keysdepends_on_skipped_cells§errored$61462af5-69bd-42be-8918-7992c79ee00dqueued¤logsrunning¦outputbodyCComment savoir si prime_list contient assez de nombres pour avoir la bonne réponse ?
On a la bonne réponse modulo prod(prime_list) donc si prod(prime_list) > 2^power, on a la bonne réponse.
persist_js_state¤mimetext/htmllast_run_timestampAPOHܷhas_pluto_hook_features¬rootassigneecell_id$61462af5-69bd-42be-8918-7992c79ee00ddepends_on_disabled_cells§runtime rXpublished_object_keysdepends_on_skipped_cells§errored$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fdqueued¤logsrunning¦outputbody3persist_js_state¤mimetext/plainlast_run_timestampAPC2has_pluto_hook_features¬rootassigneecell_id$ab467d70-ceb1-40e5-b8fe-82e2f1bd95fddepends_on_disabled_cells§runtime)Ipublished_object_keysdepends_on_skipped_cells§errored$57816e2c-a675-43e7-b674-2877ffcf1415queued¤logsrunning¦outputbodypersist_js_state¤mimetext/htmllast_run_timestampAP鸷has_pluto_hook_features¬rootassigneep_pickercell_id$57816e2c-a675-43e7-b674-2877ffcf1415depends_on_disabled_cells§runtimeRpublished_object_keysdepends_on_skipped_cells§errored$16b677e4-c467-462a-b770-b7a31160e129queued¤logsrunning¦outputbodyelements 3text/plain5text/plain7text/plain11text/plain13text/plain17text/plain19text/plain23text/plain 29text/plain
31text/plain 37text/plain 41text/plain
43text/plain47text/plain53text/plain59text/plain61text/plain67text/plain71text/plain73text/plain79text/plain83text/plain89text/plain97text/plainprefix_shortobjectidba8255a72db8c2ffprefixInt64typeArraypersist_js_state¤mime!application/vnd.pluto.tree+objectlast_run_timestampAPOhas_pluto_hook_features¬rootassigneeprime_listcell_id$16b677e4-c467-462a-b770-b7a31160e129depends_on_disabled_cells§runtime@published_object_keysdepends_on_skipped_cells§errored$6e5e3ec6-c96a-4a4a-bf4d-4b115f9b0d82queued¤logsrunning¦outputbody*collision (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAPhas_pluto_hook_features¬rootassigneecell_id$6e5e3ec6-c96a-4a4a-bf4d-4b115f9b0d82depends_on_disabled_cells§runtime 7published_object_keysdepends_on_skipped_cells§errored$6332b2f2-ed2f-448a-b1df-247b110e335bqueued¤logsrunning¦outputbody5Que faire si que $m$ est impair, c'est à dire $m = 2k + 1$...
Si $b = a^(2k)$, calcule le produit $b \times a$.
persist_js_state¤mimetext/htmllast_run_timestampAP%has_pluto_hook_features¬rootassigneecell_id$6332b2f2-ed2f-448a-b1df-247b110e335bdepends_on_disabled_cells§runtime Jpublished_object_keysdepends_on_skipped_cells§errored$3c198d79-c46a-4781-8bd1-b6b68f06c31fqueued¤logslinemsgN 0.007587 seconds (3.41 k allocations: 161.203 KiB, 99.47% compilation time)
text/plaincell_id$3c198d79-c46a-4781-8bd1-b6b68f06c31fkwargsidPlutoRunner_d1acb81efileP/home/runner/.julia/packages/Pluto/CBqeh/src/runner/PlutoRunner/src/io/stdout.jlgroupstdoutlevelLogLevel(-555)running¦outputbodyL3618502788666131106986593281521497120414687020801267626233049500247285301248persist_js_state¤mimetext/plainlast_run_timestampAPhas_pluto_hook_features¬rootassigneecell_id$3c198d79-c46a-4781-8bd1-b6b68f06c31fdepends_on_disabled_cells§runtime npublished_object_keysdepends_on_skipped_cells§errored$d830fffd-3781-40ca-85cb-c242f99667cequeued¤logsrunning¦outputbody)fib_diag (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAP]has_pluto_hook_features¬rootassigneecell_id$d830fffd-3781-40ca-85cb-c242f99667cedepends_on_disabled_cells§runtime M)published_object_keysdepends_on_skipped_cells§errored$8b16a522-9be4-4286-b64d-3d1bbdef7142queued¤logsrunning¦outputbody
Étant donné un nombre premier $p$ et une racine primitive $g$ modulo $p$ et un entier $a$ tel que $p \nmid a$, le Discrete logarithme problem consiste à retrouver $x$ tel que $g^x \equiv a \pmod{p}$.
persist_js_state¤mimetext/htmllast_run_timestampAP
_has_pluto_hook_features¬rootassigneecell_id$6c3bca1a-3109-4e48-97e1-e0ed4599ffb2depends_on_disabled_cells§runtime/*published_object_keysdepends_on_skipped_cells§errored$a59a20e2-a7c7-48a9-ad8d-8094e03a749dqueued¤logsrunning¦outputbodyelements0text/plain1text/plain2text/plain3text/plain4text/plain5text/plain6text/plainprefix_shortobjectid7e4b9ecc34765b1bprefixInt64typeArraypersist_js_state¤mime!application/vnd.pluto.tree+objectlast_run_timestampAP#Khas_pluto_hook_features¬rootassigneecell_id$a59a20e2-a7c7-48a9-ad8d-8094e03a749ddepends_on_disabled_cells§runtime{published_object_keysdepends_on_skipped_cells§errored$06679a09-47d7-4024-8232-4954c08747a0queued¤logsrunning¦outputbodypersist_js_state¤mimetext/plainlast_run_timestampAPRhas_pluto_hook_features¬rootassigneecell_id$06679a09-47d7-4024-8232-4954c08747a0depends_on_disabled_cells§runtime%published_object_keysdepends_on_skipped_cells§errored$58da5ba4-c858-4684-a9f4-5a39fdc4fb03queued¤logsrunning¦outputbody+fast_power (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAP.\}has_pluto_hook_features¬rootassigneecell_id$58da5ba4-c858-4684-a9f4-5a39fdc4fb03depends_on_disabled_cells§runtime
published_object_keysdepends_on_skipped_cells§errored$a7afc0cb-a980-4f4f-b782-9791d932ee52queued¤logsrunning¦outputbodyF
Par l'algo d'Euclide, $\text{gcd}(n, n - 1) = 1$ donc $\text{gcd}(1000, 999) = 1$.
persist_js_state¤mimetext/htmllast_run_timestampAP\Shas_pluto_hook_features¬rootassigneecell_id$6ed7c73d-60da-4908-85cb-958745d81ebcdepends_on_disabled_cells§runtime Ɔpublished_object_keysdepends_on_skipped_cells§errored$bc9a718f-4b97-4e15-acf8-d180abc5b6d5queued¤logsrunning¦outputbodyEst-ce une complexité linéaire ou exponentielle en fonction de la taille de l'input
La taille est proportionnelle à $\log_2(p)$ donc on être linéaire en $p$ c'est être proportionnel à $2^{\log_2(p)}$ et donc la complexité est exponentielle en la taille de l'input ! [HPS14; Section 2.6]
persist_js_state¤mimetext/htmllast_run_timestampAP4߷has_pluto_hook_features¬rootassigneecell_id$bc9a718f-4b97-4e15-acf8-d180abc5b6d5depends_on_disabled_cells§runtime vpublished_object_keysdepends_on_skipped_cells§errored$ec14d629-b720-47cd-bc08-ff96f49271abqueued¤logsrunning¦outputbody-discrete_log (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAP鍤has_pluto_hook_features¬rootassigneecell_id$ec14d629-b720-47cd-bc08-ff96f49271abdepends_on_disabled_cells§runtime 6published_object_keysdepends_on_skipped_cells§errored$d1b260fb-7500-47fb-bb48-21b5857ab55aqueued¤logsrunning¦outputbody
Lemme: Si $a \equiv r \pmod{b}$ alors $\text{gcd}(a, b) = \text{gcd}(b, r)$.
Étant donné un nombre premier $p$ et une racine primitive $g$ modulo $p$, Alice (resp. Bob) génère un nombre secret $a$ (resp. $b$). Ils communique ensuite publiquement $A$ et $B$.
Définition Le Greatest Common Divisor (GCD) de deux nombres $a \in \mathbb{Z}$ et $b \in \mathbb{Z}$, noté $\text{gcd}(a, b)$ est le plus grand nombre $g \in \mathbb{Z}$ qui divise $a$ (noté $g \mid a$) et $b$ (noté $g \mid b$). C'est à dire qu'il existe $x \in \mathbb{Z}$ tel que $a = gx$ et $y \in \mathbb{Z}$ tel que $b = gy$. En notation modulaire, $a \equiv 0 \pmod{g}$ et $b \equiv 0 \pmod{g}$.
Théorème de Bézout Il existe $x, y \in \mathbb{Z}$ tels que $ax + by = c$ si et seulement si $\text{gcd}(a, b)$ divise $c$. En notation modulaire $ax \equiv c \pmod{b}$ et $by \equiv c \pmod{a}$.
persist_js_state¤mimetext/htmllast_run_timestampAPumhas_pluto_hook_features¬rootassigneecell_id$08b18315-c28e-44ed-beb2-5b17421b0224depends_on_disabled_cells§runtime 7published_object_keysdepends_on_skipped_cells§errored$8670abc2-63e6-496a-b20c-812197acd9adqueued¤logsrunning¦outputbody/fast_mod_power (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAP6Xhas_pluto_hook_features¬rootassigneecell_id$8670abc2-63e6-496a-b20c-812197acd9addepends_on_disabled_cells§runtime
uZpublished_object_keysdepends_on_skipped_cells§errored$18031ccb-657f-409a-9080-9a0ada3ae8b5queued¤logsrunning¦outputbodypersist_js_state¤mimetext/htmllast_run_timestampAP>has_pluto_hook_features¬rootassigneeslider_bcell_id$18031ccb-657f-409a-9080-9a0ada3ae8b5depends_on_disabled_cells§runtime Zpublished_object_keysdepends_on_skipped_cells§errored$4714b7d7-32ee-42a1-bfa5-93eafda739d3queued¤logsrunning¦outputbodyt
persist_js_state¤mimetext/htmllast_run_timestampAPշhas_pluto_hook_features¬rootassigneecell_id$7da0705e-c925-4f8d-9ca4-8d8a0f859feadepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$227e415e-ab17-4f3a-b695-9573c9ee2b57queued¤logsrunning¦outputbodyWhat is the relation between $A'$ and $B'$ ?
$$A' \equiv (g^b)^a \equiv g^{ab} \equiv (g^{a})^b \equiv B' \pmod{p}$$
Alice et Bob ont donc maintenant la même clef! Il est cependant difficile de trouver $A'$ depuis $A$ et $B$ sans connaitre les secrets $a$ ou $b$ si le Discrete Logarithm Problem est difficile.
persist_js_state¤mimetext/htmllast_run_timestampAP!has_pluto_hook_features¬rootassigneecell_id$d81bbd74-42df-4bb2-a045-9c2642cc19e5depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$1e27eedc-5308-4608-863f-fb81d60acdf0queued¤logsrunning¦outputbodyٿQuelle est la complexité?
persist_js_state¤mimetext/htmllast_run_timestampAP= has_pluto_hook_features¬rootassigneecell_id$ee43c389-55f4-4cf9-a8db-ce37d1b89db4depends_on_disabled_cells§runtime3published_object_keysdepends_on_skipped_cells§errored$f6e22fc3-382e-4548-bc59-8f944e06d237queued¤logsrunning¦outputbody32×2 Matrix{Float64}:
1.0 1.0
1.0 -1.11022e-16persist_js_state¤mimetext/plainlast_run_timestampAPhas_pluto_hook_features¬rootassigneecell_id$f6e22fc3-382e-4548-bc59-8f944e06d237depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$8315b53f-abca-483d-bbf6-7e9193e751c9queued¤logsrunning¦outputbody*draw_fib (generic function with 2 methods)persist_js_state¤mimetext/plainlast_run_timestampAP/shas_pluto_hook_features¬rootassigneecell_id$8315b53f-abca-483d-bbf6-7e9193e751c9depends_on_disabled_cells§runtime
Njpublished_object_keysdepends_on_skipped_cells§errored$3026f9c5-81d3-443a-940a-f22fef9754afqueued¤logsrunning¦outputbody,giant_steps (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAP<has_pluto_hook_features¬rootassigneecell_id$3026f9c5-81d3-443a-940a-f22fef9754afdepends_on_disabled_cells§runtime 0published_object_keysdepends_on_skipped_cells§errored$87fdefa1-3bbd-4b69-ad3a-72baca6e55eequeued¤logsrunning¦outputbody4persist_js_state¤mimetext/plainlast_run_timestampAPDlhas_pluto_hook_features¬rootassigneecell_id$87fdefa1-3bbd-4b69-ad3a-72baca6e55eedepends_on_disabled_cells§runtime
persist_js_state¤mimetext/htmllast_run_timestampAP/X has_pluto_hook_features¬rootassigneecell_id$59817f59-429b-4f17-a46a-185571fd1e5adepends_on_disabled_cells§runtime"published_object_keysdepends_on_skipped_cells§errored$a4698418-ebf7-4992-a3ba-a15ff282bf87queued¤logsrunning¦outputbodyPQuelle est la complexité temporelle ?
Si $n$ est impair, au coup suivant, il est pair donc il n'est impair qu'au pire une fois sur deux. En $l$ multiplication, on divise $m$ au moins par $2^{l/2}$ donc on a une complexité logarithmique $\Theta(\log(m))$ en supposant que prod_func a une complexité $\Theta(1)$.
persist_js_state¤mimetext/htmllast_run_timestampAP yhas_pluto_hook_features¬rootassigneecell_id$736307ec-a2a4-11ef-0f85-ad1a0093e06adepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$9207b107-e1b0-4328-a004-f4b8152b423fqueued¤logsrunning¦outputbody7Observation clé Si $a > b$, trouver un mono-variant.
On a $(a, b) > (b, r)$. En effet, $a > b$ par supposition et $b > r$ par définition de l'algorithme d'Euclide. Notons que même si la supposition $a > b$ n'est pas vraie, elle le devient pour $\text{gcd}(b, r)$.
persist_js_state¤mimetext/htmllast_run_timestampAP0has_pluto_hook_features¬rootassigneecell_id$1b2245f8-2f02-4c4d-b6d2-e65af1f2a21edepends_on_disabled_cells§runtime "published_object_keysdepends_on_skipped_cells§errored$eeaec4f4-71bd-43df-b9c9-a00bc3b1864bqueued¤logsrunning¦outputbodyelements1text/plain89932200text/plain-32561659text/plainobjectid54a1c5b46a9f8dc9typeTuplepersist_js_state¤mime!application/vnd.pluto.tree+objectlast_run_timestampAP has_pluto_hook_features¬rootassigneecell_id$eeaec4f4-71bd-43df-b9c9-a00bc3b1864bdepends_on_disabled_cells§runtime#published_object_keysdepends_on_skipped_cells§errored$ba16d83d-21a5-4f0c-807b-674a167da4dcqueued¤logslinemsgXLoading bibliography from `/home/runner/work/LSINC1113/LSINC1113/Lectures/biblio.bib`...text/plaincell_id$ba16d83d-21a5-4f0c-807b-674a167da4dckwargsidMain_workspace#3_bb783fd7file7/home/runner/work/LSINC1113/LSINC1113/Lectures/utils.jlgrouputilslevelInfolinemsg=Entry west2022Introduction is missing the publisher field(s).text/plaincell_id$ba16d83d-21a5-4f0c-807b-674a167da4dckwargsidBibInternal_c5a7ae9dfileComment prouver que l'égalité $ax + by = c$ implique que $\text{gcd}(a, b)$ divise $c$ ?
Soit $g = \text{gcd}(a, b)$. Par définition, il existe $\alpha, \beta$ tels que $a = \alpha g$ et $b = \beta g$. On a alors $c = ax + by = (\alpha x + \beta y) g$ ce qui implique que $c$ est un multiple de $g$.
persist_js_state¤mimetext/htmllast_run_timestampAPfohas_pluto_hook_features¬rootassigneecell_id$7bad8c6c-45c7-402f-ad59-6857e9268901depends_on_disabled_cells§runtime [&published_object_keysdepends_on_skipped_cells§errored$21df1900-3954-4506-b759-aeeee664d1dfqueued¤logsrunning¦outputbody'modinv (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAP has_pluto_hook_features¬rootassigneecell_id$21df1900-3954-4506-b759-aeeee664d1dfdepends_on_disabled_cells§runtime
ɵpublished_object_keysdepends_on_skipped_cells§errored$1072a756-5026-4de9-93a8-f942d54c474aqueued¤logsrunning¦outputbodyE
$$a \equiv \alpha \pmod{n} \quad \text{et} \quad b \equiv \beta \pmod{n}
\quad \Rightarrow \quad a + b \equiv \alpha + \beta \pmod{n}$$
persist_js_state¤mimetext/htmllast_run_timestampAPؐhas_pluto_hook_features¬rootassigneecell_id$f4f49568-dcf2-4c76-ba66-065d2fda7a4adepends_on_disabled_cells§runtime Fpublished_object_keysdepends_on_skipped_cells§errored$9752afbb-96e6-4f96-92cb-09654cf46155queued¤logsrunning¦outputbody[Est-ce que l'inverse modulaire existe toujours ?
Par le théorème de Bézout, il existe si et seulement si $\text{gcd}(a, n) \mid 1$, c'est à dire que $\text{gcd}(a, n) = 1$.
Si tous les mois avaient 30 jours, est-ce qu'il y a des jours de la semaine qui ne seront jamais le premier du mois ?
Reformulation: pour tout nombre $0 \le j < 7$, existe-t-il $x$ et $y$ tels que $30x = j + 7y$. Notation modulo : $30x \equiv j \pmod{7}$.
Si tous les ans avaient 365 jours, est-ce qu'il y a des jours de la semaine qui ne seront jamais le 25 Décembre ? Est si tous les ans avaient 366 jours ? Et s'ils avaient 364 jours ?
Reformulation: pour tout nombre $0 \le j < 7$, existe-t-il $x$ et $y$ tels que $365x = j + 7y$. Notation modulo : $365x \equiv j \pmod{7}$.
persist_js_state¤mimetext/htmllast_run_timestampAPܷhas_pluto_hook_features¬rootassigneecell_id$819f15ef-31d0-44b6-837a-e3e67f2667b9depends_on_disabled_cells§runtime mpublished_object_keysdepends_on_skipped_cells§errored$3f1af973-a02b-4e06-8e6e-eff414fcaf67queued¤logsrunning¦outputbody&pgcdx (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAP֡has_pluto_hook_features¬rootassigneecell_id$3f1af973-a02b-4e06-8e6e-eff414fcaf67depends_on_disabled_cells§runtime ]published_object_keysdepends_on_skipped_cells§errored$4853f4ef-fbb8-48c3-9523-13ab4969d097queued¤logsrunning¦outputbody+baby_steps (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAPhas_pluto_hook_features¬rootassigneecell_id$4853f4ef-fbb8-48c3-9523-13ab4969d097depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$9722971a-16f1-4f28-ba31-c12b673b8a30queued¤logsrunning¦outputbody3
Et modulo 999 ?
persist_js_state¤mimetext/htmllast_run_timestampAPFhas_pluto_hook_features¬rootassigneecell_id$9722971a-16f1-4f28-ba31-c12b673b8a30depends_on_disabled_cells§runtime Dpublished_object_keysdepends_on_skipped_cells§errored$462fa407-d973-4e9e-8512-b7cd3bb98b7bqueued¤logsrunning¦outputbody(fib_seq (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAPShas_pluto_hook_features¬rootassigneecell_id$462fa407-d973-4e9e-8512-b7cd3bb98b7bdepends_on_disabled_cells§runtime Lpublished_object_keysdepends_on_skipped_cells§errored$6e59ee60-ef73-45ca-86eb-4d8a44c73771queued¤logsrunning¦outputbodyObservation clé Que dit le théorème de Bézout par rapport à $\text{gcd}(a, d)$ et $r$.
Le reste $r$ est divisible par $\text{gcd}(a, d)$. Le nombre $\text{gcd}(a, d)$ divise donc les 3 nombres, $a$, $d$ et $r$ et donc $\text{gcd}(a, d) = \text{gcd}(a, d, r)$.
Ils ne reste plus qu'à chercher une collision entre les listes de restes modulo $p$ pour $g^{i-1}$ et $a(g^{-n})^{j-1}$. L'identification des collision peut se faire en $\mathcal{O}(\sqrt{n}\log(n))$ avec une recherche dichotomique our en $\mathcal{O}(\sqrt{n})$ amorti avec un dictionaire.
$$A \equiv g^a \pmod{p} \qquad B \equiv g^b \pmod{p}$$
persist_js_state¤mimetext/htmllast_run_timestampAP:has_pluto_hook_features¬rootassigneecell_id$c376513c-6553-4cd6-8384-ae6ff9d472d7depends_on_disabled_cells§runtime hpublished_object_keysdepends_on_skipped_cells§errored$38744170-9af6-44b5-a0be-46a83da3253equeued¤logsrunning¦outputbody(fib_pow (generic function with 1 method)persist_js_state¤mimetext/plainlast_run_timestampAPSehas_pluto_hook_features¬rootassigneecell_id$38744170-9af6-44b5-a0be-46a83da3253edepends_on_disabled_cells§runtime }
a
$\alpha$
b
$\beta$
n
1
3
persist_js_state¤mimetext/htmllast_run_timestampAPhas_pluto_hook_features¬rootassigneecell_id$4ef2c7e9-fb37-4e38-a252-b9c3f83d2a82depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$93aa2719-f962-497b-9fda-30f54fd848ebqueued¤logsrunning¦outputbodyelements0text/plain4text/plain1text/plain5text/plain2text/plain6text/plain3text/plainprefix_shortobjectidf24b43a689b4a3a5prefixInt64typeArraypersist_js_state¤mime!application/vnd.pluto.tree+objectlast_run_timestampAP"has_pluto_hook_features¬rootassigneecell_id$93aa2719-f962-497b-9fda-30f54fd848ebdepends_on_disabled_cells§runtime 3published_object_keysdepends_on_skipped_cells§errored$77093b36-c232-4477-be49-845f1a631829queued¤logslinemsg 0.000001 seconds
text/plaincell_id$77093b36-c232-4477-be49-845f1a631829kwargsidPlutoRunner_d1acb81efileP/home/runner/.julia/packages/Pluto/CBqeh/src/runner/PlutoRunner/src/io/stdout.jlgroupstdoutlevelLogLevel(-555)running¦outputbody248persist_js_state¤mimetext/plainlast_run_timestampAP;\has_pluto_hook_features¬rootassignee@time pow_1000cell_id$77093b36-c232-4477-be49-845f1a631829depends_on_disabled_cells§runtime
published_object_keysdepends_on_skipped_cells§errored$d6b89fda-308f-43da-8028-1a812b4516cfqueued¤logsrunning¦outputbodyObservation clé Que dit le théorème de Bézout par rapport à $\text{gcd}(d, r)$ et $a$.
Le nombre $a$ est divisible par $\text{gcd}(d, r)$. Le nombre $\text{gcd}(d, r)$ divise donc les 3 nombres, $a$, $d$ et $r$ et donc $\text{gcd}(d, r) = \text{gcd}(a, d, r)$. En combinant ça avec l'observation précédente, on a $\text{gcd}(a, d) = \text{gcd}(d, r)$. On peut généraliser cela en le lemme suivant:
