<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@dbf9b5bd5fef4a4ba6dd7ea53a9e23eb" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<h2 class="hd hd-2 unit-title">Introduction</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@92097bcc202641da996968ff3bca7aee">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@92097bcc202641da996968ff3bca7aee" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="XBlockToXModuleShim" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Read <a href="/assets/courseware/v1/27b1ffcc1ac8ab3cf64b05531cbc8290/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Session15.pdf" target="[object Object]">Chapter 8.11–8.12 (PDF)</a> of <em>Mathematics for Computer Science</em> for 2.4 RSA Encryption.</p>
<p>View the <a href="/assets/courseware/v1/fb80e14da57448148ce2ec48ce9d6356/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_cp15.pdf" target="[object Object]">Section 2.4 In-Class Questions (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@1af1d38338f14c61b2db9595d477e205" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<h2 class="hd hd-2 unit-title">Lecture Video | RSA Public Key Encryption</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@8bb49c3c25f54424aef911c6a84b6d4f">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@8bb49c3c25f54424aef911c6a84b6d4f" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="XBlockToXModuleShim" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">RSA Public Key Encryption</h3>
<div
id="video_8bb49c3c25f54424aef911c6a84b6d4f"
class="video closed"
data-metadata='{"autoAdvance": false, "transcriptLanguages": {"en": "English"}, "savedVideoPosition": 0.0, "recordedYoutubeIsAvailable": true, "speed": null, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8bb49c3c25f54424aef911c6a84b6d4f/handler/transcript/translation/__lang__", "start": 0.0, "showCaptions": "true", "ytTestTimeout": 1500, "saveStateEnabled": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "generalSpeed": 1.0, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8bb49c3c25f54424aef911c6a84b6d4f/handler/transcript/available_translations", "completionPercentage": 0.95, "end": 0.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_rsa_ipod.mp4"], "ytMetadataEndpoint": "", "prioritizeHls": false, "autohideHtml5": false, "autoplay": false, "poster": null, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8bb49c3c25f54424aef911c6a84b6d4f/handler/publish_completion", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8bb49c3c25f54424aef911c6a84b6d4f/handler/xmodule_handler/save_user_state", "duration": 0.0, "captionDataDir": null, "completionEnabled": false, "streams": "1.00:ZUZ8VbX1YNQ"}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="8bb49c3c25f54424aef911c6a84b6d4f"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_8bb49c3c25f54424aef911c6a84b6d4f">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_8bb49c3c25f54424aef911c6a84b6d4f">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_rsa_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8bb49c3c25f54424aef911c6a84b6d4f/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8bb49c3c25f54424aef911c6a84b6d4f/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@0d4f44c3315a49038148a0d46e31a372">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@0d4f44c3315a49038148a0d46e31a372" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="XBlockToXModuleShim" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/5d832d0f3eba739dcf2f4ef399812257/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_RSA_Encytion.pdf" target="[object Object]">RSA Public Key Encryption (PDF)</a></p>
<p><a href="/assets/courseware/v1/88640c446813dfd339adcdb9a864b385/asset-v1:OCW+6.042J+2T2019+type@asset+block/RSAPublicKey_2.4_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@b2d573237eb94661a21dae0d9c675fb1" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<h2 class="hd hd-2 unit-title">Exercise | RSA Encryption</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@83ab1e6e2a7e434f8d9403100dcab252">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@83ab1e6e2a7e434f8d9403100dcab252" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="True" data-init="XBlockToXModuleShim" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_83ab1e6e2a7e434f8d9403100dcab252" class="problems-wrapper" role="group"
aria-labelledby="83ab1e6e2a7e434f8d9403100dcab252-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@83ab1e6e2a7e434f8d9403100dcab252" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@83ab1e6e2a7e434f8d9403100dcab252/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="83ab1e6e2a7e434f8d9403100dcab252-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@83ab1e6e2a7e434f8d9403100dcab252-problem-progress" tabindex="-1">
RSA Encryption
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@83ab1e6e2a7e434f8d9403100dcab252-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_83ab1e6e2a7e434f8d9403100dcab252_2_1" id="label_83ab1e6e2a7e434f8d9403100dcab252_2_1">The value <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>d</mi>
</math> in an RSA private key is derived from two prime numbers <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>q</mi>
</math> by</label>
<select name="input_83ab1e6e2a7e434f8d9403100dcab252_2_1" id="input_83ab1e6e2a7e434f8d9403100dcab252_2_1" aria-describedby="status_83ab1e6e2a7e434f8d9403100dcab252_2_1">
<option value="option_83ab1e6e2a7e434f8d9403100dcab252_2_1_dummy_default">Select an option</option>
<option value="Finding a number that is relatively prime to pq"> Finding a number that is relatively prime to pq</option>
<option value="Finding a number that is relatively prime to (p-1)(q-1)"> Finding a number that is relatively prime to (p-1)(q-1)</option>
<option value="Finding the inverse (mod pq) of a number that is relatively prime to pq"> Finding the inverse (mod pq) of a number that is relatively prime to pq</option>
<option value="Finding the inverse (mod (p-1)(q-1)) of a number that is relatively prime to (p-1)(q-1)"> Finding the inverse (mod (p-1)(q-1)) of a number that is relatively prime to (p-1)(q-1)</option>
<option value="Finding the inverse (mod pq) of a number that is relatively prime to (p-1)(q-1)"> Finding the inverse (mod pq) of a number that is relatively prime to (p-1)(q-1)</option>
<option value="Finding the inverse (mod (p-1)(q-1)) of a number that is relatively prime to pq"> Finding the inverse (mod (p-1)(q-1)) of a number that is relatively prime to pq</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_83ab1e6e2a7e434f8d9403100dcab252_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_83ab1e6e2a7e434f8d9403100dcab252_2_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="RSA Encryption " />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_83ab1e6e2a7e434f8d9403100dcab252" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_83ab1e6e2a7e434f8d9403100dcab252">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="83ab1e6e2a7e434f8d9403100dcab252-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="83ab1e6e2a7e434f8d9403100dcab252-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="83ab1e6e2a7e434f8d9403100dcab252-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="83ab1e6e2a7e434f8d9403100dcab252-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@65c9c2536a644bd889677e5e4ea70559" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<h2 class="hd hd-2 unit-title">Lecture Video | Reducing Factoring to SAT</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@05cfd3edbe6248ea920a60dc872feaef">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@05cfd3edbe6248ea920a60dc872feaef" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="XBlockToXModuleShim" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Reducing Factoring to SAT</h3>
<div
id="video_05cfd3edbe6248ea920a60dc872feaef"
class="video closed"
data-metadata='{"autoAdvance": false, "transcriptLanguages": {"en": "English"}, "savedVideoPosition": 0.0, "recordedYoutubeIsAvailable": true, "speed": null, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@05cfd3edbe6248ea920a60dc872feaef/handler/transcript/translation/__lang__", "start": 0.0, "showCaptions": "true", "ytTestTimeout": 1500, "saveStateEnabled": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "generalSpeed": 1.0, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@05cfd3edbe6248ea920a60dc872feaef/handler/transcript/available_translations", "completionPercentage": 0.95, "end": 0.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": ["https://archive.org/download/MIT6.042JS15/MIT6_042JS15_sat_factors_video_ipod.mp4"], "ytMetadataEndpoint": "", "prioritizeHls": false, "autohideHtml5": false, "autoplay": false, "poster": null, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@05cfd3edbe6248ea920a60dc872feaef/handler/publish_completion", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@05cfd3edbe6248ea920a60dc872feaef/handler/xmodule_handler/save_user_state", "duration": 0.0, "captionDataDir": null, "completionEnabled": false, "streams": "1.00:yWIQCewgfwY"}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="05cfd3edbe6248ea920a60dc872feaef"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_05cfd3edbe6248ea920a60dc872feaef">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_05cfd3edbe6248ea920a60dc872feaef">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://archive.org/download/MIT6.042JS15/MIT6_042JS15_sat_factors_video_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@05cfd3edbe6248ea920a60dc872feaef/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@05cfd3edbe6248ea920a60dc872feaef/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@8d7067ef3aee495f94f83491bcd57da5">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@8d7067ef3aee495f94f83491bcd57da5" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="XBlockToXModuleShim" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/0bf412c7b75a0b5367088a53068a3418/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_FactoringSAT.pdf" target="[object Object]">Reducing Factoring to SAT (PDF)</a></p>
<p><a href="/assets/courseware/v1/5fcd952a1a5476cd5209cc2b65713dae/asset-v1:OCW+6.042J+2T2019+type@asset+block/ReducingFactoring_2.4_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@163dc72c85654d33a4bfb3aeb4b0185b" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<h2 class="hd hd-2 unit-title">Exercise | Relative Primality</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@d79836f5b42047b3ab324004b33bbc93">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@d79836f5b42047b3ab324004b33bbc93" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="True" data-init="XBlockToXModuleShim" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_d79836f5b42047b3ab324004b33bbc93" class="problems-wrapper" role="group"
aria-labelledby="d79836f5b42047b3ab324004b33bbc93-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@d79836f5b42047b3ab324004b33bbc93" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@d79836f5b42047b3ab324004b33bbc93/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="d79836f5b42047b3ab324004b33bbc93-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@d79836f5b42047b3ab324004b33bbc93-problem-progress" tabindex="-1">
Relative Primality
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@d79836f5b42047b3ab324004b33bbc93-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_d79836f5b42047b3ab324004b33bbc93_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_d79836f5b42047b3ab324004b33bbc93_2_1" id="label_d79836f5b42047b3ab324004b33bbc93_2_1">How many numbers between 1 and 3780 (inclusive) are relatively prime to 3780?</label>
<input type="text" name="input_d79836f5b42047b3ab324004b33bbc93_2_1" id="input_d79836f5b42047b3ab324004b33bbc93_2_1" aria-describedby="status_d79836f5b42047b3ab324004b33bbc93_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_d79836f5b42047b3ab324004b33bbc93_2_1"/>
<span class="status unanswered" id="status_d79836f5b42047b3ab324004b33bbc93_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_d79836f5b42047b3ab324004b33bbc93_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_d79836f5b42047b3ab324004b33bbc93_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Relative Primality " />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_d79836f5b42047b3ab324004b33bbc93" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_d79836f5b42047b3ab324004b33bbc93">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="d79836f5b42047b3ab324004b33bbc93-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="d79836f5b42047b3ab324004b33bbc93-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="d79836f5b42047b3ab324004b33bbc93-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="d79836f5b42047b3ab324004b33bbc93-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@0772ac1c6e1d4dd99ecda4cc46dd06e2" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<h2 class="hd hd-2 unit-title">Exercise | RSA Computations</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@4e538314d33b4c07a2f5733b307ecd75">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@4e538314d33b4c07a2f5733b307ecd75" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="True" data-init="XBlockToXModuleShim" data-request-token="a3ceafdedbe611efb03e029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_4e538314d33b4c07a2f5733b307ecd75" class="problems-wrapper" role="group"
aria-labelledby="4e538314d33b4c07a2f5733b307ecd75-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@4e538314d33b4c07a2f5733b307ecd75" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@4e538314d33b4c07a2f5733b307ecd75/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="4e538314d33b4c07a2f5733b307ecd75-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@4e538314d33b4c07a2f5733b307ecd75-problem-progress" tabindex="-1">
RSA Computations
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@4e538314d33b4c07a2f5733b307ecd75-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_4e538314d33b4c07a2f5733b307ecd75_2_1">
<fieldset aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1">
<legend id="4e538314d33b4c07a2f5733b307ecd75_2_1-legend" class="response-fieldset-legend field-group-hd">The feasibility and security of the RSA public-key encryption system using keys based on 300-digit primes <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
<mo>,</mo>
<mi>q</mi>
</math> depends on the fact that certain computations listed below are "easy" and certain others are "hard."
<br/>
<br/>
1. Which of the following computations have to be "easy" in order for RSA to be feasible using keys based on 300 digit primes <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
<mo>,</mo>
<mi>q</mi>
</math>?
<br/>
<em> Note that there are some easy computations in this list that are not relevant to RSA.</em></legend>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_0-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> testing if a 300-digit number is prime
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_1-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> finding <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>q</mi>
</math> given <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
</math> and the product <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>::=</mo>
<mi>p</mi>
<mi>q</mi>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_2-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> finding <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>::=</mo>
<mi>p</mi>
<mi>q</mi>
</math> given <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
<mo>,</mo>
<mi>q</mi>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_3-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> finding 300-digit primes, <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
<mo>,</mo>
<mi>q</mi>
</math> given <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>::=</mo>
<mi>p</mi>
<mi>q</mi>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_4-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> finding <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi mathvariant="normal">&#934;<!-- &#934; --></mi>
<mo stretchy="false">(</mo>
<mi>p</mi>
<mi>q</mi>
<mo stretchy="false">)</mo>
</math> given <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
<mo>,</mo>
<mi>q</mi>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_5-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> generating 300 random digits
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_6-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> finding a 300-digit prime number
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_7-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> factoring a 600-digit number
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_8" class="field-input input-checkbox" value="choice_8"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_8-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_8" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> testing whether a 300-digit number is relatively prime to a given 600-digit number
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_9" class="field-input input-checkbox" value="choice_9"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_9-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_9" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> finding a 300-digit number that is relatively prime to a given 300-digit number
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_10" class="field-input input-checkbox" value="choice_10"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_10-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_10" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> finding an inverse (if there is one) modulo a 600-digit number of a 300-digit number
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_11" class="field-input input-checkbox" value="choice_11"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_11-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_11" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> raising a 600-digit number to a 600-digit power
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_2_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_12" class="field-input input-checkbox" value="choice_12"/><label id="4e538314d33b4c07a2f5733b307ecd75_2_1-choice_12-label" for="input_4e538314d33b4c07a2f5733b307ecd75_2_1_choice_12" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_2_1"> finding the remainder on division by a 600 digit number <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
</math> of a 600 digit number raised to a 600 digit power
</label>
</div>
<span id="answer_4e538314d33b4c07a2f5733b307ecd75_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_4e538314d33b4c07a2f5733b307ecd75_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_4e538314d33b4c07a2f5733b307ecd75_solution_1"/>
</div><div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_4e538314d33b4c07a2f5733b307ecd75_3_1">
<fieldset aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1">
<legend id="4e538314d33b4c07a2f5733b307ecd75_3_1-legend" class="response-fieldset-legend field-group-hd">2. Which of the following computations have to be "hard" in order for RSA to be secure using keys based on 300-digit primes <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
<mo>,</mo>
<mi>q</mi>
</math> ?
<br/>
<em>Note that there are some hard computations in this list that are not relevant to RSA.</em></legend>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_0-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> testing if a 300-digit number is prime
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_1-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> finding <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>q</mi>
</math> given <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
</math> and the product <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>::=</mo>
<mi>p</mi>
<mi>q</mi>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_2-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> finding <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>::=</mo>
<mi>p</mi>
<mi>q</mi>
</math> given <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
<mo>,</mo>
<mi>q</mi>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_3-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> finding 300-digit primes, <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
<mo>,</mo>
<mi>q</mi>
</math> given <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>::=</mo>
<mi>p</mi>
<mi>q</mi>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_4-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> finding <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi mathvariant="normal">&#934;<!-- &#934; --></mi>
<mo stretchy="false">(</mo>
<mi>p</mi>
<mi>q</mi>
<mo stretchy="false">)</mo>
</math> given <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>p</mi>
<mo>,</mo>
<mi>q</mi>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_5-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> generating 300 random digits
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_6-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> finding a 300-digit prime number
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_7-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> factoring a 600-digit number
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_8" class="field-input input-checkbox" value="choice_8"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_8-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_8" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> testing whether a 300-digit number is relatively prime to a given 600-digit number
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_9" class="field-input input-checkbox" value="choice_9"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_9-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_9" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> finding a 300-digit number that is relatively prime to a given 300-digit number
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_10" class="field-input input-checkbox" value="choice_10"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_10-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_10" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> finding an inverse (if there is one) modulo a 600-digit number of a 300-digit number
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_11" class="field-input input-checkbox" value="choice_11"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_11-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_11" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> raising a 600-digit number to a 600-digit power
</label>
</div>
<div class="field">
<input type="checkbox" name="input_4e538314d33b4c07a2f5733b307ecd75_3_1[]" id="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_12" class="field-input input-checkbox" value="choice_12"/><label id="4e538314d33b4c07a2f5733b307ecd75_3_1-choice_12-label" for="input_4e538314d33b4c07a2f5733b307ecd75_3_1_choice_12" class="response-label field-label label-inline" aria-describedby="status_4e538314d33b4c07a2f5733b307ecd75_3_1"> finding the remainder on division by a 600 digit number <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
</math> of a 600 digit number raised to a 600 digit power
</label>
</div>
<span id="answer_4e538314d33b4c07a2f5733b307ecd75_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_4e538314d33b4c07a2f5733b307ecd75_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_4e538314d33b4c07a2f5733b307ecd75_solution_2"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="RSA Computations" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_4e538314d33b4c07a2f5733b307ecd75" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_4e538314d33b4c07a2f5733b307ecd75">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="4e538314d33b4c07a2f5733b307ecd75-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="4e538314d33b4c07a2f5733b307ecd75-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="4e538314d33b4c07a2f5733b307ecd75-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="4e538314d33b4c07a2f5733b307ecd75-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>