<commit_before><!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
  "http://www.w3.org/TR/html4/loose.dtd">
<html xml:lang="en" >
<head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <link rel="stylesheet" type="text/css" href="crtAlgorithm.css">
    <title>Der Chinese Remainder Theorem Algorithm</title>
</head>
<body>
   <h1>The Chinese Remainder Theorem Algorithm</h1>
   
<!--l. 30--><p class="noindent">The <span class="cmbx-10">Chinese Remainder Theorem </span>Algorithm (<b>CRT</b>) is a solution method to solve simultaneous congruences. It will for example used to speed up the RSA algorithm, especially for the generation of digital signatures and decryption. Another application of the <span class="cmbx-10">Chinese Remainder Theorem</span> is to calculate the root of the <span
class="cmbx-10">Fiat-Shamir</span> method.

<p>How to use the according JCT plug-in is describes <a href="index.html">here</a>.</p>

<p>
 We have linear equations (congruences) of the form<br
class="newline" />
<!--l. 33--><p class="indent" >   <span
class="cmmi-10">x </span><span
class="cmsy-10">&#x2261; </span><span
class="cmmi-10">a</span><sub><span
class="cmr-7">0</span></sub><span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;m</span><sub><span
class="cmr-7">1</span></sub><span
class="cmmi-10">,      x </span><span
class="cmsy-10">&#x2261; </span><span
class="cmmi-10">a</span><sub><span
class="cmr-7">2</span></sub><span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;m</span><sub><span
class="cmr-7">2</span></sub><span
class="cmmi-10">,</span>      <span
class="cmmi-10">&#x2026;</span>     <span
class="cmmi-10">x </span><span
class="cmsy-10">&#x2261; </span><span
class="cmmi-10">a</span><sub><span
class="cmmi-7">n</span></sub><span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;m</span><sub><span
class="cmmi-7">n</span></sub>
<!--l. 39--><p class="noindent" >available with <span
class="cmmi-10">m</span><sub><span
class="cmr-7">1</span></sub><span
class="cmmi-10">,</span><span
class="cmmi-10">&#x2026;</span><span
class="cmmi-10">,m</span><sub><span
class="cmmi-7">n</span></sub> natural numbers which are paired coprime
and <span
class="cmmi-10">a</span><sub><span
class="cmr-7">1</span></sub><span
class="cmmi-10">,</span><span
class="cmmi-10">&#x2026;</span><span
class="cmmi-10">a</span><sub><span
class="cmmi-7">n</span></sub> integers. Now <br
class="newline" />
<!--l. 43--><p class="indent" >   <span
class="cmmi-10">m </span>= <span
class="cmex-10">&#x220F;</span>
  <span
class="cmmi-10">m</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">,      M</span><sub><span
class="cmmi-7">i</span></sub> = <span
class="cmmi-10">m&#x2215;m</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">,      </span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n</span>
<!--l. 47--><p class="indent" >   is calculated. There is a clear solution of the simultaneous congruences.It is
the equation<br
class="newline" />
<!--l. 50--><p class="indent" >   <span
class="cmmi-10">gcd</span>(<span
class="cmmi-10">m</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">,M</span><sub><span
class="cmmi-7">i</span></sub>) = 1<span
class="cmmi-10">,      </span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n</span>
<!--l. 54--><p class="indent" >   because of <span
class="cmmi-10">m</span><sub><span
class="cmmi-7">i</span></sub> the values are paired coprime. We use <span
class="cmbx-10">extended Euclidean</span>,
to calculate the numbers <span
class="cmmi-10">y</span><sub><span
class="cmmi-7">i</span></sub> <span
class="cmsy-10">&#x2208; </span><span
class="msbm-10">&#x2124;</span><span
class="cmmi-10">,</span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n </span>with<br
class="newline" />
<!--l. 58--><p class="indent" >   <span
class="cmmi-10">y</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">M</span><sub><span
class="cmmi-7">i</span></sub> <span
class="cmsy-10">&#x2261; </span>1<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;m</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">,      </span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n.</span>
<!--l. 62--><p class="indent" >   Now we can use<br
class="newline" />
<!--l. 64--><p class="indent" >   <span
class="cmmi-10">x </span>= (<span
class="cmex-10">&#x2211;</span>
  <span
class="cmmi-10">a</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">y</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">M</span><sub><span
class="cmmi-7">i</span></sub>)<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;m     </span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n</span>
<!--l. 68--><p class="indent" >   and get a solution <span
class="cmmi-10">x </span> of the simultaneous congruence. We assume the following theorem <span class="cite">[<a
href="#XJBu">1</a>]</span>
   <div class="newtheorem">
<!--l. 71--><p class="noindent" ><span class="head">
<span
class="cmbx-10">Theorem</span><span
class="cmbx-10">&#x00A0;1.1</span> </span><a
 id="x1-10011"></a> <span
class="cmti-10">Let </span><span
class="cmmi-10">m</span><sub><span
class="cmr-7">0</span></sub><span
class="cmmi-10">,</span><span
class="cmmi-10">&#x2026;</span><span
class="cmmi-10">,m</span><sub><span
class="cmmi-7">n</span></sub> <span
class="cmti-10">be paired coprime natural numbers and</span>
<span
class="cmti-10">let </span><span
class="cmmi-10">a</span><sub><span
class="cmr-7">0</span></sub><span
class="cmmi-10">,</span><span
class="cmmi-10">&#x2026;</span><span
class="cmmi-10">a</span><sub><span
class="cmmi-7">n</span></sub> <span
class="cmti-10">integer numbers. Then the simulantious congruences hat a solution <span
class="cmmi-10">x</span><span
class="cmti-10">,</span>
<span
class="cmti-10">which is clearly mod </span><span
class="cmmi-10">m </span>= <span
class="cmex-10">&#x220F;</span>
  <span
class="cmmi-10">m</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">,      </span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n.</span>
   </div>
<!--l. 78--><p class="indent" >   The proof of this can be seen in <span class="cite">[<a
href="#XJBu">1</a>]</span> nachlesen. We want to show the algorithm with an example. <br
class="newline" />
<!--l. 81--><p class="noindent" ><span
class="cmbx-10">Example  </span>We want to solve the simultaneous congruence
<!--l. 84--><p class="noindent" ><span
class="cmmi-10">x </span><span
class="cmsy-10">&#x2261; </span>2<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;</span>4<span
class="cmmi-10">,      x </span><span
class="cmsy-10">&#x2261; </span>1<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;</span>3<span
class="cmmi-10">,      x </span><span
class="cmsy-10">&#x2261; </span>4<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;</span>5<span
class="cmmi-10">,      x </span><span
class="cmsy-10">&#x2261; </span>3<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;</span>7<br
class="newline" />

<!--l. 88--><p class="noindent" >So is <span
class="cmmi-10">m</span><sub><span<commit_msg>Online help in crypto: typo in crtAlgorithm.html corrected (en only)<commit_after><!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
  "http://www.w3.org/TR/html4/loose.dtd">
<html xml:lang="en" >
<head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <link rel="stylesheet" type="text/css" href="crtAlgorithm.css">
    <title>Der Chinese Remainder Theorem Algorithm</title>
</head>
<body>
   <h1>The Chinese Remainder Theorem Algorithm</h1>
   
<!--l. 30--><p class="noindent">The <span class="cmbx-10">Chinese Remainder Theorem </span>Algorithm (<b>CRT</b>) is a solution method to solve simultaneous congruences. It will for example used to speed up the RSA algorithm, especially for the generation of digital signatures and decryption. Another application of the <span class="cmbx-10">Chinese Remainder Theorem</span> is to calculate the root of the <span
class="cmbx-10">Fiat-Shamir</span> method.

<p>How to use the according JCT plug-in is describes <a href="index.html">here</a>.</p>

<p>
 We have linear equations (congruences) of the form<br
class="newline" />
<!--l. 33--><p class="indent" >   <span
class="cmmi-10">x </span><span
class="cmsy-10">&#x2261; </span><span
class="cmmi-10">a</span><sub><span
class="cmr-7">0</span></sub><span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;m</span><sub><span
class="cmr-7">1</span></sub><span
class="cmmi-10">,      x </span><span
class="cmsy-10">&#x2261; </span><span
class="cmmi-10">a</span><sub><span
class="cmr-7">2</span></sub><span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;m</span><sub><span
class="cmr-7">2</span></sub><span
class="cmmi-10">,</span>      <span
class="cmmi-10">&#x2026;</span>     <span
class="cmmi-10">x </span><span
class="cmsy-10">&#x2261; </span><span
class="cmmi-10">a</span><sub><span
class="cmmi-7">n</span></sub><span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;m</span><sub><span
class="cmmi-7">n</span></sub>
<!--l. 39--><p class="noindent" >available with <span
class="cmmi-10">m</span><sub><span
class="cmr-7">1</span></sub><span
class="cmmi-10">,</span><span
class="cmmi-10">&#x2026;</span><span
class="cmmi-10">,m</span><sub><span
class="cmmi-7">n</span></sub> natural numbers which are paired coprime
and <span
class="cmmi-10">a</span><sub><span
class="cmr-7">1</span></sub><span
class="cmmi-10">,</span><span
class="cmmi-10">&#x2026;</span><span
class="cmmi-10">a</span><sub><span
class="cmmi-7">n</span></sub> integers. Now <br
class="newline" />
<!--l. 43--><p class="indent" >   <span
class="cmmi-10">m </span>= <span
class="cmex-10">&#x220F;</span>
  <span
class="cmmi-10">m</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">,      M</span><sub><span
class="cmmi-7">i</span></sub> = <span
class="cmmi-10">m&#x2215;m</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">,      </span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n</span>
<!--l. 47--><p class="indent" >   is calculated. There is a clear solution of the simultaneous congruences.It is
the equation<br
class="newline" />
<!--l. 50--><p class="indent" >   <span
class="cmmi-10">gcd</span>(<span
class="cmmi-10">m</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">,M</span><sub><span
class="cmmi-7">i</span></sub>) = 1<span
class="cmmi-10">,      </span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n</span>
<!--l. 54--><p class="indent" >   because of <span
class="cmmi-10">m</span><sub><span
class="cmmi-7">i</span></sub> the values are paired coprime. We use <span
class="cmbx-10">extended Euclidean</span>,
to calculate the numbers <span
class="cmmi-10">y</span><sub><span
class="cmmi-7">i</span></sub> <span
class="cmsy-10">&#x2208; </span><span
class="msbm-10">&#x2124;</span><span
class="cmmi-10">,</span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n </span>with<br
class="newline" />
<!--l. 58--><p class="indent" >   <span
class="cmmi-10">y</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">M</span><sub><span
class="cmmi-7">i</span></sub> <span
class="cmsy-10">&#x2261; </span>1<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;m</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">,      </span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n.</span>
<!--l. 62--><p class="indent" >   Now we can use<br
class="newline" />
<!--l. 64--><p class="indent" >   <span
class="cmmi-10">x </span>= (<span
class="cmex-10">&#x2211;</span>
  <span
class="cmmi-10">a</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">y</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">M</span><sub><span
class="cmmi-7">i</span></sub>)<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;m     </span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n</span>
<!--l. 68--><p class="indent" >   and get a solution <span
class="cmmi-10">x </span> of the simultaneous congruence. We assume the following theorem <span class="cite">[<a
href="#XJBu">1</a>]</span>
   <div class="newtheorem">
<!--l. 71--><p class="noindent" ><span class="head">
<span
class="cmbx-10">Theorem</span><span
class="cmbx-10">&#x00A0;1.1</span> </span><a
 id="x1-10011"></a> <span
class="cmti-10">Let </span><span
class="cmmi-10">m</span><sub><span
class="cmr-7">0</span></sub><span
class="cmmi-10">,</span><span
class="cmmi-10">&#x2026;</span><span
class="cmmi-10">,m</span><sub><span
class="cmmi-7">n</span></sub> <span
class="cmti-10">be paired coprime natural numbers and</span>
<span
class="cmti-10">let </span><span
class="cmmi-10">a</span><sub><span
class="cmr-7">0</span></sub><span
class="cmmi-10">,</span><span
class="cmmi-10">&#x2026;</span><span
class="cmmi-10">a</span><sub><span
class="cmmi-7">n</span></sub> <span
class="cmti-10">integer numbers. Then the simulantious congruences hat a solution <span
class="cmmi-10">x</span><span
class="cmti-10">,</span>
<span
class="cmti-10">which is clearly mod </span><span
class="cmmi-10">m </span>= <span
class="cmex-10">&#x220F;</span>
  <span
class="cmmi-10">m</span><sub><span
class="cmmi-7">i</span></sub><span
class="cmmi-10">,      </span>0 <span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">i </span><span
class="cmsy-10">&#x2264; </span><span
class="cmmi-10">n.</span>
   </div>
<!--l. 78--><p class="indent" >   The proof of this can be seen in <span class="cite">[<a
href="#XJBu">1</a>]</span>. We want to show the algorithm with an example.</p>

<!--l. 81--><p class="noindent" ><span
class="cmbx-10">Example  </span>We want to solve the simultaneous congruence
<!--l. 84--><p class="noindent" ><span
class="cmmi-10">x </span><span
class="cmsy-10">&#x2261; </span>2<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;</span>4<span
class="cmmi-10">,      x </span><span
class="cmsy-10">&#x2261; </span>1<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;</span>3<span
class="cmmi-10">,      x </span><span
class="cmsy-10">&#x2261; </span>4<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;</span>5<span
class="cmmi-10">,      x </span><span
class="cmsy-10">&#x2261; </span>3<span
class="cmmi-10">&#x00A0;mod</span><span
class="cmmi-10">&#x00A0;</span>7<br
class="newline" />

<!--l. 88--><p class="noindent" >So is <span
class="cmmi-10">m</span><sub><span
{'fraction_non_alphanumeric': 0.26941638247217037, 'fraction_numerical': 0.06743452802264976, 'mean_word_length': 5.969506726457399, 'pattern_counts': {'":': 0, '<': 855, '<?xml version=': 0, '>': 853, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 2}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5010714', 'n_tokens_mistral': 7095, 'n_tokens_neox': 6502, 'n_words': 1023}