{"group":{"id":1,"name":"Community","lockable":false,"created_at":"2012-01-18T18:02:15.000Z","updated_at":"2025-12-14T01:33:56.000Z","description":"Problems submitted by members of the MATLAB Central community.","is_default":true,"created_by":161519,"badge_id":null,"featured":false,"trending":false,"solution_count_in_trending_period":0,"trending_last_calculated":"2025-12-14T00:00:00.000Z","image_id":null,"published":true,"community_created":false,"status_id":2,"is_default_group_for_player":false,"deleted_by":null,"deleted_at":null,"restored_by":null,"restored_at":null,"description_opc":null,"description_html":null,"published_at":null},"problems":[{"id":60790,"title":"Implement Shor's algorithm","description":"Shor's algorithm, proposed in 1994 by Peter Shor, is an algorithm for factoring numbers that runs in polynomial time (polynomial in the number of digits/bits of the input) on a quantum computer. It works as follows.\r\nTo find a factor of a given integer , which we assume to be an odd composite number that is not a prime power, pick a random integer . Next, if  is coprime to , compute the order of  in the group : that is, find the smallest integer  such that . (If  and  are not coprime, their GCD is a factor of .) If  is odd, choose a new  and begin anew; if it is even, compute , and compute the GCDs of  and  and  respectively. If one of these is non-trivial – neither 1 nor  – it is the desired factor; if both are trivial, choose a new  and start over.\r\nOn a quantum computer, for given  and ,  can be found efficiently. On a classical computer, it can't (as far as we know), but it can still be computed.\r\nYour task is to implement Shor's algorithm. The input will be the product of a small number of distinct primes, and your function should return a factor , the randomly-chosen , its order , the number , and (for informational purposes only) the number of 's tried until the algorithm found a factor. If  and  are not coprime, you may return NaN for  and .\r\nNote 1:  and  not being coprime should be a rare event for such . As such, the test suite will check that you don't get lucky too often. Solutions that call factor() and claim that  just so happened to be one of the factors returned every single time will get rejected; valid solutions should not be affected by this. If yours is, or if you otherwise happen to get unlucky with the inputs such that the test suite times out, submit your solution again.\r\nNote 2: the test suite bans a few keywords, and \"factor\" is among them, so avoid this word in comments, variable names etc.","description_html":"\u003cdiv style = \"text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(0, 0, 0); white-space: normal; \"\u003e\u003cdiv style=\"block-size: 444.5px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 222.25px; transform-origin: 407px 222.25px; vertical-align: baseline; \"\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 359.192px 8px; transform-origin: 359.192px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eShor's algorithm, proposed in 1994 by Peter Shor, is an algorithm for factoring numbers that runs in polynomial time (polynomial in the number of digits/bits of the input) on a quantum computer. It works as follows.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 126px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 63px; text-align: left; transform-origin: 384px 63px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 103.458px 8px; transform-origin: 103.458px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eTo find a factor of a given integer \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 261.767px 8px; transform-origin: 261.767px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, which we assume to be an odd composite number that is not a prime power, pick a random integer \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAIcAAAAkCAYAAACjbylKAAAEeUlEQVR4Xu2aS8iOQRTH2SvFio0FCwo7l9hTIguFZCW5rGwQFhYWFEk2bsXCQi4rJcVWyWVDKRYsWLBCYs//X8+f8803M8/M+z433ztPnd7Lc+Z25jdnzpnnmT2rXMUCAQvMLpYpFghZoMBR2AhaoMBR4ChwFAbyLVA8R77NJqZEgWNipjp/oDlwHED1JyFbIS/zmyolWrLABtS7DbILMqdq4x0+lwXaW4z/90N2QxZUOr/weQtyHPJN5VLgEBSqaHWBo6VpHq9aQvLIVFE3T4TkfaW/EZ+P3eZjcKyC8t6qgKWyrtHxhlhKj2qBeSj41RS+i+87IpUJjufQWevTi8HBwh+qQmfxeaT6XuAYdfraLUcQbjtNxOaXO8JlyAnImVw4rP5Q4JhpcQ+3glOQ+6EJyuDpKnTp4Z9CWC+v4MTj3h3IdsgS4wSmNJcSc7BA33DMtLhHUKxJmMRUPj5D8ROESYNij1hgSv0fkPWQv0GobWzocLhQMGg6D5kWPKVasGc9FwpO3kXIlTH7pfjhHOo5CuHEK4HwBZvSvwY9Zi7ea6hwtA0FjXMasrJaPTTOBcgeyDoI92IauamrLSjUP8UPigf1m/e5kAiIvXTfm6VIcUhwMNo+BjkIUb7ehqfQFslonnsyg262/QYSW22jgOJC3pSncPvCbWQFZDmEWwTH89HYcX71v8pRn4tgkfP/lHqHAEdXUHDgCsIIBiG0e+0z/GYM8MUYeRQgWKYrKNS/n/jCQNR6CAao+yoFNzD16U8ba59wdAmFBYN5/SbPihEcPjecCknXULBfPI96AXEBsIdcBH5hNYiQ/iDg6BoKDprHwowxeIXOaX5X9+lRcgPEPqDQZGqb9I1LwFNX8YVsEUxhVXEfnoP7nfJw9mOclZqyou3+G2rLHiDVGs1p1ILHW01sSynjkg4BmAvxpaR2XBp7TH9Ku33AwQ640Tsf/DSdIbgrK+Y1tMIYMAbz/siMKfvhoZIuX1yTM+kpujoyjx2V27SWgSmP2JXyRtvoCw51qgtIZJzQxNsHVnXPI+omrGtI5BliW6H1bIy3GHRHU1gNsm842obEBmWhiX+LTiytOrITn8xoxr26gqT2CBwDcR/IJW97Q4FDk8FI+jBE7nnc7cZ6Bd9pII3LXF/H2Iw3vkN4auh9GJVJjd6dsGc3TW43tUfgVX8FEX8mx3hDg0O2d1feqJBYz+EaxXoIwshtZzPkAaSJI23LkS9DGxcSgZ+yFSp9ZZ+Ss7FUOGxK1JTrTVmETUBi+05AXkP4FtSTylAPjecgIDcb8hq+8TUJicaVAgf7Iv3kbKzufQ4+X9gC0bGyBswOvWrRiK5hBQkPr3i0nvNOCctegih9JiA3IPIcCtjaOtqOQaJX9WKP1t3ybhDP+5yP65DYA0mexRyChF4fnNbPVM+Rssq70NHKu4fGZsp7rJw0XrkHb63b+3+Do3WDlAb+WaDAUWgIWqDAUeAocBQG8i1QPEe+zSamRIFjYqY6f6AFjnybTUyJAsfETHX+QP8AikAvNCuJa9oAAAAASUVORK5CYII=\" width=\"67.5\" height=\"18\" style=\"width: 67.5px; height: 18px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 27.6px 8px; transform-origin: 27.6px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e. Next, if \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 43.5583px 8px; transform-origin: 43.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e is coprime to \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 70.3917px 8px; transform-origin: 70.3917px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, compute the order of \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 40.8417px 8px; transform-origin: 40.8417px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e in the group \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAH0AAAAnCAYAAAAilUe0AAAGiklEQVR4Xu1bTahVVRR+b15UNjKkxBoUJk6yQmnSwKBJg6AiRBqE5SAaKeSgQYMEpUE0KKVAIvqDaCYoklAYpQ6MFB0YVESNyiLn9n1yvtd+273XXvvsc967eO6FhXrv3mvvtb71f46LC/PP5DSwODmJ5wIvzEGfoBHMQZ+DPkENTFDkm8HT7wVuD4E+myB+vUSuBX0NTnkJtL/XaeNsIti3g54Yh/2Kct2O066Azox5ag3oBPwo6JWxL1Up8L9Y/+JN4unU8SegL0HvVerBvdwLOi9zCrRzxgB/Fvd5H3SrW+LZXyhdv10A3ht1XwOfQ6C/JLoX9O+w4WvQ3ozOGJaODaDPhyuNimf+DSL4uQ/v9jToedAt3aJL+POBzAbWCExhO0BruzVX8efHICpwSXn4+7UBZN4HHnG6JKDnQU8Z+ngZv70LOg7KpTamvmdAhzuZrl/XA/qBTgF3GQLykiymPB8CsAt0EHQCdAeI3sow/RjoJw8TrOGZf3YCU/DSJzbMkoER/MsdUyo1dQZ5ej4bsEgAvdVtoCevA+VSEw2MkTVnnGRjAS/AP8e63SC3p1Oxv4D2gIbIMVTkOdAF0KOd8LocL1ZzBgV+HWQZYwiIjETfURlWhBDo3wd39QCcWnMRX94GklELrNIdfseej0C5CJsDPgs4N5Q83ePlNYqIhafSPwWVhE+dwZTzA4ih2PPRWeFaS34Bkwq/nvO0hvmUqUUeLcP/Dd9tA4XpIuZL/dMZSjVL6PFMdwzpN3i4mJdAZ8hlLvMq1lKGBFDUqBE+5isvvA8/eNOBlP8t9igsW4DKW2rOiO+plBLmVBo+w/rjoFJrJjk9UVDA8w5ZwPmjBbo84zmsax18pISnp24EMcd7cnKoUE++iwFgqPwVxJSgotMq6Lj+H4c35gxdqZGp7EkQPZqGT6OviR68x4+g0hxCRsr7WMWdCTo9gwXXnd2Fc8KVvlclGiqwj/DhOVTEOyDvkEgew+KR+ZH7VZmnijStX1b1lgSNfqdhbQXJo2X4JiCJM8THCvFhDmfN9KYFvOXp9MRHQKUUUNJFLPwWbDhdskaDqfbXGKNCnyr2MBSmQNDvuaq9JDMjERWvsCzD574HK51IDpJLM6mizWznLECZz8MquyRo6ve4GGoRXvwZgdaDSuEuvA8Nb1OgcIVe9e2xAclQ76kEiGfSKL8CsXbQHcWvTyoT6CkDtKr0LPAW6Bw8tLQrKeF5Sea3lrEpjbG2heSeEASCo/TFv8c5NrXeY/SaprE9k0dL+UotHj7hGqWFuJhTNLGKNp3tHs60gq72TMKrMOwrPBXRZ+yqdBADGw5f/gBv9fu59R6w1CHIo1NzCQ+fFOgpvRFUgm61fdTZWdBSlzOWp+d609Z0oS7CGqrESlV4TE3gVLdwj8KnPKi2VUsZdTyXqAWc6+XpLc6y7NwxQE9dUsJbs+SSQmrHruJHYBluU4OQcGCjgs5an7tj2J5p0ijDr01F8RlDts7XeVugq6+VECVQ+HuuN2U+ahW+duyq+3A+b038wvaNBR3X13oVDeVukIw6NZfw6C+1xirkevEcumVTlTyG8LVjVypEXmJNtBTOuZ6FK9vUmlaN+1kvyKhTht8LnG6TQK9pUc3zLNBL/WHMONebtky1dIaKrtKTsfhOnlFq/CCGRZ23l1bRF0aSeC7RAjj3Kop4HywVz7NAl0CeMazaM75ZoyJrSOH7jF0pvHeU6h5hBhpVe8avVC/Ehl8EwLGA7WOoV8cWe0lp2kalfRMAmeJm9aaeBwUeIVgIfgjyjl3JU3nV8wRPBs593jtr5qD2LGX4HtmsNZKhJt0UzyyBridj1mRKQ47USxEvFG/w/4LcC4ECpLaFUjvmAV1hlPncc45qBVb84UsR9+PfjIyUxfuxHjbRsPgMfrDQzkuVQPe8RBH2ul5BU+v4SlLqoULt2JXe8QaIAOpD4D8AWQpmd/AqyHpTRfxU77TIq725OkW6b5leJu9XAp2bNAXrM4ceQilMMQSx5q2aIc5dbR409s2gmpbZdWcP6GTUZxLmukBh0Wob3BAy9OHBaPUFaBRH84LOizOMH1lhj1stY+sD1FB7PG/CNp1VA7o8/uQKAT9aTmvS2LibV+Q/lNSCrhzf+vqUR3V9xq4evrO8hmGdT8Ssp2bN9+8DevOhTgYc7vwMGuKlTOeR01g2y6B7nhVPA6WBpZxl0AcWdc5OGpiDPkFbmIM+QdD/A2kV0DcnKNgCAAAAAElFTkSuQmCC\" width=\"62.5\" height=\"19.5\" style=\"width: 62.5px; height: 19.5px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 51.325px 8px; transform-origin: 51.325px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e: that is, find the smallest integer \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003er\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 32.275px 8px; transform-origin: 32.275px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e such that \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAALAAAAAmCAYAAABkiBEAAAAGlUlEQVR4Xu2bTejuQxTH792TsGJBcRdXFOW1RF2JuiVFIaRb5GUhSW5IFhZueUmy8LKwsPC2UFKKhQWRtwVFLFiQ2InYu99PzbmdO/+Z38zze+b33Hlu86vT/3n+v5k5Z875zplzzsyze9d4hga2WAO7t1j2IfrQwK4B4AGCrdbAAPBWm28IPwA8MLDVGhgA3mrzDeEHgAcGtloDA8Bbbb4h/ADwwEBJAxerwV2ip0W/lBpv+v0A8LTG79XrJ0TXi77etHGOIb9rxPtO0X7RCUGOS9bQAXrcJ7rJzelVfb4nM0f43yi61fH/U59fFB3yfVoD+GwNfpHoQtGZoptFCH8gAOGjY2iUVVgbcE9rYLxV+PbU9hQJ84Ho0oY6wIs/HMb7T39PLEwYO7wkArxXiHbsAEsAmFX2lAiwfie6XQQQplZcL4az7RJ5/Opfx/v0Mrc5cnjAtdABDu0tJ8h9+vzyhGAG4GfU5mCqXWsAw8OE/FKffxUhJFvFO6kVNEerC/ZhB7FV3tp4C4q92NCtdfCKJL3bSQtGLpuQ/m29wyFmF88SADYhs25/MXW3Hbi18dpKt5nRWuvgR4n9j+gMUU149kdof7n+/rUpD4yQe0WPiY4KuDej82ZcWhuvmWAbHKilDtjdfhYRDvBYLJwLLa09Oze7evJp7YGN6Trelwz0wwZGWncBtTQeBrhBRCJyuogEieSE7+aJvKF4/4jouuAMUAc5xbUTerHKAckzz7mi30Xvi5LxoxuLvg+J8IzmIT/VZ0JAA9q6MbDFs8yBMA0w25PCobW/RY0IJZJPLYDjCTLJ10QPishSEQoFG9N1ErbjCcDM5cmgIwxA5k1N9XnRb6JPROeLaMeDDh8XvR7ekwRf6fqnQGyLgZIXYLOkyP5PDAnfq0SpUiAhHwkrC8oD3eLPIFo+DrUGhb+Mx4I9T0Q44MdPORveMycWZDJ8gF8JwCjhzaBgmDBZBiNb/yoIjHKMCZ4TYxigK+fWZbOWHtgnLyQu90dg+kLfrVz1kz4/IPIlR9Mrijo1MqgBIec0bGzsdIHIl6Ie1XcqRrlt2sJB+K7rgf/VGJ8HbDCed1TM+ZwIBbT/QTSV5E0CGPB+JsrFs/8Hht4rwBSyVdYlMiuFagng0li2cyFaqmTky0/eOXgQ5ADm+3pbYV9CBJ6cdy7JXanKIw4v9rS5BWIOshgG5jywB29uZRuAi0xqZ9lZu1bGY1qlsTwQU/rMvTfvWzoUIJu3WNs8uHlf8hXi8tRTkrvWZMYrXmR+4fpdINd+B78cgG3LYnIpb+oVukdtWp6RH08xsCm8BIS5ADYPVgKwD0HMg1toMZUcluSuBTC8SBBjLNkuYMfVhkfkpX22fGaMUwAuKZO+FtMRuxSZ1M4ytBsA3ll+zNnEdsESgD0QzcMT6gGcTQAYOXNxts8PTLap9kfBKQVgW5k57+tXzWSNbkXg9ta8lfdZMoQwAMNjKiFPATiVw8Q2aKEDi8Fzx8ZWeoW3JbB44KpCQDxpP1gOnH5SpbPs3kC5ijwtjLd0COGrF1NVgtRcarx3Cx2Yh50KNX2IQ5WGGvZk+SwXQvigOgVOAP5t2HoYIy7prAKQ3tu2MN7SAPbbb/bCi4TwyZ4Bw4M/B64WOigeB0u++JJP6dDmCHZiD+wFjk9ArDLBIQY1S4t/AfVZQUm9g3IV+VoYb2kAx9tvXEs1/laF8BUly/RpkwPMujqoOg4OQvpKSXVlKwaw98B+EAMvJ0R3iKgNE2I8K3pP1PLC90ji6pM4bF8K6UyfcU4TVwBi0PD+e5GV3+aEiyZbTV+/oKorWzGA40mxYnk4auTEhss5FjuhEJ4DYQWv4t2m2vYCYL/FTp7HV0zcH5umkhPvOFJ199J7HyL4QwkOBHAw7Jo4nvgomfcfi6yMxa7K3YmTRNzDoB/Oyh7i09tENWVTj6UaAFt77m9UV7ZyZbQXguCUZ7iVj6e1yVvAzbbzXGPwVmBh0SZsedwHwHjmeYwhOw7x/yo37OyCjf8pDTp9Q4THOTnww0EYiOAHr3dF34hwHPsT771N6GO8aAsIuGsBEAGwXQFIKY85w8MuFiEfR77Y9moRdzEYA5lqgAuP+Bct/I8YHTmmxmAh/i3K/dRoh/yluxCpCY//DQ10o4EB4G5MMQSZo4EB4DlaG3260cAAcDemGILM0cAA8BytjT7daGAAuBtTDEHmaGAAeI7WRp9uNDAA3I0phiBzNDAAPEdro083GjgMtEjgNmgI5+YAAAAASUVORK5CYII=\" width=\"88\" height=\"19\" style=\"width: 88px; height: 19px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 12.0417px 8px; transform-origin: 12.0417px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e. (If \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 127.558px 8px; transform-origin: 127.558px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e are not coprime, their GCD is a factor of \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 12.0417px 8px; transform-origin: 12.0417px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e.) If \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003er\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 54.8417px 8px; transform-origin: 54.8417px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e is odd, choose a new \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 120.967px 8px; transform-origin: 120.967px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and begin anew; if it is even, compute \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAMQAAAAmCAYAAACbKjTiAAAIIklEQVR4Xu2cW+h9UxDH//93Ep54oPBAhAe3iCJRIkW5JyG3kiRC8iBRLknKLXnwIDwokeJBInJNinhAkXhyi3fmo/31n9+y1p455+xzfuewdk37nN9ee61Zs+Y7M2vWnN/OHf3qEugS+EcCO7ssugS6BHZJoAOia0OXgJNAB8Ry1eE16/705Q7Re59SAh0QU0pza1/X2NcDjG5Z3hC956kl0AExtUR39Yd3uM7oazfE+fb5RqNjh7+9b/frjT5cHhu951kk0AExi7Tybfeypu8YHeJewWPcYPSw0S9GlxudNjwnrHo9331vuSwJdEAsR7K3DUr/uOv+B/t8YuEx8CKAAjD0vcZy1mKmXjsgZhJXuvEX1vIEo5+HN1D6c42uLnoghHrO6MvCm6QH2sCGRxvPVxrdVxiHtZhKB8T0y3Cgdflo0uIDFLzEf91DMM8rjM4w2m0Q+TF2n3fvRPh5stF5bvmerBgcPZZBusiN/6N9fsToXq8CHRDjgGAvcJTRqUZHGF04fL/J7m+Wwhy6esLubxg9n8AaC/uY0e2NvhJdbEwTZPmqkRIKiwBCk8bL3Dx8+cPuuwfSkLwBQxm+/v1qB0QOEFhxhEiG6CGjfYxaYQ7hkt9Mj40AaA438uHVxmj4HIx6BZ4CEAo5xcq19sHv20oWBYj77UE1Hd4BEa8qlu2nAQC/2R23j6v+xqjMDCk0YKGii9DqK6P/U4ZpakDgja9ygiaNfdyI4DFArF0TjB0Qkdru2OGtUKS8CPwBo0xs/J61e8loSwwbs7PRLaYGBN4YI7WfEV6ba8zzkOmjfdMjd0DE+iUrlNn4ZsMl+uQqs04xN5vdYkpAyMMS/nBpL9HaXKv9C9a26cE7IGIFw6pgfSLvkC3VUIaEeFdp2ZiLrS1Y0HOM2Bjua0RYx+ac77KUfuF5fqvRWUYHD11FAFf4t//Q/lC7f2/0slFUjsK7JB6w3LLgb9vnb53iLrqH0H6AdaEagPBTV02v1f4Ca9RMeGQBAbruGQT+3TDRs+1O9mVPo4/HBnGMrstHzYcNLQvGxWaZ0+PjjVAuFl1WJXNOUCvVKOfLolxmxD7Eg0EKHe09ULS7jJSpIbNCTh/eWZe3jMiG6QQcpb/D6Jnh+ad2P8m9XwOFeIFHrK42qfo7MTjjnmJUCw3xfqQ3JUPJQPG7vi8KCPrDABw2yNL3X8va8Zw5AfCmIcoAwocMqs1BOJ8ZyRpl04bKu0so896z49X6l9vGgtIP1qWcj7wBJ84YgmZWYhigVqpRjq29CONiKf11iX0hg5VJ1fKe30zW6qHYnwg0gJmSEZ8A0Ak5fe1dKIgUqxV6qG9AceQgP81F8mqFJYSU8lCLAuJ36+tdI53we92qGTDaf240tukeTbt6i8AESxfvhX5QIZhSGfR9uwGhxR6bD+lVWR0pTrR4KAJXa4PM6SxnEzqUKuXjx2zJzv89isUVHvBODcytRIFfn9ac/bvew6AvAnrLe0R8Z+ZOG+T5gVFpGFuAa7X/13hjHkLKgAUqXTwdaXDQuAl5dIGhNR8BPIqta4tWlmpkF3bedpFiecWuedPWc8koOuTSvgr+5WHkHQA3+5raFfGdlYfGKkHrDYH3Uq32aUCog5pbpBPl5lsWKDuxVbXTfBivZfn+HJiJDndKnmcp1ZhqvpFizQsIGbkIED7kUniZMSgR31n5MBYbdnlyvScvJU8sgw+/tA8Nd81D+E5bcaRHYpR9yU5yWe38fFrW34cB2fBP/BLPf2I0dkI69dwixZoXEDIKESD8+PJAxOgo4piHjfjOygk+W/sUv78Sb2Ptt4xZA4TvsKUccpmzxr7ZCU/ZLrMIsm7zhH9Yn1WXbkdzWhQQyH8snK4BQmBaNiBkvFqeXJlB5qCEgtYo/M1JbdJS9laqsRWnZZR4OzbVfj41l+l5Gj20yUxwRW2WBQifKBlLJNTGz3iXiO+M+GSwxzy5D+nYM3KGMppu1cAlIDy6auFSGaPNGm+vGhB+PplU4OihTWa1VtQmUqx5PYSPDsZSzX7zLUXLZB0jvjPiC8svrJOy6C+dKCkB4QVZAkK5dphWLrnMYWcmtMo2Y/OBDxaWBVXOHqvDzzspqVjnGqNIseYFRBlutKp25XW9jvjERUsBI74j3UiVXwyd+ExY+tyqBITytfTpKwcFBk5COekEEFFlYTS5VTz3C1wukj8E4/SVEPFMo1eM+N3zKjfJs8oiUqx5AQEfvu9aBKC+y/1jGT2USlgefs4aXXjeMu96gKYTJbU9hD/cQOk5bOEc4lmjp4w4EOFKo27W1Z64vXflgILyBU6Gqa1BsP5HK4CCMod19g6Ix5cp1LJ8fp9XC32j5z4k8odsGEwqdCl3udSoLN0oDyCRJ7VPexhRR8V7ii6YB/p1sZH/zySt5feAywBC7am/CtOtGrQGCCZ1txGWgPQbx+NPD4uQyedPrM8Ld6dzAl/fo/nQuebE4q27Z2AO/BTT/3SSNcJYMQ/qyqjBopbIn4qzf3rR6CMjSlEwcOXzsmxdY9EWpaJWCsUGEOw1WvVAvu6N0h7p0IP2mdo3Igz6gKcMEFgjAHynkUqF+Bt7HPgY6wNg/2qUrirO1DIxuK5NO532vPfPXQKhBGYBRJSBCgfrDboE1l0CswBik06n113unb81lcAsgNBhBzFh6pBjTefc2eoSaEogCwifjs38WKaLvEtgIyUQAYITP//PeTXJTcjIbOSCdKa3VwIRILaXuz56l8CKJdABsWKB9+HWWwIdEOu9Pp27FUvgL0tZPEVaPSsaAAAAAElFTkSuQmCC\" width=\"98\" height=\"19\" style=\"width: 98px; height: 19px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 86.725px 8px; transform-origin: 86.725px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, and compute the GCDs of \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAEYAAAAkCAYAAAA0EkzVAAACbElEQVRoQ+2Yuy8FQRTG3Z4CFQUFBYlC45EIlZBoJAoKOolXotAIaqFQqTwiSgn/AYXiJsQjOgkFBQUVUej5vmQmmayZzM69szKbO5N82WtnzM757Tlnzk6hKjYtgULkoicQwRg8I4KJYNySRvSY6DHRY0wE6tCxAk1BjTZMlRBKEsg8YFRD31BNpYOZAIAx6AuaETByB+ZKLHwS12fbG03Z36LMxfl78ugxP8LYblxvUxruMiyCMdCKYP4TDGN1A+qHXqEmaBQahGqhO+jYxa81Y3MXSnsio5/huiCSGbfAe6hBGLiG62algKHxO9A4dAKxDvhUjJcxy1utAlg5bHLjMaewcgi6hkYSUAjgAWqDHqE+Tb8rpFyAWYVVzCkshjo13kBv+hCWb+G6nIKC6mEphmuHpCrODJOXvSvR6BeI5fM+NKt50BzuMczYhiHmH1vLPRiZbGmoKXe8oY+J9x3qgNTcYwNk6g8+lKTRzB3tFm9hUub3iI8WNBjWK0/CSl0YqWHGYdypdn1QwRxBg+EuxN2ILQmGUC5EH3cjtnpPYcS5ggbThQXeCKO5TfeK3xJKEX8PQASj9vtwmqDB0EBZn/A3jecOxTrmCDpQwPmodlWgWYJJpgCrp+tO8Og16xDDinXDJXQI8VtI1jc0yPfxQBZgaMO0eLEsP2SjXXzR58KuPx7verTpu9pVFyQPqhZxM4vzGKdwdwFj27GcHhz6YBcwpVS7odtvXJ8LGPlRyfhshnxUu8GCSwtG3cZNFXGwRpayMBsYlvtLEE/X1UY425CvqreUtWf6PzYwmT485MkjGMPbiWAMYH4BMu+dJVUMypQAAAAASUVORK5CYII=\" width=\"35\" height=\"18\" style=\"width: 35px; height: 18px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAEYAAAAkCAYAAAA0EkzVAAACUklEQVRoQ+2Yuy8FQRTG3Z4CFQUFBYlC45EIlZBoJAoancSr0whqoVCpPCJKCf8BhUJCPKKTUFBQUBGFP8D3JTPJ5N6ZzM7Oxu64M8mX3Xtnd2fOb845c3ZLNbFpCZQiFz2BCMbgGRFMBOOWNKLHRI+JHmMi0ICOFWgaarZhqoZQkkAWAKMW+oHqqh3MFABMQN/QrIARwQBEG/QigFzj2Bc9pjJWIhhD/ohg/hIMY3UDGoTeoBZoHBqG6qF76NiW6XPuz9xj9kRGP8NxUSQzboEPUJMwdg3HzZwNtw2fGRgavwNNQicQ64AvZXQ5EP9qF8Bsk8uzPzMwp7BiBLqBxsqg0MBHqAN6ggY0/XlC0I2dCZhVPJk5hcVQt8Yb6E2fYvQtHJcTUCBkwvZpDOfRlA/wBkOjXyGWz/vQnGYi8/iPYcbGiXLCthY8GJlsaagpd7yjj4n3A+qC1NxjA5RXv7fHSKOZOzot3sKkzPeREJoXGNYrz8JKXRipYcbLuFPthkAFc/QCo+aBcjCEcikgcDdiawwkjDhXLzA9eMCtMJrbdL84l1Au8HsIIhi1PwSn8QJDA2V9wnMazx2KdcwRdKCAC6HalQtWngKsnq77gkevWYcYVqxjrqBDiO9Csr7hgL3QXcFdhTbMiIVl+SEb7eJCnwu7Ksxw/bQZWrWbet1cwNh2rNSTKOKNLmDSVLtFtDnRnFzAyJdKxmcrFEK1mwiC7qKkYNRt3FQRp55EEW+0gWG5vwTx67raCGcbCqXqdWZvA+P8wP9yQwRjWMkIxgDmF5EMfSVCIHhFAAAAAElFTkSuQmCC\" width=\"35\" height=\"18\" style=\"width: 35px; height: 18px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 1.94167px 8px; transform-origin: 1.94167px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e respectively. If one of these is non-trivial – neither 1 nor \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 176.575px 8px; transform-origin: 176.575px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e – it is the desired factor; if both are trivial, choose a new \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and start over.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 107.733px 8px; transform-origin: 107.733px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eOn a quantum computer, for given \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 3.88333px 8px; transform-origin: 3.88333px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003er\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 218.875px 8px; transform-origin: 218.875px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e can be found efficiently. On a classical computer, it can't (as far as we know), but it can still be computed.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 63px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 31.5px; text-align: left; transform-origin: 384px 31.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 366.7px 8px; transform-origin: 366.7px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eYour task is to implement Shor's algorithm. The input will be the product of a small number of distinct primes, and your function should return a factor \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ef\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 71.1833px 8px; transform-origin: 71.1833px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, the randomly-chosen \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 31.1083px 8px; transform-origin: 31.1083px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, its order \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003er\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 41.225px 8px; transform-origin: 41.225px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, the number \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eq\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 119.808px 8px; transform-origin: 119.808px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, and (for informational purposes only) the number of \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 131.617px 8px; transform-origin: 131.617px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e's tried until the algorithm found a factor. If \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 129.125px 8px; transform-origin: 129.125px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e are not coprime, you may return NaN for \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003er\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eq\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 1.94167px 8px; transform-origin: 1.94167px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 84.5px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 42.25px; text-align: left; transform-origin: 384px 42.25px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 24.5px 8px; transform-origin: 24.5px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eNote 1: \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 157.925px 8px; transform-origin: 157.925px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e not being coprime should be a rare event for such \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 161.558px 8px; transform-origin: 161.558px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e. As such, the test suite will check that you don't get lucky \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 9.725px 8px; transform-origin: 9.725px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"font-style: italic; \"\u003etoo\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 78.175px 8px; transform-origin: 78.175px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e often. Solutions that call \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 30.8px 8px; transform-origin: 30.8px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"font-family: Menlo, Monaco, Consolas, \u0026quot;Courier New\u0026quot;, monospace; perspective-origin: 30.8px 8.5px; transform-origin: 30.8px 8.5px; \"\u003efactor()\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 47.45px 8px; transform-origin: 47.45px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and claim that \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 177.75px 8px; transform-origin: 177.75px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e just so happened to be one of the factors returned every single time will get rejected; valid solutions should not be affected by this. If yours is, or if you otherwise happen to get unlucky with the inputs such that the test suite times out, submit your solution again.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 374.075px 8px; transform-origin: 374.075px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eNote 2: the test suite bans a few keywords, and \"factor\" is among them, so avoid this word in comments, variable names etc.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function [f, a, r, q, cnt] = shor(N)\r\n\r\nend\r\n","test_suite":"%% \r\ns = [\r\n        \"% Compute x^y mod for integers x, y, z\"\r\n        \"function res = modexp(x, y, z)\"\r\n        \"    res = 1;\"\r\n        \"    x = mod(x, z);\"\r\n        \"    while y\"\r\n        \"        if mod(y, 2)\"\r\n        \"            res = mod(res*x, z);\"\r\n        \"        end\"\r\n        \"        x = mod(x^2, z);\"\r\n        \"        y = floor(y/2);\"\r\n        \"    end\"\r\n        \"end\"\r\n    ];\r\nwritelines(s, \"modexp.m\", WriteMode = \"overwrite\")\r\n% No test here, this just writes out the modexp function used by the test suite\r\n\r\n%rng(0xDEADBEEF)\r\n\r\n%%\r\nNcnt = 20;\r\npmax = 1e4;\r\n\r\np = primes(pmax);\r\nNp = numel(p);\r\n\r\nlenp = length(num2str(p(end)));\r\nlenN = length(num2str(p(end)^2));\r\n\r\nT = NaN(1, Ncnt);\r\nnumNaN = 0;\r\n\r\nfor i = 1:Ncnt\r\n\r\n    i1 = randi(Np);\r\n    while true\r\n        i2 = randi(Np);\r\n        if i2 ~= i1\r\n            break\r\n        end\r\n    end\r\n\r\n    N = p(i1) * p(i2);\r\n\r\n    tic\r\n    [f, a, r, q, cnt] = shor(N);\r\n    T(i) = toc;\r\n    \r\n    assert(~mod(N, f), \"f is not a factor of N.\")\r\n    assert(f ~= 1 \u0026\u0026 f ~= N, \"f is not a non-trivial factor of N.\")\r\n    \r\n    Nstars = round(T(i)*10);\r\n    stars = [repelem('*', Nstars) repelem(' ', Nstars \u003e 0)];\r\n    fprintf(\"%\" + lenN + \"u = %\" + lenp + \"u*%\" + lenp + \"u (a = %\" + lenN + \"u, r = %\" + lenN + \"u, q = %\" + lenN + \"u, tries = %2u) %s%.2fs\\n\", N, f, N/f, a, r, q, cnt, stars, T(i));\r\n\r\n    if ~isnan(r)\r\n        assert(modexp(a, r, N) == 1, \"a^r = 1 mod N failed.\")\r\n        assert(modexp(a, r/2, N) == q, \"a^(r/2) = q mod N failed.\")\r\n        assert(f == gcd(q+1, N) || f == gcd(q-1, N), \"f does not obtain from q.\")\r\n    else\r\n        numNaN = numNaN + 1;\r\n    end\r\n\r\nend\r\n\r\nfprintf(\"Took %.2f seconds to find factors of %u numbers using Shor's algorithm!\\n\", sum(T), Ncnt)\r\nfprintf(\"gcd(a, N) \u003e 1 in %u / %u cases.\\n\", numNaN, Ncnt)\r\n\r\nassert(numNaN \u003c Ncnt/4, \"You got lucky a little TOO often, friend.\")\r\n\r\n%%\r\nNcnt = 20;\r\npmax = 5e2;\r\n\r\np = primes(pmax);\r\nNp = numel(p);\r\n\r\nlenp = length(num2str(p(end)^2));\r\nlenN = length(num2str(p(end)^3));\r\n\r\nT = NaN(1, Ncnt);\r\nnumNaN = 0;\r\n\r\nfor i = 1:Ncnt\r\n\r\n    i1 = randi(Np);\r\n    while true\r\n        i2 = randi(Np);\r\n        if i2 ~= i1\r\n            break\r\n        end\r\n    end\r\n    while true\r\n        i3 = randi(Np);\r\n        if i3 ~= i1 \u0026\u0026 i3 ~= i2\r\n            break\r\n        end\r\n    end\r\n\r\n    N = p(i1) * p(i2) * p(i3);\r\n\r\n    tic\r\n    [f, a, r, q, cnt] = shor(N);\r\n    T(i) = toc;\r\n    \r\n    assert(~mod(N, f), \"f is not a factor of N.\")\r\n    assert(f ~= 1 \u0026\u0026 f ~= N, \"f is not a non-trivial factor of N.\")\r\n    \r\n    Nstars = round(T(i)*10);\r\n    stars = [repelem('*', Nstars) repelem(' ', Nstars \u003e 0)];\r\n    fprintf(\"%\" + lenN + \"u = %\" + lenp + \"u*%\" + lenp + \"u (a = %\" + lenN + \"u, r = %\" + lenN + \"u, q = %\" + lenN + \"u, tries = %2u) %s%.2fs\\n\", N, f, N/f, a, r, q, cnt, stars, T(i));\r\n\r\n    if ~isnan(r)\r\n        assert(modexp(a, r, N) == 1, \"a^r = 1 mod N failed.\")\r\n        assert(modexp(a, r/2, N) == q, \"a^(r/2) = q mod N failed.\")\r\n        assert(f == gcd(q+1, N) || f == gcd(q-1, N), \"f does not obtain from q.\")\r\n    else\r\n        numNaN = numNaN + 1;\r\n    end\r\n\r\nend\r\n\r\nfprintf(\"Took %.2f seconds to find factors of %u numbers using Shor's algorithm!\\n\", sum(T), Ncnt)\r\nfprintf(\"gcd(a, N) \u003e 1 in %u / %u cases.\\n\", numNaN, Ncnt)\r\n\r\nassert(numNaN \u003c Ncnt/4, \"You got lucky a little TOO often, friend.\")\r\n\r\n%%\r\nfiletext = fileread(\"shor.m\");\r\nillegal = contains(filetext, \"assignin\") || contains(filetext, \"assert\") || contains(filetext, \"regexp\") || contains(filetext, \"str2num\") || contains(filetext, \"factor\"); \r\nassert(~illegal, \"Illegal keyword found.\")\r\n","published":true,"deleted":false,"likes_count":0,"comments_count":4,"created_by":332395,"edited_by":332395,"edited_at":"2025-02-18T07:30:07.000Z","deleted_by":null,"deleted_at":null,"solvers_count":4,"test_suite_updated_at":"2025-02-18T07:30:07.000Z","rescore_all_solutions":false,"group_id":1,"created_at":"2025-02-09T12:22:40.000Z","updated_at":"2025-02-18T21:57:39.000Z","published_at":"2025-02-09T12:22:40.000Z","restored_at":null,"restored_by":null,"spam":null,"simulink":false,"admin_reviewed":false,"description_opc":"{\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eShor's algorithm, proposed in 1994 by Peter Shor, is an algorithm for factoring numbers that runs in polynomial time (polynomial in the number of digits/bits of the input) on a quantum computer. It works as follows.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eTo find a factor of a given integer \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, which we assume to be an odd composite number that is not a prime power, pick a random integer \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003e1 \u0026lt; a \u0026lt; N\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e. Next, if \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e is coprime to \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, compute the order of \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e in the group \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003e(\\\\mathbb{Z}/N\\\\mathbb{Z})^\\\\times\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e: that is, find the smallest integer \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003er\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e such that \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea^r \\\\equiv 1\\\\;\\\\mathrm{mod}\\\\;N\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e. (If \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e are not coprime, their GCD is a factor of \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e.) If \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003er\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e is odd, choose a new \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and begin anew; if it is even, compute \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eq = a^{r/2} \\\\;\\\\mathrm{mod}\\\\; N\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, and compute the GCDs of \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eq+1\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eq-1\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e respectively. If one of these is non-trivial – neither 1 nor \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e – it is the desired factor; if both are trivial, choose a new \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and start over.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eOn a quantum computer, for given \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003er\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e can be found efficiently. On a classical computer, it can't (as far as we know), but it can still be computed.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eYour task is to implement Shor's algorithm. The input will be the product of a small number of distinct primes, and your function should return a factor \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ef\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, the randomly-chosen \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, its order \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003er\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, the number \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eq\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, and (for informational purposes only) the number of \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e's tried until the algorithm found a factor. If \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e are not coprime, you may return NaN for \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003er\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eq\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eNote 1: \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e not being coprime should be a rare event for such \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e. As such, the test suite will check that you don't get lucky \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003etoo\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e often. Solutions that call \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:rFonts w:cs=\\\"monospace\\\"/\u003e\u003c/w:rPr\u003e\u003cw:t\u003efactor()\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and claim that \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e just so happened to be one of the factors returned every single time will get rejected; valid solutions should not be affected by this. If yours is, or if you otherwise happen to get unlucky with the inputs such that the test suite times out, submit your solution again.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eNote 2: the test suite bans a few keywords, and \\\"factor\\\" is among them, so avoid this word in comments, variable names etc.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\",\"relationship\":null}],\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"target\":\"/matlab/document.xml\",\"relationshipId\":\"rId1\"}]}"}],"problem_search":{"errors":[],"problems":[{"id":60790,"title":"Implement Shor's algorithm","description":"Shor's algorithm, proposed in 1994 by Peter Shor, is an algorithm for factoring numbers that runs in polynomial time (polynomial in the number of digits/bits of the input) on a quantum computer. It works as follows.\r\nTo find a factor of a given integer , which we assume to be an odd composite number that is not a prime power, pick a random integer . Next, if  is coprime to , compute the order of  in the group : that is, find the smallest integer  such that . (If  and  are not coprime, their GCD is a factor of .) If  is odd, choose a new  and begin anew; if it is even, compute , and compute the GCDs of  and  and  respectively. If one of these is non-trivial – neither 1 nor  – it is the desired factor; if both are trivial, choose a new  and start over.\r\nOn a quantum computer, for given  and ,  can be found efficiently. On a classical computer, it can't (as far as we know), but it can still be computed.\r\nYour task is to implement Shor's algorithm. The input will be the product of a small number of distinct primes, and your function should return a factor , the randomly-chosen , its order , the number , and (for informational purposes only) the number of 's tried until the algorithm found a factor. If  and  are not coprime, you may return NaN for  and .\r\nNote 1:  and  not being coprime should be a rare event for such . As such, the test suite will check that you don't get lucky too often. Solutions that call factor() and claim that  just so happened to be one of the factors returned every single time will get rejected; valid solutions should not be affected by this. If yours is, or if you otherwise happen to get unlucky with the inputs such that the test suite times out, submit your solution again.\r\nNote 2: the test suite bans a few keywords, and \"factor\" is among them, so avoid this word in comments, variable names etc.","description_html":"\u003cdiv style = \"text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(0, 0, 0); white-space: normal; \"\u003e\u003cdiv style=\"block-size: 444.5px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 222.25px; transform-origin: 407px 222.25px; vertical-align: baseline; \"\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 359.192px 8px; transform-origin: 359.192px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eShor's algorithm, proposed in 1994 by Peter Shor, is an algorithm for factoring numbers that runs in polynomial time (polynomial in the number of digits/bits of the input) on a quantum computer. It works as follows.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 126px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 63px; text-align: left; transform-origin: 384px 63px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 103.458px 8px; transform-origin: 103.458px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eTo find a factor of a given integer \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 261.767px 8px; transform-origin: 261.767px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, which we assume to be an odd composite number that is not a prime power, pick a random integer \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAIcAAAAkCAYAAACjbylKAAAEeUlEQVR4Xu2aS8iOQRTH2SvFio0FCwo7l9hTIguFZCW5rGwQFhYWFEk2bsXCQi4rJcVWyWVDKRYsWLBCYs//X8+f8803M8/M+z433ztPnd7Lc+Z25jdnzpnnmT2rXMUCAQvMLpYpFghZoMBR2AhaoMBR4ChwFAbyLVA8R77NJqZEgWNipjp/oDlwHED1JyFbIS/zmyolWrLABtS7DbILMqdq4x0+lwXaW4z/90N2QxZUOr/weQtyHPJN5VLgEBSqaHWBo6VpHq9aQvLIVFE3T4TkfaW/EZ+P3eZjcKyC8t6qgKWyrtHxhlhKj2qBeSj41RS+i+87IpUJjufQWevTi8HBwh+qQmfxeaT6XuAYdfraLUcQbjtNxOaXO8JlyAnImVw4rP5Q4JhpcQ+3glOQ+6EJyuDpKnTp4Z9CWC+v4MTj3h3IdsgS4wSmNJcSc7BA33DMtLhHUKxJmMRUPj5D8ROESYNij1hgSv0fkPWQv0GobWzocLhQMGg6D5kWPKVasGc9FwpO3kXIlTH7pfjhHOo5CuHEK4HwBZvSvwY9Zi7ea6hwtA0FjXMasrJaPTTOBcgeyDoI92IauamrLSjUP8UPigf1m/e5kAiIvXTfm6VIcUhwMNo+BjkIUb7ehqfQFslonnsyg262/QYSW22jgOJC3pSncPvCbWQFZDmEWwTH89HYcX71v8pRn4tgkfP/lHqHAEdXUHDgCsIIBiG0e+0z/GYM8MUYeRQgWKYrKNS/n/jCQNR6CAao+yoFNzD16U8ba59wdAmFBYN5/SbPihEcPjecCknXULBfPI96AXEBsIdcBH5hNYiQ/iDg6BoKDprHwowxeIXOaX5X9+lRcgPEPqDQZGqb9I1LwFNX8YVsEUxhVXEfnoP7nfJw9mOclZqyou3+G2rLHiDVGs1p1ILHW01sSynjkg4BmAvxpaR2XBp7TH9Ku33AwQ640Tsf/DSdIbgrK+Y1tMIYMAbz/siMKfvhoZIuX1yTM+kpujoyjx2V27SWgSmP2JXyRtvoCw51qgtIZJzQxNsHVnXPI+omrGtI5BliW6H1bIy3GHRHU1gNsm842obEBmWhiX+LTiytOrITn8xoxr26gqT2CBwDcR/IJW97Q4FDk8FI+jBE7nnc7cZ6Bd9pII3LXF/H2Iw3vkN4auh9GJVJjd6dsGc3TW43tUfgVX8FEX8mx3hDg0O2d1feqJBYz+EaxXoIwshtZzPkAaSJI23LkS9DGxcSgZ+yFSp9ZZ+Ss7FUOGxK1JTrTVmETUBi+05AXkP4FtSTylAPjecgIDcb8hq+8TUJicaVAgf7Iv3kbKzufQ4+X9gC0bGyBswOvWrRiK5hBQkPr3i0nvNOCctegih9JiA3IPIcCtjaOtqOQaJX9WKP1t3ybhDP+5yP65DYA0mexRyChF4fnNbPVM+Rssq70NHKu4fGZsp7rJw0XrkHb63b+3+Do3WDlAb+WaDAUWgIWqDAUeAocBQG8i1QPEe+zSamRIFjYqY6f6AFjnybTUyJAsfETHX+QP8AikAvNCuJa9oAAAAASUVORK5CYII=\" width=\"67.5\" height=\"18\" style=\"width: 67.5px; height: 18px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 27.6px 8px; transform-origin: 27.6px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e. Next, if \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 43.5583px 8px; transform-origin: 43.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e is coprime to \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 70.3917px 8px; transform-origin: 70.3917px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, compute the order of \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 40.8417px 8px; transform-origin: 40.8417px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e in the group \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAH0AAAAnCAYAAAAilUe0AAAGiklEQVR4Xu1bTahVVRR+b15UNjKkxBoUJk6yQmnSwKBJg6AiRBqE5SAaKeSgQYMEpUE0KKVAIvqDaCYoklAYpQ6MFB0YVESNyiLn9n1yvtd+273XXvvsc967eO6FhXrv3mvvtb71f46LC/PP5DSwODmJ5wIvzEGfoBHMQZ+DPkENTFDkm8HT7wVuD4E+myB+vUSuBX0NTnkJtL/XaeNsIti3g54Yh/2Kct2O066Azox5ag3oBPwo6JWxL1Up8L9Y/+JN4unU8SegL0HvVerBvdwLOi9zCrRzxgB/Fvd5H3SrW+LZXyhdv10A3ht1XwOfQ6C/JLoX9O+w4WvQ3ozOGJaODaDPhyuNimf+DSL4uQ/v9jToedAt3aJL+POBzAbWCExhO0BruzVX8efHICpwSXn4+7UBZN4HHnG6JKDnQU8Z+ngZv70LOg7KpTamvmdAhzuZrl/XA/qBTgF3GQLykiymPB8CsAt0EHQCdAeI3sow/RjoJw8TrOGZf3YCU/DSJzbMkoER/MsdUyo1dQZ5ej4bsEgAvdVtoCevA+VSEw2MkTVnnGRjAS/AP8e63SC3p1Oxv4D2gIbIMVTkOdAF0KOd8LocL1ZzBgV+HWQZYwiIjETfURlWhBDo3wd39QCcWnMRX94GklELrNIdfseej0C5CJsDPgs4N5Q83ePlNYqIhafSPwWVhE+dwZTzA4ih2PPRWeFaS34Bkwq/nvO0hvmUqUUeLcP/Dd9tA4XpIuZL/dMZSjVL6PFMdwzpN3i4mJdAZ8hlLvMq1lKGBFDUqBE+5isvvA8/eNOBlP8t9igsW4DKW2rOiO+plBLmVBo+w/rjoFJrJjk9UVDA8w5ZwPmjBbo84zmsax18pISnp24EMcd7cnKoUE++iwFgqPwVxJSgotMq6Lj+H4c35gxdqZGp7EkQPZqGT6OviR68x4+g0hxCRsr7WMWdCTo9gwXXnd2Fc8KVvlclGiqwj/DhOVTEOyDvkEgew+KR+ZH7VZmnijStX1b1lgSNfqdhbQXJo2X4JiCJM8THCvFhDmfN9KYFvOXp9MRHQKUUUNJFLPwWbDhdskaDqfbXGKNCnyr2MBSmQNDvuaq9JDMjERWvsCzD574HK51IDpJLM6mizWznLECZz8MquyRo6ve4GGoRXvwZgdaDSuEuvA8Nb1OgcIVe9e2xAclQ76kEiGfSKL8CsXbQHcWvTyoT6CkDtKr0LPAW6Bw8tLQrKeF5Sea3lrEpjbG2heSeEASCo/TFv8c5NrXeY/SaprE9k0dL+UotHj7hGqWFuJhTNLGKNp3tHs60gq72TMKrMOwrPBXRZ+yqdBADGw5f/gBv9fu59R6w1CHIo1NzCQ+fFOgpvRFUgm61fdTZWdBSlzOWp+d609Z0oS7CGqrESlV4TE3gVLdwj8KnPKi2VUsZdTyXqAWc6+XpLc6y7NwxQE9dUsJbs+SSQmrHruJHYBluU4OQcGCjgs5an7tj2J5p0ijDr01F8RlDts7XeVugq6+VECVQ+HuuN2U+ahW+duyq+3A+b038wvaNBR3X13oVDeVukIw6NZfw6C+1xirkevEcumVTlTyG8LVjVypEXmJNtBTOuZ6FK9vUmlaN+1kvyKhTht8LnG6TQK9pUc3zLNBL/WHMONebtky1dIaKrtKTsfhOnlFq/CCGRZ23l1bRF0aSeC7RAjj3Kop4HywVz7NAl0CeMazaM75ZoyJrSOH7jF0pvHeU6h5hBhpVe8avVC/Ehl8EwLGA7WOoV8cWe0lp2kalfRMAmeJm9aaeBwUeIVgIfgjyjl3JU3nV8wRPBs593jtr5qD2LGX4HtmsNZKhJt0UzyyBridj1mRKQ47USxEvFG/w/4LcC4ECpLaFUjvmAV1hlPncc45qBVb84UsR9+PfjIyUxfuxHjbRsPgMfrDQzkuVQPe8RBH2ul5BU+v4SlLqoULt2JXe8QaIAOpD4D8AWQpmd/AqyHpTRfxU77TIq725OkW6b5leJu9XAp2bNAXrM4ceQilMMQSx5q2aIc5dbR409s2gmpbZdWcP6GTUZxLmukBh0Wob3BAy9OHBaPUFaBRH84LOizOMH1lhj1stY+sD1FB7PG/CNp1VA7o8/uQKAT9aTmvS2LibV+Q/lNSCrhzf+vqUR3V9xq4evrO8hmGdT8Ssp2bN9+8DevOhTgYc7vwMGuKlTOeR01g2y6B7nhVPA6WBpZxl0AcWdc5OGpiDPkFbmIM+QdD/A2kV0DcnKNgCAAAAAElFTkSuQmCC\" width=\"62.5\" height=\"19.5\" style=\"width: 62.5px; height: 19.5px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 51.325px 8px; transform-origin: 51.325px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e: that is, find the smallest integer \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003er\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 32.275px 8px; transform-origin: 32.275px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e such that \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAALAAAAAmCAYAAABkiBEAAAAGlUlEQVR4Xu2bTejuQxTH792TsGJBcRdXFOW1RF2JuiVFIaRb5GUhSW5IFhZueUmy8LKwsPC2UFKKhQWRtwVFLFiQ2InYu99PzbmdO/+Z38zze+b33Hlu86vT/3n+v5k5Z875zplzzsyze9d4hga2WAO7t1j2IfrQwK4B4AGCrdbAAPBWm28IPwA8MLDVGhgA3mrzDeEHgAcGtloDA8Bbbb4h/ADwwEBJAxerwV2ip0W/lBpv+v0A8LTG79XrJ0TXi77etHGOIb9rxPtO0X7RCUGOS9bQAXrcJ7rJzelVfb4nM0f43yi61fH/U59fFB3yfVoD+GwNfpHoQtGZoptFCH8gAOGjY2iUVVgbcE9rYLxV+PbU9hQJ84Ho0oY6wIs/HMb7T39PLEwYO7wkArxXiHbsAEsAmFX2lAiwfie6XQQQplZcL4az7RJ5/Opfx/v0Mrc5cnjAtdABDu0tJ8h9+vzyhGAG4GfU5mCqXWsAw8OE/FKffxUhJFvFO6kVNEerC/ZhB7FV3tp4C4q92NCtdfCKJL3bSQtGLpuQ/m29wyFmF88SADYhs25/MXW3Hbi18dpKt5nRWuvgR4n9j+gMUU149kdof7n+/rUpD4yQe0WPiY4KuDej82ZcWhuvmWAbHKilDtjdfhYRDvBYLJwLLa09Oze7evJp7YGN6Trelwz0wwZGWncBtTQeBrhBRCJyuogEieSE7+aJvKF4/4jouuAMUAc5xbUTerHKAckzz7mi30Xvi5LxoxuLvg+J8IzmIT/VZ0JAA9q6MbDFs8yBMA0w25PCobW/RY0IJZJPLYDjCTLJ10QPishSEQoFG9N1ErbjCcDM5cmgIwxA5k1N9XnRb6JPROeLaMeDDh8XvR7ekwRf6fqnQGyLgZIXYLOkyP5PDAnfq0SpUiAhHwkrC8oD3eLPIFo+DrUGhb+Mx4I9T0Q44MdPORveMycWZDJ8gF8JwCjhzaBgmDBZBiNb/yoIjHKMCZ4TYxigK+fWZbOWHtgnLyQu90dg+kLfrVz1kz4/IPIlR9Mrijo1MqgBIec0bGzsdIHIl6Ie1XcqRrlt2sJB+K7rgf/VGJ8HbDCed1TM+ZwIBbT/QTSV5E0CGPB+JsrFs/8Hht4rwBSyVdYlMiuFagng0li2cyFaqmTky0/eOXgQ5ADm+3pbYV9CBJ6cdy7JXanKIw4v9rS5BWIOshgG5jywB29uZRuAi0xqZ9lZu1bGY1qlsTwQU/rMvTfvWzoUIJu3WNs8uHlf8hXi8tRTkrvWZMYrXmR+4fpdINd+B78cgG3LYnIpb+oVukdtWp6RH08xsCm8BIS5ADYPVgKwD0HMg1toMZUcluSuBTC8SBBjLNkuYMfVhkfkpX22fGaMUwAuKZO+FtMRuxSZ1M4ytBsA3ll+zNnEdsESgD0QzcMT6gGcTQAYOXNxts8PTLap9kfBKQVgW5k57+tXzWSNbkXg9ta8lfdZMoQwAMNjKiFPATiVw8Q2aKEDi8Fzx8ZWeoW3JbB44KpCQDxpP1gOnH5SpbPs3kC5ijwtjLd0COGrF1NVgtRcarx3Cx2Yh50KNX2IQ5WGGvZk+SwXQvigOgVOAP5t2HoYIy7prAKQ3tu2MN7SAPbbb/bCi4TwyZ4Bw4M/B64WOigeB0u++JJP6dDmCHZiD+wFjk9ArDLBIQY1S4t/AfVZQUm9g3IV+VoYb2kAx9tvXEs1/laF8BUly/RpkwPMujqoOg4OQvpKSXVlKwaw98B+EAMvJ0R3iKgNE2I8K3pP1PLC90ji6pM4bF8K6UyfcU4TVwBi0PD+e5GV3+aEiyZbTV+/oKorWzGA40mxYnk4auTEhss5FjuhEJ4DYQWv4t2m2vYCYL/FTp7HV0zcH5umkhPvOFJ199J7HyL4QwkOBHAw7Jo4nvgomfcfi6yMxa7K3YmTRNzDoB/Oyh7i09tENWVTj6UaAFt77m9UV7ZyZbQXguCUZ7iVj6e1yVvAzbbzXGPwVmBh0SZsedwHwHjmeYwhOw7x/yo37OyCjf8pDTp9Q4THOTnww0EYiOAHr3dF34hwHPsT771N6GO8aAsIuGsBEAGwXQFIKY85w8MuFiEfR77Y9moRdzEYA5lqgAuP+Bct/I8YHTmmxmAh/i3K/dRoh/yluxCpCY//DQ10o4EB4G5MMQSZo4EB4DlaG3260cAAcDemGILM0cAA8BytjT7daGAAuBtTDEHmaGAAeI7WRp9uNDAA3I0phiBzNDAAPEdro083GjgMtEjgNmgI5+YAAAAASUVORK5CYII=\" width=\"88\" height=\"19\" style=\"width: 88px; height: 19px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 12.0417px 8px; transform-origin: 12.0417px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e. (If \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 127.558px 8px; transform-origin: 127.558px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e are not coprime, their GCD is a factor of \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 12.0417px 8px; transform-origin: 12.0417px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e.) If \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003er\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 54.8417px 8px; transform-origin: 54.8417px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e is odd, choose a new \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 120.967px 8px; transform-origin: 120.967px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and begin anew; if it is even, compute \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAMQAAAAmCAYAAACbKjTiAAAIIklEQVR4Xu2cW+h9UxDH//93Ep54oPBAhAe3iCJRIkW5JyG3kiRC8iBRLknKLXnwIDwokeJBInJNinhAkXhyi3fmo/31n9+y1p455+xzfuewdk37nN9ee61Zs+Y7M2vWnN/OHf3qEugS+EcCO7ssugS6BHZJoAOia0OXgJNAB8Ry1eE16/705Q7Re59SAh0QU0pza1/X2NcDjG5Z3hC956kl0AExtUR39Yd3uM7oazfE+fb5RqNjh7+9b/frjT5cHhu951kk0AExi7Tybfeypu8YHeJewWPcYPSw0S9GlxudNjwnrHo9331vuSwJdEAsR7K3DUr/uOv+B/t8YuEx8CKAAjD0vcZy1mKmXjsgZhJXuvEX1vIEo5+HN1D6c42uLnoghHrO6MvCm6QH2sCGRxvPVxrdVxiHtZhKB8T0y3Cgdflo0uIDFLzEf91DMM8rjM4w2m0Q+TF2n3fvRPh5stF5bvmerBgcPZZBusiN/6N9fsToXq8CHRDjgGAvcJTRqUZHGF04fL/J7m+Wwhy6esLubxg9n8AaC/uY0e2NvhJdbEwTZPmqkRIKiwBCk8bL3Dx8+cPuuwfSkLwBQxm+/v1qB0QOEFhxhEiG6CGjfYxaYQ7hkt9Mj40AaA438uHVxmj4HIx6BZ4CEAo5xcq19sHv20oWBYj77UE1Hd4BEa8qlu2nAQC/2R23j6v+xqjMDCk0YKGii9DqK6P/U4ZpakDgja9ygiaNfdyI4DFArF0TjB0Qkdru2OGtUKS8CPwBo0xs/J61e8loSwwbs7PRLaYGBN4YI7WfEV6ba8zzkOmjfdMjd0DE+iUrlNn4ZsMl+uQqs04xN5vdYkpAyMMS/nBpL9HaXKv9C9a26cE7IGIFw6pgfSLvkC3VUIaEeFdp2ZiLrS1Y0HOM2Bjua0RYx+ac77KUfuF5fqvRWUYHD11FAFf4t//Q/lC7f2/0slFUjsK7JB6w3LLgb9vnb53iLrqH0H6AdaEagPBTV02v1f4Ca9RMeGQBAbruGQT+3TDRs+1O9mVPo4/HBnGMrstHzYcNLQvGxWaZ0+PjjVAuFl1WJXNOUCvVKOfLolxmxD7Eg0EKHe09ULS7jJSpIbNCTh/eWZe3jMiG6QQcpb/D6Jnh+ad2P8m9XwOFeIFHrK42qfo7MTjjnmJUCw3xfqQ3JUPJQPG7vi8KCPrDABw2yNL3X8va8Zw5AfCmIcoAwocMqs1BOJ8ZyRpl04bKu0so896z49X6l9vGgtIP1qWcj7wBJ84YgmZWYhigVqpRjq29CONiKf11iX0hg5VJ1fKe30zW6qHYnwg0gJmSEZ8A0Ak5fe1dKIgUqxV6qG9AceQgP81F8mqFJYSU8lCLAuJ36+tdI53we92qGTDaf240tukeTbt6i8AESxfvhX5QIZhSGfR9uwGhxR6bD+lVWR0pTrR4KAJXa4PM6SxnEzqUKuXjx2zJzv89isUVHvBODcytRIFfn9ac/bvew6AvAnrLe0R8Z+ZOG+T5gVFpGFuAa7X/13hjHkLKgAUqXTwdaXDQuAl5dIGhNR8BPIqta4tWlmpkF3bedpFiecWuedPWc8koOuTSvgr+5WHkHQA3+5raFfGdlYfGKkHrDYH3Uq32aUCog5pbpBPl5lsWKDuxVbXTfBivZfn+HJiJDndKnmcp1ZhqvpFizQsIGbkIED7kUniZMSgR31n5MBYbdnlyvScvJU8sgw+/tA8Nd81D+E5bcaRHYpR9yU5yWe38fFrW34cB2fBP/BLPf2I0dkI69dwixZoXEDIKESD8+PJAxOgo4piHjfjOygk+W/sUv78Sb2Ptt4xZA4TvsKUccpmzxr7ZCU/ZLrMIsm7zhH9Yn1WXbkdzWhQQyH8snK4BQmBaNiBkvFqeXJlB5qCEgtYo/M1JbdJS9laqsRWnZZR4OzbVfj41l+l5Gj20yUxwRW2WBQifKBlLJNTGz3iXiO+M+GSwxzy5D+nYM3KGMppu1cAlIDy6auFSGaPNGm+vGhB+PplU4OihTWa1VtQmUqx5PYSPDsZSzX7zLUXLZB0jvjPiC8svrJOy6C+dKCkB4QVZAkK5dphWLrnMYWcmtMo2Y/OBDxaWBVXOHqvDzzspqVjnGqNIseYFRBlutKp25XW9jvjERUsBI74j3UiVXwyd+ExY+tyqBITytfTpKwcFBk5COekEEFFlYTS5VTz3C1wukj8E4/SVEPFMo1eM+N3zKjfJs8oiUqx5AQEfvu9aBKC+y/1jGT2USlgefs4aXXjeMu96gKYTJbU9hD/cQOk5bOEc4lmjp4w4EOFKo27W1Z64vXflgILyBU6Gqa1BsP5HK4CCMod19g6Ix5cp1LJ8fp9XC32j5z4k8odsGEwqdCl3udSoLN0oDyCRJ7VPexhRR8V7ii6YB/p1sZH/zySt5feAywBC7am/CtOtGrQGCCZ1txGWgPQbx+NPD4uQyedPrM8Ld6dzAl/fo/nQuebE4q27Z2AO/BTT/3SSNcJYMQ/qyqjBopbIn4qzf3rR6CMjSlEwcOXzsmxdY9EWpaJWCsUGEOw1WvVAvu6N0h7p0IP2mdo3Igz6gKcMEFgjAHynkUqF+Bt7HPgY6wNg/2qUrirO1DIxuK5NO532vPfPXQKhBGYBRJSBCgfrDboE1l0CswBik06n113unb81lcAsgNBhBzFh6pBjTefc2eoSaEogCwifjs38WKaLvEtgIyUQAYITP//PeTXJTcjIbOSCdKa3VwIRILaXuz56l8CKJdABsWKB9+HWWwIdEOu9Pp27FUvgL0tZPEVaPSsaAAAAAElFTkSuQmCC\" width=\"98\" height=\"19\" style=\"width: 98px; height: 19px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 86.725px 8px; transform-origin: 86.725px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, and compute the GCDs of \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAEYAAAAkCAYAAAA0EkzVAAACbElEQVRoQ+2Yuy8FQRTG3Z4CFQUFBYlC45EIlZBoJAoKOolXotAIaqFQqTwiSgn/AYXiJsQjOgkFBQUVUej5vmQmmayZzM69szKbO5N82WtnzM757Tlnzk6hKjYtgULkoicQwRg8I4KJYNySRvSY6DHRY0wE6tCxAk1BjTZMlRBKEsg8YFRD31BNpYOZAIAx6AuaETByB+ZKLHwS12fbG03Z36LMxfl78ugxP8LYblxvUxruMiyCMdCKYP4TDGN1A+qHXqEmaBQahGqhO+jYxa81Y3MXSnsio5/huiCSGbfAe6hBGLiG62algKHxO9A4dAKxDvhUjJcxy1utAlg5bHLjMaewcgi6hkYSUAjgAWqDHqE+Tb8rpFyAWYVVzCkshjo13kBv+hCWb+G6nIKC6mEphmuHpCrODJOXvSvR6BeI5fM+NKt50BzuMczYhiHmH1vLPRiZbGmoKXe8oY+J9x3qgNTcYwNk6g8+lKTRzB3tFm9hUub3iI8WNBjWK0/CSl0YqWHGYdypdn1QwRxBg+EuxN2ILQmGUC5EH3cjtnpPYcS5ggbThQXeCKO5TfeK3xJKEX8PQASj9vtwmqDB0EBZn/A3jecOxTrmCDpQwPmodlWgWYJJpgCrp+tO8Og16xDDinXDJXQI8VtI1jc0yPfxQBZgaMO0eLEsP2SjXXzR58KuPx7verTpu9pVFyQPqhZxM4vzGKdwdwFj27GcHhz6YBcwpVS7odtvXJ8LGPlRyfhshnxUu8GCSwtG3cZNFXGwRpayMBsYlvtLEE/X1UY425CvqreUtWf6PzYwmT485MkjGMPbiWAMYH4BMu+dJVUMypQAAAAASUVORK5CYII=\" width=\"35\" height=\"18\" style=\"width: 35px; height: 18px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"vertical-align:-5px\"\u003e\u003cimg src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAEYAAAAkCAYAAAA0EkzVAAACUklEQVRoQ+2Yuy8FQRTG3Z4CFQUFBYlC45EIlZBoJAoancSr0whqoVCpPCJKCf8BhUJCPKKTUFBQUBGFP8D3JTPJ5N6ZzM7Oxu64M8mX3Xtnd2fOb845c3ZLNbFpCZQiFz2BCMbgGRFMBOOWNKLHRI+JHmMi0ICOFWgaarZhqoZQkkAWAKMW+oHqqh3MFABMQN/QrIARwQBEG/QigFzj2Bc9pjJWIhhD/ohg/hIMY3UDGoTeoBZoHBqG6qF76NiW6XPuz9xj9kRGP8NxUSQzboEPUJMwdg3HzZwNtw2fGRgavwNNQicQ64AvZXQ5EP9qF8Bsk8uzPzMwp7BiBLqBxsqg0MBHqAN6ggY0/XlC0I2dCZhVPJk5hcVQt8Yb6E2fYvQtHJcTUCBkwvZpDOfRlA/wBkOjXyGWz/vQnGYi8/iPYcbGiXLCthY8GJlsaagpd7yjj4n3A+qC1NxjA5RXv7fHSKOZOzot3sKkzPeREJoXGNYrz8JKXRipYcbLuFPthkAFc/QCo+aBcjCEcikgcDdiawwkjDhXLzA9eMCtMJrbdL84l1Au8HsIIhi1PwSn8QJDA2V9wnMazx2KdcwRdKCAC6HalQtWngKsnq77gkevWYcYVqxjrqBDiO9Csr7hgL3QXcFdhTbMiIVl+SEb7eJCnwu7Ksxw/bQZWrWbet1cwNh2rNSTKOKNLmDSVLtFtDnRnFzAyJdKxmcrFEK1mwiC7qKkYNRt3FQRp55EEW+0gWG5vwTx67raCGcbCqXqdWZvA+P8wP9yQwRjWMkIxgDmF5EMfSVCIHhFAAAAAElFTkSuQmCC\" width=\"35\" height=\"18\" style=\"width: 35px; height: 18px;\"\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 1.94167px 8px; transform-origin: 1.94167px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e respectively. If one of these is non-trivial – neither 1 nor \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 176.575px 8px; transform-origin: 176.575px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e – it is the desired factor; if both are trivial, choose a new \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and start over.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 107.733px 8px; transform-origin: 107.733px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eOn a quantum computer, for given \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 3.88333px 8px; transform-origin: 3.88333px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003er\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 218.875px 8px; transform-origin: 218.875px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e can be found efficiently. On a classical computer, it can't (as far as we know), but it can still be computed.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 63px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 31.5px; text-align: left; transform-origin: 384px 31.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 366.7px 8px; transform-origin: 366.7px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eYour task is to implement Shor's algorithm. The input will be the product of a small number of distinct primes, and your function should return a factor \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ef\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 71.1833px 8px; transform-origin: 71.1833px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, the randomly-chosen \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 31.1083px 8px; transform-origin: 31.1083px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, its order \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003er\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 41.225px 8px; transform-origin: 41.225px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, the number \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eq\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 119.808px 8px; transform-origin: 119.808px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e, and (for informational purposes only) the number of \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 131.617px 8px; transform-origin: 131.617px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e's tried until the algorithm found a factor. If \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 129.125px 8px; transform-origin: 129.125px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e are not coprime, you may return NaN for \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003er\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eq\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 1.94167px 8px; transform-origin: 1.94167px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 84.5px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 42.25px; text-align: left; transform-origin: 384px 42.25px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 24.5px 8px; transform-origin: 24.5px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eNote 1: \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 15.5583px 8px; transform-origin: 15.5583px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 157.925px 8px; transform-origin: 157.925px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e not being coprime should be a rare event for such \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003eN\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 161.558px 8px; transform-origin: 161.558px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e. As such, the test suite will check that you don't get lucky \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 9.725px 8px; transform-origin: 9.725px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"font-style: italic; \"\u003etoo\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 78.175px 8px; transform-origin: 78.175px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e often. Solutions that call \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 30.8px 8px; transform-origin: 30.8px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"font-family: Menlo, Monaco, Consolas, \u0026quot;Courier New\u0026quot;, monospace; perspective-origin: 30.8px 8.5px; transform-origin: 30.8px 8.5px; \"\u003efactor()\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 47.45px 8px; transform-origin: 47.45px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e and claim that \u003c/span\u003e\u003c/span\u003e\u003cspan style=\"font-family: \u0026quot;STIXGeneral\u0026quot;, \u0026quot;STIXGeneral-webfont\u0026quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);\"\u003ea\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 177.75px 8px; transform-origin: 177.75px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e just so happened to be one of the factors returned every single time will get rejected; valid solutions should not be affected by this. If yours is, or if you otherwise happen to get unlucky with the inputs such that the test suite times out, submit your solution again.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 374.075px 8px; transform-origin: 374.075px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eNote 2: the test suite bans a few keywords, and \"factor\" is among them, so avoid this word in comments, variable names etc.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function [f, a, r, q, cnt] = shor(N)\r\n\r\nend\r\n","test_suite":"%% \r\ns = [\r\n        \"% Compute x^y mod for integers x, y, z\"\r\n        \"function res = modexp(x, y, z)\"\r\n        \"    res = 1;\"\r\n        \"    x = mod(x, z);\"\r\n        \"    while y\"\r\n        \"        if mod(y, 2)\"\r\n        \"            res = mod(res*x, z);\"\r\n        \"        end\"\r\n        \"        x = mod(x^2, z);\"\r\n        \"        y = floor(y/2);\"\r\n        \"    end\"\r\n        \"end\"\r\n    ];\r\nwritelines(s, \"modexp.m\", WriteMode = \"overwrite\")\r\n% No test here, this just writes out the modexp function used by the test suite\r\n\r\n%rng(0xDEADBEEF)\r\n\r\n%%\r\nNcnt = 20;\r\npmax = 1e4;\r\n\r\np = primes(pmax);\r\nNp = numel(p);\r\n\r\nlenp = length(num2str(p(end)));\r\nlenN = length(num2str(p(end)^2));\r\n\r\nT = NaN(1, Ncnt);\r\nnumNaN = 0;\r\n\r\nfor i = 1:Ncnt\r\n\r\n    i1 = randi(Np);\r\n    while true\r\n        i2 = randi(Np);\r\n        if i2 ~= i1\r\n            break\r\n        end\r\n    end\r\n\r\n    N = p(i1) * p(i2);\r\n\r\n    tic\r\n    [f, a, r, q, cnt] = shor(N);\r\n    T(i) = toc;\r\n    \r\n    assert(~mod(N, f), \"f is not a factor of N.\")\r\n    assert(f ~= 1 \u0026\u0026 f ~= N, \"f is not a non-trivial factor of N.\")\r\n    \r\n    Nstars = round(T(i)*10);\r\n    stars = [repelem('*', Nstars) repelem(' ', Nstars \u003e 0)];\r\n    fprintf(\"%\" + lenN + \"u = %\" + lenp + \"u*%\" + lenp + \"u (a = %\" + lenN + \"u, r = %\" + lenN + \"u, q = %\" + lenN + \"u, tries = %2u) %s%.2fs\\n\", N, f, N/f, a, r, q, cnt, stars, T(i));\r\n\r\n    if ~isnan(r)\r\n        assert(modexp(a, r, N) == 1, \"a^r = 1 mod N failed.\")\r\n        assert(modexp(a, r/2, N) == q, \"a^(r/2) = q mod N failed.\")\r\n        assert(f == gcd(q+1, N) || f == gcd(q-1, N), \"f does not obtain from q.\")\r\n    else\r\n        numNaN = numNaN + 1;\r\n    end\r\n\r\nend\r\n\r\nfprintf(\"Took %.2f seconds to find factors of %u numbers using Shor's algorithm!\\n\", sum(T), Ncnt)\r\nfprintf(\"gcd(a, N) \u003e 1 in %u / %u cases.\\n\", numNaN, Ncnt)\r\n\r\nassert(numNaN \u003c Ncnt/4, \"You got lucky a little TOO often, friend.\")\r\n\r\n%%\r\nNcnt = 20;\r\npmax = 5e2;\r\n\r\np = primes(pmax);\r\nNp = numel(p);\r\n\r\nlenp = length(num2str(p(end)^2));\r\nlenN = length(num2str(p(end)^3));\r\n\r\nT = NaN(1, Ncnt);\r\nnumNaN = 0;\r\n\r\nfor i = 1:Ncnt\r\n\r\n    i1 = randi(Np);\r\n    while true\r\n        i2 = randi(Np);\r\n        if i2 ~= i1\r\n            break\r\n        end\r\n    end\r\n    while true\r\n        i3 = randi(Np);\r\n        if i3 ~= i1 \u0026\u0026 i3 ~= i2\r\n            break\r\n        end\r\n    end\r\n\r\n    N = p(i1) * p(i2) * p(i3);\r\n\r\n    tic\r\n    [f, a, r, q, cnt] = shor(N);\r\n    T(i) = toc;\r\n    \r\n    assert(~mod(N, f), \"f is not a factor of N.\")\r\n    assert(f ~= 1 \u0026\u0026 f ~= N, \"f is not a non-trivial factor of N.\")\r\n    \r\n    Nstars = round(T(i)*10);\r\n    stars = [repelem('*', Nstars) repelem(' ', Nstars \u003e 0)];\r\n    fprintf(\"%\" + lenN + \"u = %\" + lenp + \"u*%\" + lenp + \"u (a = %\" + lenN + \"u, r = %\" + lenN + \"u, q = %\" + lenN + \"u, tries = %2u) %s%.2fs\\n\", N, f, N/f, a, r, q, cnt, stars, T(i));\r\n\r\n    if ~isnan(r)\r\n        assert(modexp(a, r, N) == 1, \"a^r = 1 mod N failed.\")\r\n        assert(modexp(a, r/2, N) == q, \"a^(r/2) = q mod N failed.\")\r\n        assert(f == gcd(q+1, N) || f == gcd(q-1, N), \"f does not obtain from q.\")\r\n    else\r\n        numNaN = numNaN + 1;\r\n    end\r\n\r\nend\r\n\r\nfprintf(\"Took %.2f seconds to find factors of %u numbers using Shor's algorithm!\\n\", sum(T), Ncnt)\r\nfprintf(\"gcd(a, N) \u003e 1 in %u / %u cases.\\n\", numNaN, Ncnt)\r\n\r\nassert(numNaN \u003c Ncnt/4, \"You got lucky a little TOO often, friend.\")\r\n\r\n%%\r\nfiletext = fileread(\"shor.m\");\r\nillegal = contains(filetext, \"assignin\") || contains(filetext, \"assert\") || contains(filetext, \"regexp\") || contains(filetext, \"str2num\") || contains(filetext, \"factor\"); \r\nassert(~illegal, \"Illegal keyword found.\")\r\n","published":true,"deleted":false,"likes_count":0,"comments_count":4,"created_by":332395,"edited_by":332395,"edited_at":"2025-02-18T07:30:07.000Z","deleted_by":null,"deleted_at":null,"solvers_count":4,"test_suite_updated_at":"2025-02-18T07:30:07.000Z","rescore_all_solutions":false,"group_id":1,"created_at":"2025-02-09T12:22:40.000Z","updated_at":"2025-02-18T21:57:39.000Z","published_at":"2025-02-09T12:22:40.000Z","restored_at":null,"restored_by":null,"spam":null,"simulink":false,"admin_reviewed":false,"description_opc":"{\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eShor's algorithm, proposed in 1994 by Peter Shor, is an algorithm for factoring numbers that runs in polynomial time (polynomial in the number of digits/bits of the input) on a quantum computer. It works as follows.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eTo find a factor of a given integer \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, which we assume to be an odd composite number that is not a prime power, pick a random integer \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003e1 \u0026lt; a \u0026lt; N\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e. Next, if \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e is coprime to \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, compute the order of \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e in the group \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003e(\\\\mathbb{Z}/N\\\\mathbb{Z})^\\\\times\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e: that is, find the smallest integer \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003er\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e such that \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea^r \\\\equiv 1\\\\;\\\\mathrm{mod}\\\\;N\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e. (If \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e are not coprime, their GCD is a factor of \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e.) If \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003er\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e is odd, choose a new \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and begin anew; if it is even, compute \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eq = a^{r/2} \\\\;\\\\mathrm{mod}\\\\; N\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, and compute the GCDs of \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eq+1\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eq-1\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e respectively. If one of these is non-trivial – neither 1 nor \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e – it is the desired factor; if both are trivial, choose a new \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and start over.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eOn a quantum computer, for given \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003er\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e can be found efficiently. On a classical computer, it can't (as far as we know), but it can still be computed.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eYour task is to implement Shor's algorithm. The input will be the product of a small number of distinct primes, and your function should return a factor \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ef\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, the randomly-chosen \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, its order \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003er\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, the number \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eq\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e, and (for informational purposes only) the number of \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e's tried until the algorithm found a factor. If \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e are not coprime, you may return NaN for \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003er\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eq\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eNote 1: \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e and \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e not being coprime should be a rare event for such \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e. As such, the test suite will check that you don't get lucky \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003etoo\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e often. Solutions that call \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:rFonts w:cs=\\\"monospace\\\"/\u003e\u003c/w:rPr\u003e\u003cw:t\u003efactor()\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and claim that \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:customXml w:element=\\\"equation\\\"\u003e\u003cw:customXmlPr\u003e\u003cw:attr w:name=\\\"displayStyle\\\" w:val=\\\"false\\\"/\u003e\u003c/w:customXmlPr\u003e\u003cw:r\u003e\u003cw:t\u003ea\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:customXml\u003e\u003cw:r\u003e\u003cw:t\u003e just so happened to be one of the factors returned every single time will get rejected; valid solutions should not be affected by this. If yours is, or if you otherwise happen to get unlucky with the inputs such that the test suite times out, submit your solution again.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eNote 2: the test suite bans a few keywords, and \\\"factor\\\" is among them, so avoid this word in comments, variable names etc.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\",\"relationship\":null}],\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"target\":\"/matlab/document.xml\",\"relationshipId\":\"rId1\"}]}"}],"term":"tag:\"shor\"","current_player_id":null,"fields":[{"name":"page","type":"integer","callback":null,"default":1,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"per_page","type":"integer","callback":null,"default":50,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"sort","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"body","type":"text","callback":null,"default":"*:*","directive":null,"facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":false},{"name":"group","type":"string","callback":null,"default":null,"directive":"group","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"difficulty_rating_bin","type":"string","callback":null,"default":null,"directive":"difficulty_rating_bin","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"id","type":"integer","callback":null,"default":null,"directive":"id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"tag","type":"string","callback":null,"default":null,"directive":"tag","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"product","type":"string","callback":null,"default":null,"directive":"product","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_at","type":"timeframe","callback":{},"default":null,"directive":"created_at","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"profile_id","type":"integer","callback":null,"default":null,"directive":"author_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_by","type":"string","callback":null,"default":null,"directive":"author","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player_id","type":"integer","callback":null,"default":null,"directive":"solver_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player","type":"string","callback":null,"default":null,"directive":"solver","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"solvers_count","type":"integer","callback":null,"default":null,"directive":"solvers_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"comments_count","type":"integer","callback":null,"default":null,"directive":"comments_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"likes_count","type":"integer","callback":null,"default":null,"directive":"likes_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leader_id","type":"integer","callback":null,"default":null,"directive":"leader_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leading_solution","type":"integer","callback":null,"default":null,"directive":"leading_solution","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true}],"filters":[{"name":"asset_type","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":"\"cody:problem\"","prepend":true},{"name":"profile_id","type":"integer","callback":{},"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":"author_id","static":null,"prepend":true}],"query":{"params":{"per_page":50,"term":"tag:\"shor\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"shor\"","","\"","shor","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f736216c6c8\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f736216c628\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f736216bb88\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f736216c948\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f736216c8a8\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f736216c808\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f736216c768\u003e":"tag:\"shor\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f736216c768\u003e":"tag:\"shor\""},"queried_facets":{}},"query_backend":{"connection":{"configuration":{"index_url":"http://index-op-v2/solr/","query_url":"http://search-op-v2/solr/","direct_access_index_urls":["http://index-op-v2/solr/"],"direct_access_query_urls":["http://search-op-v2/solr/"],"timeout":10,"vhost":"search","exchange":"search.topic","heartbeat":30,"pre_index_mode":false,"host":"rabbitmq-eks","port":5672,"username":"search","password":"J3bGPZzQ7asjJcCk","virtual_host":"search","indexer":"amqp","http_logging":"true","core":"cody"},"query_connection":{"uri":"http://search-op-v2/solr/cody/","proxy":null,"connection":{"parallel_manager":null,"headers":{"User-Agent":"Faraday v1.0.1"},"params":{},"options":{"params_encoder":"Faraday::FlatParamsEncoder","proxy":null,"bind":null,"timeout":null,"open_timeout":null,"read_timeout":null,"write_timeout":null,"boundary":null,"oauth":null,"context":null,"on_data":null},"ssl":{"verify":true,"ca_file":null,"ca_path":null,"verify_mode":null,"cert_store":null,"client_cert":null,"client_key":null,"certificate":null,"private_key":null,"verify_depth":null,"version":null,"min_version":null,"max_version":null},"default_parallel_manager":null,"builder":{"adapter":{"name":"Faraday::Adapter::NetHttp","args":[],"block":null},"handlers":[{"name":"Faraday::Response::RaiseError","args":[],"block":null}],"app":{"app":{"ssl_cert_store":{"verify_callback":null,"error":null,"error_string":null,"chain":null,"time":null},"app":{},"connection_options":{},"config_block":null}}},"url_prefix":"http://search-op-v2/solr/cody/","manual_proxy":false,"proxy":null},"update_format":"RSolr::JSON::Generator","update_path":"update","options":{"url":"http://search-op-v2/solr/cody"}}},"query":{"params":{"per_page":50,"term":"tag:\"shor\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"shor\"","","\"","shor","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f736216c6c8\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f736216c628\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f736216bb88\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f736216c948\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f736216c8a8\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f736216c808\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f736216c768\u003e":"tag:\"shor\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f736216c768\u003e":"tag:\"shor\""},"queried_facets":{}},"options":{"fields":["id","difficulty_rating"]},"join":" "},"results":[{"id":60790,"difficulty_rating":"medium"}]}}