{"page":"\u003clink rel=\"stylesheet\" href=\"https://lessonplanet.com/assets/packs/css/resources-c03aa079.css\" /\u003e\n\u003clink rel=\"stylesheet\" href=\"https://lessonplanet.com/assets/packs/css/lp_boclips_stylesheets-517835be.css\" media=\"all\" /\u003e\n\u003cdiv data-title='How Shor\u0026#39;s Algorithm Factors 314191' data-url='/boclips/videos/5f7dd1758cd8ed7a1e388da4' data-video-url='/boclips/videos/5f7dd1758cd8ed7a1e388da4' id='bo_player_modal'\u003e\n\u003cdiv class='boclips-resource-page modal-dialog panel-container'\u003e\n\u003cdiv class='react-notifications-root'\u003e\u003c/div\u003e\n\u003cdiv class='rp-header'\u003e\n\u003cdiv class='rp-type'\u003e\n\u003ci aria-hidden='true' class='fai fa-regular fa-circle-play'\u003e\u003c/i\u003e\nVideo\n\u003c/div\u003e\n\u003ch1 class='rp-title' id='video-title'\u003e\nHow Shor\u0026#39;s Algorithm Factors 314191\n\u003c/h1\u003e\n\u003cdiv class='rp-actions'\u003e\n\u003cdiv class='mr-1'\u003e\n\u003ca class=\"btn btn-success\" data-posthog-event=\"Signup: LP Signup Activity\" data-posthog-location=\"body_link_boclips\" data-remote=\"true\" href=\"/subscription/new\"\u003e\u003cspan\u003e\u003cspan\u003eGet Free Access\u003c/span\u003e\u003cspan class=\"\"\u003e for 10 Days\u003c/span\u003e\u003cspan\u003e!\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv class='rp-body'\u003e\n\u003cdiv class='rp-info'\u003e\n\u003cdiv aria-label='Hide resource details' class='rp-hide-info' role='button' tabindex='0'\u003e\u0026times;\u003c/div\u003e\n\u003ci aria-label='Expand resource details' class='rp-expand-info fai fa-solid fa-up-right-and-down-left-from-center' role='button' tabindex='0'\u003e\u003c/i\u003e\n\u003ci aria-label='Compress resource details' class='rp-compress-info fai fa-solid fa-down-left-and-up-right-to-center' role='button' tabindex='0'\u003e\u003c/i\u003e\n\u003cdiv class='rp-rating'\u003e\n\u003cspan class='resource-pool'\u003e\n\u003cspan class='pool-label'\u003ePublisher:\u003c/span\u003e\n\u003cspan class='pool-name'\u003e\n\u003cspan class='text'\u003e\u003ca data-publisher-id=\"30358008\" href=\"/search?publisher_ids%5B%5D=30358008\"\u003eMinutePhysics\u003c/a\u003e\u003c/span\u003e\n\u003c/span\u003e\n\u003c/span\u003e\n\u003c/div\u003e\n\u003cdiv class='rp-description'\u003e\n\u003cspan class='short-description'\u003eThis video explains how Shor’s Algorithm factors the pseudoprime number 314191 into its prime factors using a quantum computer. The quantum computation relies on the number-theoretic analysis of the factoring problem via modular...\u003c/span\u003e\n\u003cspan class='full-description hide'\u003eThis video explains how Shor’s Algorithm factors the pseudoprime number 314191 into its prime factors using a quantum computer. The quantum computation relies on the number-theoretic analysis of the factoring problem via modular arithmetic mod N (where N is the number to be factored), and finding the order or period of a random coprime number mod N. The exponential speedup comes in part from the use of the quantum fast fourier transform which achieves interference among frequencies that are not related to the period (period-finding is the goal of the QFT FFT).\u003cbr/\u003e\u003cbr/\u003eREFERENCES\u003cbr/\u003e\u003cbr/\u003eRSA Numbers (sample large numbers to try \u003ca href='https://en.wikipedia.org/wiki/RSA_numbers' target='_blank' rel='nofollow'\u003efactoring)\u003c/a\u003e\u003cbr/\u003e\u003cbr/\u003eIBM on \u003ca href='https://www.ibm.com/support/knowledgecenter/en/SSB23S1.1.0.13/gtps7/s7pkey.html' target='_blank' rel='nofollow'\u003eRSA\u003c/a\u003e\u003cbr/\u003e\u003cbr/\u003eModulo Multiplication Group \u003ca href='http://mathworld.wolfram.com/ModuloMultiplicationGroup.html' target='_blank' rel='nofollow'\u003eTables\u003c/a\u003e\u003cbr/\u003e\u003cbr/\u003eDifference of squares \u003ca href='https://en.wikipedia.org/wiki/Difference_of_two_squares' target='_blank' rel='nofollow'\u003efactorization\u003c/a\u003e \u003cbr/\u003e\u003cbr/\u003eEuclid’s \u003ca href='https://en.wikipedia.org/wiki/Euclideanalgorithm' target='_blank' rel='nofollow'\u003eAlgorithm\u003c/a\u003e \u003cbr/\u003e\u003cbr/\u003eRational sieve for \u003ca href='https://en.wikipedia.org/wiki/Rational_sieve' target='_blank' rel='nofollow'\u003efactoring\u003c/a\u003e \u003cbr/\u003e\u003cbr/\u003eGeneral Number field \u003ca href='https://en.wikipedia.org/wiki/Generalnumberfieldsieve' target='_blank' rel='nofollow'\u003eSieve\u003c/a\u003e \u003cbr/\u003e\u003cbr/\u003eScott Aaronson blog post about Shor’s \u003ca href='https://www.scottaaronson.com/blog/?p=208' target='_blank' rel='nofollow'\u003eAlgorithm\u003c/a\u003e \u003cbr/\u003e\u003cbr/\u003eExperimental implementation of Shor’s Algorithm (factoring 15, 21, and \u003ca href='https://arxiv.org/pdf/1903.00768.pdf' target='_blank' rel='nofollow'\u003e35)\u003c/a\u003e \u003cbr/\u003e\u003cbr/\u003eAdiabatic Quantum Computation factoring the number \u003ca href='https://arxiv.org/pdf/1706.08061.pdf' target='_blank' rel='nofollow'\u003e291311\u003c/a\u003e \u003cbr/\u003e\u003cbr/\u003eScott Aaronson course \u003ca href='https://www.scottaaronson.com/qclec/' target='_blank' rel='nofollow'\u003enotes\u003c/a\u003e \u003ca href='https://www.scottaaronson.com/qclec/combined.pdf' target='_blank' rel='nofollow'\u003e\u003c/a\u003e \u003cbr/\u003e\u003cbr/\u003eShor’s Algorithm on \u003ca href='https://www.quantiki.org/wiki/shors-factoring-algorithm' target='_blank' rel='nofollow'\u003eQuantiki\u003c/a\u003e \u003cbr/\u003e\u003cbr/\u003eTLS And SSL use RSA \u003ca href='https://en.wikipedia.org/wiki/TransportLayerSecurity' target='_blank' rel='nofollow'\u003eencryption\u003c/a\u003e \u003cbr/\u003e\u003cbr/\u003eDashlane security \u003ca href='https://www.dashlane.com/download/DashlaneSecurityWhitePaperOctober2018.pdf' target='_blank' rel='nofollow'\u003ewhitepaper\u003c/a\u003e \u003cbr/\u003e\u003cbr/\u003e\u003cbr/\u003eMinute Physics provides an energetic and entertaining view of old and new problems in physics -- all in a minute! Created by Henry Reich\u003c/span\u003e\n\u003c/div\u003e\n\u003cdiv class='action-container flex justify-between'\u003e\n\u003cbutton aria-expanded='false' aria-label='Read more description' class='rp-full-description' type='button'\u003e\n\u003ci class='fai fa-solid fa-align-left'\u003e\u003c/i\u003e\n\u003cspan id='read_more'\u003eRead More\u003c/span\u003e\n\u003c/button\u003e\n\u003cdiv class='rp-report'\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv aria-labelledby='resource-details-heading' class='rp-info-section'\u003e\n\u003ch2 class='title' id='resource-details-heading'\u003eResource Details\u003c/h2\u003e\n\u003cdiv class='rp-resource-details clearfix'\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eCurator Rating\u003c/dt\u003e\n\u003cdd\u003e\u003cspan class=\"star-rating\" aria-label=\"5.0 out of 5 stars\" role=\"img\"\u003e\u003ci class=\"fa-solid fa-star text-action\" aria-hidden=\"true\"\u003e\u003c/i\u003e\u003ci class=\"fa-solid fa-star text-action\" aria-hidden=\"true\"\u003e\u003c/i\u003e\u003ci class=\"fa-solid fa-star text-action\" aria-hidden=\"true\"\u003e\u003c/i\u003e\u003ci class=\"fa-solid fa-star text-action\" aria-hidden=\"true\"\u003e\u003c/i\u003e\u003ci class=\"fa-solid fa-star text-action\" aria-hidden=\"true\"\u003e\u003c/i\u003e\u003c/span\u003e\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt class=\"educator-rating-title\"\u003eEducator Rating\u003c/dt\u003e\u003cdd\u003e\u003cdiv class=\"educator-rating-details\" data-path=\"/educator_ratings/rrp_data?resourceable_id=206416\u0026amp;resourceable_type=Boclips%3A%3AVideoMetadata\"\u003e\u003cspan class=\"not-yet-rated\"\u003eNot yet Rated\u003c/span\u003e\u003c/div\u003e\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eMedia Length\u003c/dt\u003e\n\u003cdd\u003e4:40\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eGrade\u003c/dt\u003e\u003cdd title=\"Grade\"\u003e12th - Higher Ed\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eSubjects\u003c/dt\u003e\u003cdd\u003e\u003cspan\u003e\u003ca href=\"/search?grade_ids%5B%5D=258\u0026amp;grade_ids%5B%5D=259\u0026amp;search_tab_id=1\u0026amp;subject_ids%5B%5D=365220\"\u003eMath\u003c/a\u003e\u003c/span\u003e\u003c/dd\u003e\u003cdd class=\"text-muted\"\u003e\u003ci class=\"fa-solid fa-lock mr5\"\u003e\u003c/i\u003e9 more...\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eMedia Type\u003c/dt\u003e\u003cdd\u003e\u003cspan\u003e\u003ca href=\"/search?grade_ids%5B%5D=258\u0026amp;grade_ids%5B%5D=259\u0026amp;search_tab_id=2\u0026amp;type_ids%5B%5D=4543647\"\u003eInstructional Videos\u003c/a\u003e\u003c/span\u003e\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eSource:\u003c/dt\u003e\n\u003cdiv class='preview-source' data-animation='true' data-boundary='.rp-info' data-container='.rp-resource-details' data-html='false' data-title='Short, animated videos answering questions about how the world really works.' data-trigger='hover focus'\u003e\n\u003cspan\u003eMinutePhysics\u003c/span\u003e\n\u003ci aria-hidden='true' class='fa-solid fa-circle-info channel-tooltip-icon' id='channel-tooltip'\u003e\u003c/i\u003e\n\u003c/div\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eDate\u003c/dt\u003e\n\u003cdd\u003e2019\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003ci aria-hidden='true' class='fai fa-solid fa-language'\u003e\u003c/i\u003e\n\u003cdt\u003eLanguage\u003c/dt\u003e\u003cdd\u003eEnglish\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eAudiences\u003c/dt\u003e\u003cdd\u003e\u003cspan\u003e\u003ca href=\"/search?audience_ids%5B%5D=371079\u0026amp;grade_ids%5B%5D=258\u0026amp;grade_ids%5B%5D=259\u0026amp;search_tab_id=1\"\u003eFor Teacher Use\u003c/a\u003e\u003c/span\u003e\u003c/dd\u003e\u003cdd class=\"text-muted\"\u003e\u003ci class=\"fa-solid fa-lock mr5\"\u003e\u003c/i\u003e2 more...\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003cdiv class='detail'\u003e\n\u003cdl\u003e\n\u003cdt\u003eUsage Permissions\u003c/dt\u003e\u003cdd\u003eFine Print: Educational Use\u003c/dd\u003e\n\u003c/dl\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv aria-labelledby='additional-materials-heading' class='rp-info-section'\u003e\n\u003ch2 class='title' id='additional-materials-heading'\u003eAdditional Materials\u003c/h2\u003e\n\u003cdiv class='additional-material'\u003e\n\u003ci aria-hidden='true' class='fai fa-solid fa-lock'\u003e\u003c/i\u003e\n\u003ca class=\"text-muted\" title=\"Video Transcript\" data-html=\"true\" data-placement=\"bottom\" data-trigger=\"click\" data-content=\"\u003cdiv class=\u0026quot;text-center py-2\u0026quot;\u003e\u003ca class=\u0026quot;bold\u0026quot; href=\u0026quot;/auth/users/sign_in\u0026quot;\u003eSign in\u003c/a\u003e or \u003ca class=\u0026quot;bold text-danger\u0026quot; data-posthog-event=\u0026quot;Signup: LP Signup Activity\u0026quot; data-posthog-location=\u0026quot;body_link_boclips\u0026quot; data-remote=\u0026quot;true\u0026quot; href=\u0026quot;/subscription/new\u0026quot;\u003eJoin Now\u003c/a\u003e\u003c/div\u003e\" data-title=\"Get Full Access\" data-container=\"body\" rel=\"popover\" tabindex=\"0\" href=\"/subscription/new\"\u003eVideo Transcript\u003c/a\u003e\n\u003c/div\u003e\n\u003cdiv class='additional-material'\u003e\n\u003ci aria-hidden='true' class='fai fa-solid fa-lock'\u003e\u003c/i\u003e\n\u003ca class=\"text-muted\" title=\"Video Preview\" data-html=\"true\" data-placement=\"bottom\" data-trigger=\"click\" data-content=\"\u003cdiv class=\u0026quot;text-center py-2\u0026quot;\u003e\u003ca class=\u0026quot;bold\u0026quot; href=\u0026quot;/auth/users/sign_in\u0026quot;\u003eSign in\u003c/a\u003e or \u003ca class=\u0026quot;bold text-danger\u0026quot; data-posthog-event=\u0026quot;Signup: LP Signup Activity\u0026quot; data-posthog-location=\u0026quot;body_link_boclips\u0026quot; data-remote=\u0026quot;true\u0026quot; href=\u0026quot;/subscription/new\u0026quot;\u003eJoin Now\u003c/a\u003e\u003c/div\u003e\" data-title=\"Get Full Access\" data-container=\"body\" rel=\"popover\" tabindex=\"0\" href=\"/subscription/new\"\u003eVideo Preview\u003c/a\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv aria-labelledby='concepts-heading' class='rp-info-section'\u003e\n\u003ch2 class='title' id='concepts-heading'\u003eConcepts\u003c/h2\u003e\n\u003cdiv class='clearfix'\u003e\n\u003cdiv class='details-list concepts' data-identifier='Boclips::VideoDecorator5f7dd1758cd8ed7a1e388da4' data-type='concepts'\u003espace, encryption, remainders, factors, numbers, power, engineering\u003c/div\u003e\n\u003cdiv class='concepts-toggle-buttons' data-identifier='Boclips::VideoDecorator5f7dd1758cd8ed7a1e388da4'\u003e\n\u003cbutton aria-expanded='false' class='more btn-link' type='button'\u003e\n\u003cspan\u003eShow More\u003c/span\u003e\n\u003ci aria-hidden='true' class='fa-solid fa-caret-down ml5'\u003e\u003c/i\u003e\n\u003c/button\u003e\n\u003cbutton aria-expanded='true' class='less btn-link' style='display: none;' type='button'\u003e\n\u003cspan\u003eShow Less\u003c/span\u003e\n\u003ci aria-hidden='true' class='fa-solid fa-caret-up ml5'\u003e\u003c/i\u003e\n\u003c/button\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv aria-labelledby='additional-tags-heading' class='rp-info-section'\u003e\n\u003ch2 class='title' id='additional-tags-heading'\u003eAdditional Tags\u003c/h2\u003e\n\u003cdiv class='clearfix'\u003e\n\u003cdiv class='details-list keyterms' data-identifier='Boclips::VideoDecorator5f7dd1758cd8ed7a1e388da4' data-type='keyterms'\u003emultiple, guests, minus, common factor, shares factors, guess, algorithm, quantum computer, measure, science, superposition, check, start, number, pies, main video, guest, give, find, state, factor, experiments, shares, shores algorithm, video, break, remainder, physics\u003c/div\u003e\n\u003cdiv class='keyterms-toggle-buttons' data-identifier='Boclips::VideoDecorator5f7dd1758cd8ed7a1e388da4'\u003e\n\u003cbutton aria-expanded='false' class='more btn-link' type='button'\u003e\n\u003cspan\u003eShow More\u003c/span\u003e\n\u003ci aria-hidden='true' class='fa-solid fa-caret-down ml5'\u003e\u003c/i\u003e\n\u003c/button\u003e\n\u003cbutton aria-expanded='true' class='less btn-link' style='display: none;' type='button'\u003e\n\u003cspan\u003eShow Less\u003c/span\u003e\n\u003ci aria-hidden='true' class='fa-solid fa-caret-up ml5'\u003e\u003c/i\u003e\n\u003c/button\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv aria-labelledby='classroom-considerations-heading' class='rp-info-section'\u003e\n\u003ch2 class='title' id='classroom-considerations-heading'\u003eClassroom Considerations\u003c/h2\u003e\n\u003cdiv class='classroom-considerations'\u003e\u003cdiv class='fai fa-solid fa-bell'\u003e\u003c/div\u003eBest For: Explaining a topic\u003c/div\u003e\u003cdiv class='classroom-considerations'\u003e\u003cdiv class='fai fa-solid fa-bell'\u003e\u003c/div\u003eVideo is ad-free\u003c/div\u003e \n\u003c/div\u003e\n\u003cdiv aria-labelledby='educator-ratings-heading' class='rp-info-section'\u003e\n\u003ch2 class='title sr-only' id='educator-ratings-heading'\u003eEducator Ratings\u003c/h2\u003e\n\u003cdiv id=\"educator-ratings-root\"\u003e\u003c/div\u003e\u003cdiv id=\"all-educator-ratings-root\"\u003e\u003c/div\u003e\u003cdiv id=\"educator-rating-form-root\"\u003e\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv class='rp-resource'\u003e\n\u003cdiv aria-label='Show resource details' class='rp-show-info' role='button' tabindex='0'\u003e\n\u003ci class='fai fa-solid fa-align-left'\u003e\u003c/i\u003e\nShow resource details\n\u003c/div\u003e\n\u003cdiv aria-label='Video player' class='player' id='player-wrapper' role='region'\u003e\n\u003cdiv class='relative container mx-auto' id='lp-boclips-visitor-thumbnail'\u003e\n\u003ca class=\"block\" data-html=\"true\" data-placement=\"bottom\" data-trigger=\"click\" data-content=\"\u003cdiv class=\u0026quot;text-center py-2\u0026quot;\u003e\u003ca class=\u0026quot;bold\u0026quot; href=\u0026quot;/auth/users/sign_in\u0026quot;\u003eSign in\u003c/a\u003e or \u003ca class=\u0026quot;bold text-danger\u0026quot; data-posthog-event=\u0026quot;Signup: LP Signup Activity\u0026quot; data-posthog-location=\u0026quot;body_link_boclips\u0026quot; data-remote=\u0026quot;true\u0026quot; href=\u0026quot;/subscription/new\u0026quot;\u003eJoin Now\u003c/a\u003e\u003c/div\u003e\" data-title=\"Get Full Access\" data-container=\"body\" rel=\"popover\" tabindex=\"0\" aria-label=\"Play video: How Shor\u0026#39;s Algorithm Factors 314191\" href=\"/subscription/new\"\u003e\u003cimg class=\"resource-img img-thumbnail img-responsive z-10 lp-boclips-thumbnail w-full h-full lozad\" alt=\"How Shor\u0026#39;s Algorithm Factors 314191\" title=\"How Shor\u0026#39;s Algorithm Factors 314191\" onError=\"handleImageNotLoadedError(this)\" data-default-image=\"https://static.lp.lexp.cloud/images/attachment_defaults/resource/large/missing.png\" data-src=\"https://cdnapisec.kaltura.com/p/1776261/thumbnail/entry_id/1_4khog05n/width/250/vid_slices/3/vid_slice/1\" width=\"315\" height=\"220\" src=\"data:image/png;base64,R0lGODlhAQABAAD/ACwAAAAAAQABAAACADs\" /\u003e\n\u003cspan aria-hidden='true' class='flex justify-center items-center bg-white rounded-full w-16 h-16 absolute top-1/2 left-1/2 -mt-8 -ml-8 cursor-pointer z-0 border-2 border-primary drop-shadow-md lp-boclips-thumbnail-playBtn'\u003e\n\u003ci class='fa-solid fa-play text-primary text-3xl ml-1 drop-shadow-xl'\u003e\u003c/i\u003e\n\u003c/span\u003e\n\u003c/a\u003e\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n"}