1381 lines
54 KiB
HTML
1381 lines
54 KiB
HTML
<!DOCTYPE html>
|
||
<html class="writer-html5" lang="en" >
|
||
<head>
|
||
<meta charset="utf-8" />
|
||
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
|
||
<link rel="shortcut icon" href="../img/favicon.ico" />
|
||
<title>Number theory - CryptoTools documentation</title>
|
||
<link rel="stylesheet" href="../css/theme.css" />
|
||
<link rel="stylesheet" href="../css/theme_extra.css" />
|
||
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.8.0/styles/github.min.css" />
|
||
<link href="../assets/_mkdocstrings.css" rel="stylesheet" />
|
||
|
||
<script>
|
||
// Current page data
|
||
var mkdocs_page_name = "Number theory";
|
||
var mkdocs_page_input_path = "number-theory.md";
|
||
var mkdocs_page_url = null;
|
||
</script>
|
||
|
||
<!--[if lt IE 9]>
|
||
<script src="../js/html5shiv.min.js"></script>
|
||
<![endif]-->
|
||
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.8.0/highlight.min.js"></script>
|
||
<script>hljs.highlightAll();</script>
|
||
</head>
|
||
|
||
<body class="wy-body-for-nav" role="document">
|
||
|
||
<div class="wy-grid-for-nav">
|
||
<nav data-toggle="wy-nav-shift" class="wy-nav-side stickynav">
|
||
<div class="wy-side-scroll">
|
||
<div class="wy-side-nav-search">
|
||
<a href=".." class="icon icon-home"> CryptoTools documentation
|
||
</a>
|
||
</div>
|
||
|
||
<div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
|
||
<ul>
|
||
<li class="toctree-l1"><a class="reference internal" href="../introduction/">Introduction</a>
|
||
</li>
|
||
</ul>
|
||
<ul>
|
||
<li class="toctree-l1"><a class="reference internal" href="../installation/">Installation</a>
|
||
</li>
|
||
</ul>
|
||
<p class="caption"><span class="caption-text">Low-level cryptographic</span></p>
|
||
<ul class="current">
|
||
<li class="toctree-l1 current"><a class="reference internal current" href="#">Number theory</a>
|
||
<ul class="current">
|
||
<li class="toctree-l2"><a class="reference internal" href="#prime-numbers">prime numbers</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.primeNumber">primeNumber</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.primeNumber.are_coprime">are_coprime</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.primeNumber.getPrimeNumber">getPrimeNumber</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.primeNumber.getSmallPrimeNumber">getSmallPrimeNumber</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.primeNumber.get_n_prime_numbers">get_n_prime_numbers</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.primeNumber.get_prime_numbers">get_prime_numbers</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.primeNumber.isPrimeNumber">isPrimeNumber</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.primeNumber.isSafePrime">isSafePrime</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.primeNumber.sieveOfEratosthenes">sieveOfEratosthenes</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.primeNumber.sophieGermainPrime">sophieGermainPrime</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#fibonacci-sequence">Fibonacci sequence</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.numbers">numbers</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Numbers.numbers.fibonacci">fibonacci</a>
|
||
</li>
|
||
</ul>
|
||
</li>
|
||
<li class="toctree-l1"><a class="reference internal" href="../group-theory/">Group theory</a>
|
||
</li>
|
||
</ul>
|
||
<p class="caption"><span class="caption-text">Public Keys</span></p>
|
||
<ul>
|
||
<li class="toctree-l1"><a class="reference internal" href="../rsa/">RSA</a>
|
||
</li>
|
||
</ul>
|
||
<p class="caption"><span class="caption-text">Examples</span></p>
|
||
<ul>
|
||
<li class="toctree-l1"><a class="reference internal" href="../examples-rsa-keys/">Generating RSA Keys</a>
|
||
</li>
|
||
</ul>
|
||
</div>
|
||
</div>
|
||
</nav>
|
||
|
||
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
|
||
<nav class="wy-nav-top" role="navigation" aria-label="Mobile navigation menu">
|
||
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
|
||
<a href="..">CryptoTools documentation</a>
|
||
|
||
</nav>
|
||
<div class="wy-nav-content">
|
||
<div class="rst-content"><div role="navigation" aria-label="breadcrumbs navigation">
|
||
<ul class="wy-breadcrumbs">
|
||
<li><a href=".." class="icon icon-home" aria-label="Docs"></a></li>
|
||
<li class="breadcrumb-item">Low-level cryptographic</li>
|
||
<li class="breadcrumb-item active">Number theory</li>
|
||
<li class="wy-breadcrumbs-aside">
|
||
</li>
|
||
</ul>
|
||
<hr/>
|
||
</div>
|
||
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
|
||
<div class="section" itemprop="articleBody">
|
||
|
||
<h1 id="number-theory">Number Theory</h1>
|
||
<p>For generating keys, we need strong prime number, they are the basis. CryptoTools provides functions for generating these numbers.</p>
|
||
<h2 id="prime-numbers">prime numbers</h2>
|
||
|
||
|
||
<div class="doc doc-object doc-module">
|
||
|
||
|
||
|
||
<a id="Cryptotools.Numbers.primeNumber"></a>
|
||
<div class="doc doc-contents first">
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
<div class="doc doc-children">
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h2 id="Cryptotools.Numbers.primeNumber.are_coprime" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">are_coprime</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">p2</span><span class="p">)</span></code>
|
||
|
||
</h2>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function check if p1 and p2 are coprime</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>p1</code></b>
|
||
(<code><span title="list">list</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>list of prime numbers of the first number</p>
|
||
</div>
|
||
</li>
|
||
<li>
|
||
<b><code>p2</code></b>
|
||
(<code><span title="list">list</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>list of prime number of the second number</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return a boolean result</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="quote">
|
||
<summary>Source code in <code>Cryptotools/Numbers/primeNumber.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">153</span>
|
||
<span class="normal">154</span>
|
||
<span class="normal">155</span>
|
||
<span class="normal">156</span>
|
||
<span class="normal">157</span>
|
||
<span class="normal">158</span>
|
||
<span class="normal">159</span>
|
||
<span class="normal">160</span>
|
||
<span class="normal">161</span>
|
||
<span class="normal">162</span>
|
||
<span class="normal">163</span>
|
||
<span class="normal">164</span>
|
||
<span class="normal">165</span>
|
||
<span class="normal">166</span>
|
||
<span class="normal">167</span>
|
||
<span class="normal">168</span>
|
||
<span class="normal">169</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span> <span class="nf">are_coprime</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">p2</span><span class="p">):</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function check if p1 and p2 are coprime</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> p1 (list): list of prime numbers of the first number</span>
|
||
<span class="sd"> p2 (list): list of prime number of the second number</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return a boolean result</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">r</span> <span class="o">=</span> <span class="kc">True</span>
|
||
<span class="k">for</span> <span class="n">entry</span> <span class="ow">in</span> <span class="n">p1</span><span class="p">:</span>
|
||
<span class="k">if</span> <span class="n">entry</span> <span class="ow">in</span> <span class="n">p2</span><span class="p">:</span>
|
||
<span class="n">r</span> <span class="o">=</span> <span class="kc">False</span>
|
||
<span class="k">break</span>
|
||
<span class="k">return</span> <span class="n">r</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h2 id="Cryptotools.Numbers.primeNumber.getPrimeNumber" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">getPrimeNumber</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">safe</span><span class="o">=</span><span class="kc">True</span><span class="p">)</span></code>
|
||
|
||
</h2>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function generate a large prime number
|
||
based on "A method for Obtaining Digital Signatures
|
||
and Public-Key Cryptosystems"
|
||
Section B. How to Find Large Prime Numbers
|
||
https://dl.acm.org/doi/pdf/10.1145/359340.359342</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>n</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>The size of the prime number. Must be a multiple of 64</p>
|
||
</div>
|
||
</li>
|
||
<li>
|
||
<b><code>safe</code></b>
|
||
(<code><span title="Boolean">Boolean</span></code>, default:
|
||
<code>True</code>
|
||
)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>When generating the prime number, the function must find a safe prime number, based on the Germain primes (2p + 1 is also a prime number)</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return the prime number</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="quote">
|
||
<summary>Source code in <code>Cryptotools/Numbers/primeNumber.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">35</span>
|
||
<span class="normal">36</span>
|
||
<span class="normal">37</span>
|
||
<span class="normal">38</span>
|
||
<span class="normal">39</span>
|
||
<span class="normal">40</span>
|
||
<span class="normal">41</span>
|
||
<span class="normal">42</span>
|
||
<span class="normal">43</span>
|
||
<span class="normal">44</span>
|
||
<span class="normal">45</span>
|
||
<span class="normal">46</span>
|
||
<span class="normal">47</span>
|
||
<span class="normal">48</span>
|
||
<span class="normal">49</span>
|
||
<span class="normal">50</span>
|
||
<span class="normal">51</span>
|
||
<span class="normal">52</span>
|
||
<span class="normal">53</span>
|
||
<span class="normal">54</span>
|
||
<span class="normal">55</span>
|
||
<span class="normal">56</span>
|
||
<span class="normal">57</span>
|
||
<span class="normal">58</span>
|
||
<span class="normal">59</span>
|
||
<span class="normal">60</span>
|
||
<span class="normal">61</span>
|
||
<span class="normal">62</span>
|
||
<span class="normal">63</span>
|
||
<span class="normal">64</span>
|
||
<span class="normal">65</span>
|
||
<span class="normal">66</span>
|
||
<span class="normal">67</span>
|
||
<span class="normal">68</span>
|
||
<span class="normal">69</span>
|
||
<span class="normal">70</span>
|
||
<span class="normal">71</span>
|
||
<span class="normal">72</span>
|
||
<span class="normal">73</span>
|
||
<span class="normal">74</span>
|
||
<span class="normal">75</span>
|
||
<span class="normal">76</span>
|
||
<span class="normal">77</span>
|
||
<span class="normal">78</span>
|
||
<span class="normal">79</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span> <span class="nf">getPrimeNumber</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">safe</span><span class="o">=</span><span class="kc">True</span><span class="p">):</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function generate a large prime number</span>
|
||
<span class="sd"> based on "A method for Obtaining Digital Signatures</span>
|
||
<span class="sd"> and Public-Key Cryptosystems"</span>
|
||
<span class="sd"> Section B. How to Find Large Prime Numbers</span>
|
||
<span class="sd"> https://dl.acm.org/doi/pdf/10.1145/359340.359342</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> n (Integer): The size of the prime number. Must be a multiple of 64</span>
|
||
<span class="sd"> safe (Boolean): When generating the prime number, the function must find a safe prime number, based on the Germain primes (2p + 1 is also a prime number)</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return the prime number</span>
|
||
<span class="sd"> """</span>
|
||
<span class="k">if</span> <span class="n">n</span> <span class="o">%</span> <span class="mi">64</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">:</span>
|
||
<span class="nb">print</span><span class="p">(</span><span class="s2">"Must be multiple of 64"</span><span class="p">)</span>
|
||
<span class="k">return</span>
|
||
<span class="c1"># from sys import getsizeof</span>
|
||
<span class="n">upper</span> <span class="o">=</span> <span class="n">getrandbits</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>
|
||
<span class="n">lower</span> <span class="o">=</span> <span class="n">upper</span> <span class="o">>></span> <span class="mi">7</span>
|
||
<span class="n">r</span> <span class="o">=</span> <span class="n">randint</span><span class="p">(</span><span class="n">lower</span><span class="p">,</span> <span class="n">upper</span><span class="p">)</span>
|
||
|
||
<span class="k">while</span> <span class="n">r</span> <span class="o">%</span> <span class="mi">2</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
|
||
<span class="n">r</span> <span class="o">+=</span> <span class="mi">1</span>
|
||
|
||
<span class="c1"># Now, we are going to compute r as prime number</span>
|
||
<span class="n">i</span> <span class="o">=</span> <span class="mi">100</span>
|
||
<span class="k">while</span> <span class="mi">1</span><span class="p">:</span>
|
||
<span class="c1"># Check if it's a prime number</span>
|
||
<span class="k">if</span> <span class="n">_millerRabinTest</span><span class="p">(</span><span class="n">r</span><span class="p">):</span>
|
||
<span class="k">break</span>
|
||
|
||
<span class="c1"># TODO: it's dirty, need to change that</span>
|
||
<span class="c1"># i = int(log2(r))</span>
|
||
<span class="c1"># i *= randint(2, 50)</span>
|
||
|
||
<span class="n">r</span> <span class="o">+=</span> <span class="n">i</span>
|
||
<span class="c1"># print(f"{i} {r}")</span>
|
||
<span class="n">i</span> <span class="o">+=</span> <span class="mi">1</span>
|
||
|
||
|
||
<span class="c1"># print(_fermatLittleTheorem(r))</span>
|
||
<span class="c1"># print(getsizeof(r))</span>
|
||
<span class="k">return</span> <span class="n">r</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h2 id="Cryptotools.Numbers.primeNumber.getSmallPrimeNumber" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">getSmallPrimeNumber</span><span class="p">(</span><span class="n">n</span><span class="p">)</span></code>
|
||
|
||
</h2>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function is deprecated</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>n</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Get the small prime number until n</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><span title="int">int</span></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return the first prime number found</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="quote">
|
||
<summary>Source code in <code>Cryptotools/Numbers/primeNumber.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal"> 81</span>
|
||
<span class="normal"> 82</span>
|
||
<span class="normal"> 83</span>
|
||
<span class="normal"> 84</span>
|
||
<span class="normal"> 85</span>
|
||
<span class="normal"> 86</span>
|
||
<span class="normal"> 87</span>
|
||
<span class="normal"> 88</span>
|
||
<span class="normal"> 89</span>
|
||
<span class="normal"> 90</span>
|
||
<span class="normal"> 91</span>
|
||
<span class="normal"> 92</span>
|
||
<span class="normal"> 93</span>
|
||
<span class="normal"> 94</span>
|
||
<span class="normal"> 95</span>
|
||
<span class="normal"> 96</span>
|
||
<span class="normal"> 97</span>
|
||
<span class="normal"> 98</span>
|
||
<span class="normal"> 99</span>
|
||
<span class="normal">100</span>
|
||
<span class="normal">101</span>
|
||
<span class="normal">102</span>
|
||
<span class="normal">103</span>
|
||
<span class="normal">104</span>
|
||
<span class="normal">105</span>
|
||
<span class="normal">106</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span> <span class="nf">getSmallPrimeNumber</span><span class="p">(</span><span class="n">n</span><span class="p">)</span> <span class="o">-></span> <span class="nb">int</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function is deprecated</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> n (Integer): Get the small prime number until n</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return the first prime number found</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">is_prime</span> <span class="o">=</span> <span class="kc">True</span>
|
||
|
||
<span class="k">while</span> <span class="kc">True</span><span class="p">:</span>
|
||
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
|
||
<span class="c1"># If n is divisible by i, it's not a prime, we break the loop</span>
|
||
<span class="k">if</span> <span class="n">n</span> <span class="o">%</span> <span class="n">i</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
|
||
<span class="n">is_prime</span> <span class="o">=</span> <span class="kc">False</span>
|
||
<span class="k">break</span>
|
||
|
||
<span class="k">if</span> <span class="n">is_prime</span><span class="p">:</span>
|
||
<span class="k">break</span>
|
||
<span class="n">is_prime</span> <span class="o">=</span> <span class="kc">True</span>
|
||
<span class="n">n</span> <span class="o">=</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span>
|
||
|
||
<span class="n">p</span> <span class="o">=</span> <span class="n">n</span>
|
||
<span class="k">return</span> <span class="n">p</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h2 id="Cryptotools.Numbers.primeNumber.get_n_prime_numbers" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">get_n_prime_numbers</span><span class="p">(</span><span class="n">n</span><span class="p">)</span></code>
|
||
|
||
</h2>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function return a list of n prime numbers</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>n</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>the range, must be an integer</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><span title="list">list</span></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return a list of n prime numbers</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="quote">
|
||
<summary>Source code in <code>Cryptotools/Numbers/primeNumber.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">124</span>
|
||
<span class="normal">125</span>
|
||
<span class="normal">126</span>
|
||
<span class="normal">127</span>
|
||
<span class="normal">128</span>
|
||
<span class="normal">129</span>
|
||
<span class="normal">130</span>
|
||
<span class="normal">131</span>
|
||
<span class="normal">132</span>
|
||
<span class="normal">133</span>
|
||
<span class="normal">134</span>
|
||
<span class="normal">135</span>
|
||
<span class="normal">136</span>
|
||
<span class="normal">137</span>
|
||
<span class="normal">138</span>
|
||
<span class="normal">139</span>
|
||
<span class="normal">140</span>
|
||
<span class="normal">141</span>
|
||
<span class="normal">142</span>
|
||
<span class="normal">143</span>
|
||
<span class="normal">144</span>
|
||
<span class="normal">145</span>
|
||
<span class="normal">146</span>
|
||
<span class="normal">147</span>
|
||
<span class="normal">148</span>
|
||
<span class="normal">149</span>
|
||
<span class="normal">150</span>
|
||
<span class="normal">151</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span> <span class="nf">get_n_prime_numbers</span><span class="p">(</span><span class="n">n</span><span class="p">)</span> <span class="o">-></span> <span class="nb">list</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function return a list of n prime numbers</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> n (Integer): the range, must be an integer</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return a list of n prime numbers</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">l</span> <span class="o">=</span> <span class="nb">list</span><span class="p">()</span>
|
||
|
||
<span class="n">count</span> <span class="o">=</span> <span class="mi">2</span>
|
||
<span class="n">index</span> <span class="o">=</span> <span class="mi">0</span>
|
||
<span class="k">while</span> <span class="n">index</span> <span class="o"><</span> <span class="n">n</span><span class="p">:</span>
|
||
<span class="n">is_prime</span> <span class="o">=</span> <span class="kc">True</span>
|
||
<span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">count</span><span class="p">):</span>
|
||
<span class="k">if</span> <span class="n">count</span> <span class="o">%</span> <span class="n">x</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
|
||
<span class="n">is_prime</span> <span class="o">=</span> <span class="kc">False</span>
|
||
<span class="k">break</span>
|
||
|
||
<span class="k">if</span> <span class="n">is_prime</span><span class="p">:</span>
|
||
<span class="n">l</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">count</span><span class="p">)</span>
|
||
<span class="n">index</span> <span class="o">+=</span> <span class="mi">1</span>
|
||
|
||
<span class="n">count</span> <span class="o">+=</span> <span class="mi">1</span>
|
||
|
||
<span class="k">return</span> <span class="n">l</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h2 id="Cryptotools.Numbers.primeNumber.get_prime_numbers" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">get_prime_numbers</span><span class="p">(</span><span class="n">n</span><span class="p">)</span></code>
|
||
|
||
</h2>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function get all prime number of the n</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>n</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>find all prime number until n is achieves</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><span title="list">list</span></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return a list of prime numbers</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="quote">
|
||
<summary>Source code in <code>Cryptotools/Numbers/primeNumber.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">108</span>
|
||
<span class="normal">109</span>
|
||
<span class="normal">110</span>
|
||
<span class="normal">111</span>
|
||
<span class="normal">112</span>
|
||
<span class="normal">113</span>
|
||
<span class="normal">114</span>
|
||
<span class="normal">115</span>
|
||
<span class="normal">116</span>
|
||
<span class="normal">117</span>
|
||
<span class="normal">118</span>
|
||
<span class="normal">119</span>
|
||
<span class="normal">120</span>
|
||
<span class="normal">121</span>
|
||
<span class="normal">122</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span> <span class="nf">get_prime_numbers</span><span class="p">(</span><span class="n">n</span><span class="p">)</span> <span class="o">-></span> <span class="nb">list</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function get all prime number of the n</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> n (Integer): find all prime number until n is achieves</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return a list of prime numbers</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">l</span> <span class="o">=</span> <span class="nb">list</span><span class="p">()</span>
|
||
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
|
||
<span class="k">if</span> <span class="n">n</span> <span class="o">%</span> <span class="n">i</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
|
||
<span class="n">l</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
|
||
<span class="k">return</span> <span class="n">l</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h2 id="Cryptotools.Numbers.primeNumber.isPrimeNumber" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">isPrimeNumber</span><span class="p">(</span><span class="n">p</span><span class="p">)</span></code>
|
||
|
||
</h2>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>Check if the number p is a prime number or not. The function iterate until p is achieve.</p>
|
||
<p>This function is not the efficient way to determine if p is prime or a composite.</p>
|
||
<p>To identify if p is prime or not, the function check the result of the Euclidean Division has a remainder. If yes, it's means it's not a prime number</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>p</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>number if possible prime or not</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return a boolean if the number p is a prime number or not. True if yes</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="quote">
|
||
<summary>Source code in <code>Cryptotools/Numbers/primeNumber.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal"> 8</span>
|
||
<span class="normal"> 9</span>
|
||
<span class="normal">10</span>
|
||
<span class="normal">11</span>
|
||
<span class="normal">12</span>
|
||
<span class="normal">13</span>
|
||
<span class="normal">14</span>
|
||
<span class="normal">15</span>
|
||
<span class="normal">16</span>
|
||
<span class="normal">17</span>
|
||
<span class="normal">18</span>
|
||
<span class="normal">19</span>
|
||
<span class="normal">20</span>
|
||
<span class="normal">21</span>
|
||
<span class="normal">22</span>
|
||
<span class="normal">23</span>
|
||
<span class="normal">24</span>
|
||
<span class="normal">25</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span> <span class="nf">isPrimeNumber</span><span class="p">(</span><span class="n">p</span><span class="p">):</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> Check if the number p is a prime number or not. The function iterate until p is achieve.</span>
|
||
|
||
<span class="sd"> This function is not the efficient way to determine if p is prime or a composite.</span>
|
||
|
||
<span class="sd"> To identify if p is prime or not, the function check the result of the Euclidean Division has a remainder. If yes, it's means it's not a prime number</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> p (Integer): number if possible prime or not</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return a boolean if the number p is a prime number or not. True if yes</span>
|
||
<span class="sd"> """</span>
|
||
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">p</span><span class="p">):</span>
|
||
<span class="k">if</span> <span class="n">p</span> <span class="o">%</span> <span class="n">i</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="kc">False</span>
|
||
<span class="k">return</span> <span class="kc">True</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h2 id="Cryptotools.Numbers.primeNumber.isSafePrime" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">isSafePrime</span><span class="p">(</span><span class="n">n</span><span class="p">)</span></code>
|
||
|
||
</h2>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function has not been implemented yet, but check if the number n is a safe prime number. This function will test different properties of the possible prime number n</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>n</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>the prime number to check</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><span title="bool">bool</span></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return a Boolean if the prime number n is safe or not. True if yes, otherwise it's False</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="quote">
|
||
<summary>Source code in <code>Cryptotools/Numbers/primeNumber.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">272</span>
|
||
<span class="normal">273</span>
|
||
<span class="normal">274</span>
|
||
<span class="normal">275</span>
|
||
<span class="normal">276</span>
|
||
<span class="normal">277</span>
|
||
<span class="normal">278</span>
|
||
<span class="normal">279</span>
|
||
<span class="normal">280</span>
|
||
<span class="normal">281</span>
|
||
<span class="normal">282</span>
|
||
<span class="normal">283</span>
|
||
<span class="normal">284</span>
|
||
<span class="normal">285</span>
|
||
<span class="normal">286</span>
|
||
<span class="normal">287</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span> <span class="nf">isSafePrime</span><span class="p">(</span><span class="n">n</span><span class="p">)</span> <span class="o">-></span> <span class="nb">bool</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function has not been implemented yet, but check if the number n is a safe prime number. This function will test different properties of the possible prime number n</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> n (Integer): the prime number to check</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return a Boolean if the prime number n is safe or not. True if yes, otherwise it's False</span>
|
||
<span class="sd"> """</span>
|
||
<span class="k">if</span> <span class="n">n</span><span class="o">.</span><span class="n">bit_length</span><span class="p">()</span> <span class="o">>=</span> <span class="mi">256</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="kc">True</span>
|
||
|
||
<span class="c1"># Do Sophie Germain's test</span>
|
||
|
||
<span class="k">return</span> <span class="kc">False</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h2 id="Cryptotools.Numbers.primeNumber.sieveOfEratosthenes" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">sieveOfEratosthenes</span><span class="p">(</span><span class="n">n</span><span class="p">)</span></code>
|
||
|
||
</h2>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function build a list of prime number based on the Sieve of Erastosthenes</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>n</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Interate until n is achives</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><span title="list">list</span></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return a list of all prime numbers to n</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="quote">
|
||
<summary>Source code in <code>Cryptotools/Numbers/primeNumber.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">171</span>
|
||
<span class="normal">172</span>
|
||
<span class="normal">173</span>
|
||
<span class="normal">174</span>
|
||
<span class="normal">175</span>
|
||
<span class="normal">176</span>
|
||
<span class="normal">177</span>
|
||
<span class="normal">178</span>
|
||
<span class="normal">179</span>
|
||
<span class="normal">180</span>
|
||
<span class="normal">181</span>
|
||
<span class="normal">182</span>
|
||
<span class="normal">183</span>
|
||
<span class="normal">184</span>
|
||
<span class="normal">185</span>
|
||
<span class="normal">186</span>
|
||
<span class="normal">187</span>
|
||
<span class="normal">188</span>
|
||
<span class="normal">189</span>
|
||
<span class="normal">190</span>
|
||
<span class="normal">191</span>
|
||
<span class="normal">192</span>
|
||
<span class="normal">193</span>
|
||
<span class="normal">194</span>
|
||
<span class="normal">195</span>
|
||
<span class="normal">196</span>
|
||
<span class="normal">197</span>
|
||
<span class="normal">198</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span> <span class="nf">sieveOfEratosthenes</span><span class="p">(</span><span class="n">n</span><span class="p">)</span> <span class="o">-></span> <span class="nb">list</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function build a list of prime number based on the Sieve of Erastosthenes</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> n (Integer): Interate until n is achives</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return a list of all prime numbers to n</span>
|
||
<span class="sd"> """</span>
|
||
<span class="k">if</span> <span class="n">n</span> <span class="o"><</span> <span class="mi">1</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="nb">list</span><span class="p">()</span>
|
||
|
||
<span class="n">eratost</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">()</span>
|
||
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
|
||
<span class="n">eratost</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="kc">True</span>
|
||
|
||
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
|
||
<span class="k">if</span> <span class="n">eratost</span><span class="p">[</span><span class="n">i</span><span class="p">]:</span>
|
||
<span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">i</span><span class="o">*</span><span class="n">i</span><span class="p">,</span> <span class="n">n</span><span class="p">,</span> <span class="n">i</span><span class="p">):</span>
|
||
<span class="n">eratost</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="kc">False</span>
|
||
|
||
<span class="n">sieve</span> <span class="o">=</span> <span class="nb">list</span><span class="p">()</span>
|
||
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
|
||
<span class="k">if</span> <span class="n">eratost</span><span class="p">[</span><span class="n">i</span><span class="p">]:</span>
|
||
<span class="n">sieve</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
|
||
|
||
<span class="k">return</span> <span class="n">sieve</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h2 id="Cryptotools.Numbers.primeNumber.sophieGermainPrime" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">sophieGermainPrime</span><span class="p">(</span><span class="n">p</span><span class="p">)</span></code>
|
||
|
||
</h2>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>Check if the number p is a safe prime number: 2p + 1 is also a prime</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>p</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Possible prime number</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><span title="bool">bool</span></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return True if p is a safe prime number, otherwise it's False</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="quote">
|
||
<summary>Source code in <code>Cryptotools/Numbers/primeNumber.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">259</span>
|
||
<span class="normal">260</span>
|
||
<span class="normal">261</span>
|
||
<span class="normal">262</span>
|
||
<span class="normal">263</span>
|
||
<span class="normal">264</span>
|
||
<span class="normal">265</span>
|
||
<span class="normal">266</span>
|
||
<span class="normal">267</span>
|
||
<span class="normal">268</span>
|
||
<span class="normal">269</span>
|
||
<span class="normal">270</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span> <span class="nf">sophieGermainPrime</span><span class="p">(</span><span class="n">p</span><span class="p">)</span> <span class="o">-></span> <span class="nb">bool</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> Check if the number p is a safe prime number: 2p + 1 is also a prime</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> p (Integer): Possible prime number</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return True if p is a safe prime number, otherwise it's False</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">pp</span> <span class="o">=</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">p</span> <span class="o">+</span> <span class="mi">1</span>
|
||
<span class="k">return</span> <span class="n">_millerRabinTest</span><span class="p">(</span><span class="n">pp</span><span class="p">)</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
|
||
|
||
</div>
|
||
|
||
</div>
|
||
|
||
</div><h2 id="fibonacci-sequence">Fibonacci sequence</h2>
|
||
|
||
|
||
<div class="doc doc-object doc-module">
|
||
|
||
|
||
|
||
<a id="Cryptotools.Numbers.numbers"></a>
|
||
<div class="doc doc-contents first">
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
<div class="doc doc-children">
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h2 id="Cryptotools.Numbers.numbers.fibonacci" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">fibonacci</span><span class="p">(</span><span class="n">n</span><span class="p">)</span></code>
|
||
|
||
</h2>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function generate the list of Fibonacci</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>n</code></b>
|
||
(<code><span title="integer">integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>it's maximum value of Fibonacci sequence</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><span title="list">list</span></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return a list of n element in the Fibonacci sequence</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="quote">
|
||
<summary>Source code in <code>Cryptotools/Numbers/numbers.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal"> 4</span>
|
||
<span class="normal"> 5</span>
|
||
<span class="normal"> 6</span>
|
||
<span class="normal"> 7</span>
|
||
<span class="normal"> 8</span>
|
||
<span class="normal"> 9</span>
|
||
<span class="normal">10</span>
|
||
<span class="normal">11</span>
|
||
<span class="normal">12</span>
|
||
<span class="normal">13</span>
|
||
<span class="normal">14</span>
|
||
<span class="normal">15</span>
|
||
<span class="normal">16</span>
|
||
<span class="normal">17</span>
|
||
<span class="normal">18</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span> <span class="nf">fibonacci</span><span class="p">(</span><span class="n">n</span><span class="p">)</span> <span class="o">-></span> <span class="nb">list</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function generate the list of Fibonacci</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> n (integer): it's maximum value of Fibonacci sequence</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return a list of n element in the Fibonacci sequence</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">fibo</span> <span class="o">=</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">]</span>
|
||
<span class="n">fibo</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">fibo</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">fibo</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
|
||
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
|
||
<span class="n">fibo</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">fibo</span><span class="p">[</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">fibo</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
|
||
<span class="k">return</span> <span class="n">fibo</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
|
||
|
||
</div>
|
||
|
||
</div>
|
||
|
||
</div>
|
||
|
||
</div>
|
||
</div><footer>
|
||
<div class="rst-footer-buttons" role="navigation" aria-label="Footer Navigation">
|
||
<a href="../installation/" class="btn btn-neutral float-left" title="Installation"><span class="icon icon-circle-arrow-left"></span> Previous</a>
|
||
<a href="../group-theory/" class="btn btn-neutral float-right" title="Group theory">Next <span class="icon icon-circle-arrow-right"></span></a>
|
||
</div>
|
||
|
||
<hr/>
|
||
|
||
<div role="contentinfo">
|
||
<!-- Copyright etc -->
|
||
</div>
|
||
|
||
Built with <a href="https://www.mkdocs.org/">MkDocs</a> using a <a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
|
||
</footer>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
</section>
|
||
|
||
</div>
|
||
|
||
<div class="rst-versions" role="note" aria-label="Versions">
|
||
<span class="rst-current-version" data-toggle="rst-current-version">
|
||
|
||
|
||
<span><a href="../installation/" style="color: #fcfcfc">« Previous</a></span>
|
||
|
||
|
||
<span><a href="../group-theory/" style="color: #fcfcfc">Next »</a></span>
|
||
|
||
</span>
|
||
</div>
|
||
<script src="../js/jquery-3.6.0.min.js"></script>
|
||
<script>var base_url = "..";</script>
|
||
<script src="../js/theme_extra.js"></script>
|
||
<script src="../js/theme.js"></script>
|
||
<script>
|
||
jQuery(function () {
|
||
SphinxRtdTheme.Navigation.enable(true);
|
||
});
|
||
</script>
|
||
|
||
</body>
|
||
</html>
|