forked from alpertron/calculators
-
Notifications
You must be signed in to change notification settings - Fork 0
/
dilog.htm
185 lines (185 loc) · 9.23 KB
/
dilog.htm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta name="Author" content="Dario Alejandro Alpern" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="description" content="Javascript application that finds discrete logarithms. Written by Dario Alpern." />
<meta name="theme-color" content="#db5945">
<link rel="alternate" hreflang="es" href="LOGDI.HTM" />
<link rel="prefetch" href="dilogW0026.js" />
<link rel="manifest" href="dilog.webmanifest">
<title>Discrete logarithm calculator</title>
<style type="text/css" media="print">
#smallheader {display:none;}
</style>
<style type="text/css" media="screen">
#smallheader {background-color:#000080; width:100%; margin:0px; text-align:center;}
#smallheader ul { padding:0; margin:0 auto; list-style:none; display:inline-block;}
#smallheader li { float:left; position:relative; display:block; margin-top:0px; margin-bottom:0px; margin-left:5px; margin-right:5px; background-color:#000080; color:#FFFFFF; font-family:"Arial", sans-serif; cursor: pointer; text-align:left;}
#smallheader li:hover {background-color:#004000; color:#FFFFFF;}
#smallheader li ul { display:none; position:absolute; }
#smallheader li:hover ul.alignleft{ display:block; height:auto;}
#smallheader li:hover ul.alignright{ display:block; height:auto; right:0px; background-color:#004000;}
#smallheader li ul li{ clear:both; white-space: nowrap; border:0px; background-color:#004000; width:100%; padding-top:1em; padding-bottom:0.5em}
#smallheader a:link{color:#FFFFFF; text-decoration: none;}
#smallheader a:visited{color:#FFFFFF; text-decoration: none;}
#smallheader a:hover{background-color:#004000; color:#FFFFFF; text-decoration: none;}
#smallheader a:active{background-color:#004000; color:#FFFFFF; text-decoration: none;}
#smallheader li ul li a:link{background-color:#004000; color:#FFFFFF; display:block; width:100%;}
#smallheader li ul li a:visited{background-color:#004000;color:#FFFFFF; display:block; width:100%;}
#smallheader li ul li a:hover{background-color:#FFFFFF; color:#004000; display:block; width:100%;}
#smallheader li ul li a:active{background-color:#FFFFFF; color:#004000; display:block; width:100%;}
@media (max-width: 400px) { #smallheader { font-size:0.7em;} }
@media (min-width: 400px) { #smallheader { font-size:1em;} }
</style>
<style>
body {font-family: arial; margin: 0; padding: 0;}
h1 {text-align:center;}
.lf {padding:0.2em; clear:both;}
.pad {padding:10px;}
#applet {margin-left: auto;margin-right: auto; border: 0px none;width:90%;text-align:center;background-color:#c0c0c0;padding:10px;}
@media (min-width: 400px) { .input{width: calc(100% - 7em);float:right;padding:3px;margin:0px;}}
@media (max-width: 400px) { .input{width:100%;padding:3px;margin:0px;}}
</style>
</head>
<body>
<nav id="smallheader">
<div style="float:right;"><a href="index.htm" hreflang="es" title="Sitio de Darío Alpern en español">ESP</a></div>
<ul>
<li>
Electronics
<ul class="alignleft">
<li>
<a href="INTEL.HTM" hreflang="es" title="All Intel microprocessors from the 4004 up to Pentium (Spanish only)">Intel Microprocessors</a>
</li>
</ul>
</li>
<li>
Mathematics
<ul class="alignleft">
<li>
<a href="CALTORS.HTM" title="Java and Javascript programs implementing calculators">Calculators</a>
</li>
<li>
<a href="NUMBERT.HTM" title="Articles and programs about number theory">Number Theory</a>
</li>
<li>
<a href="PROBLEMS.HTM" title="Interesting math problems">Problems</a>
</li>
</ul>
</li>
<li>
Programs
<ul class="alignright">
<li>
<a href="ASSEM386.HTM" title="Programs written in 80386 Assembler">Assembler 80386</a>
</li>
<li>
<a href="JAVAPROG.HTM" title="Programs written in Java">Java</a>
</li>
<li>
<a href="GAMES.HTM" title="Computer games">Games</a>
</li>
</ul>
</li>
<li class="alignright">
Contact
<ul class="alignright">
<li>
<a href="EPERS.HTM" title="Personal information">Personal</a>
</li>
<li>
<a href="FORM.HTM" title="Form to send comments">Comments</a>
</li>
<li>
<a href="EGBOOK.HTM" title="Old and new guestbook">Guestbook</a>
</li>
<li>
<a href="DONATION.HTM" title="Donations to the author of this Web site">Donations</a>
</li>
</ul>
</li>
</ul>
<br style="clear:both;"/>
</nav>
<article>
<h1>Discrete logarithm calculator</h1>
<script async="async" type="application/javascript" src="dilog0026.js"></script>
<div class="pad">
<div id="a" itemscope="itemscope" itemtype="http://data-vocabulary.org/Breadcrumb" itemref="b" style="display:inline;">
<a href="ENGLISH.HTM" itemprop="url">
<span itemprop="title">Alpertron</span>
</a> ›
</div>
<div id="b" itemscope="itemscope" itemtype="http://data-vocabulary.org/Breadcrumb" itemprop="child" itemref="c" style="display:inline;">
<a href="JAVAPROG.HTM" itemprop="url">
<span itemprop="title">Programs</span>
</a> ›
</div>
<div id="c" itemscope="itemscope" itemtype="http://data-vocabulary.org/Breadcrumb" itemprop="child" style="display:inline;">
<a href="POLFACT.HTM" itemprop="url">
<span itemprop="title">Discrete logarithm calculator</span>
</a>
</div>
</div>
<form id="applet">
<label for="base">Base</label><input type="text" id="base" value="" class="input"/>
<div class="lf"></div>
<label for="pow">Power</label><input type="text" id="pow" value="" class="input"/>
<div class="lf"></div>
<label for="mod">Modulus</label><input type="text" id="mod" value="" class="input"/>
<div class="lf"></div>
<input type="button" id="dlog" value="Discrete logarithm" />
<input type="button" id="stop" value="Stop" />
<input type="button" id="helpbtn" value="Help" />
<div class="lf"></div>
<label for="digits">Digits per group</label> <input type="number" id="digits" value="6"/>
<input type="hidden" id="app" value="0"/>
</form>
<div id="help" aria-live="polite" class="pad">
<p>The discrete logarithm problem is to find the exponent in the expression <em>Base<sup>Exponent</sup> = Power (mod Modulus)</em>.
<p>This applet works for both prime and composite moduli. The only restriction is that the base and the modulus, and the power and the modulus must be relatively prime.
<p>In this version of the discrete logarithm calculator only the Pohlig-Hellman algorithm is implemented, so the execution time is proportional to the square root of the largest prime factor of the modulus minus 1.
The applet works in a reasonable amount of time if this factor is less than <span role="math" aria-label="10 raised to the power of 17">10<sup>17</sup></span>.
<p>I will add the index-calculus algorithm soon. This algorithm has subexponential running time.
<h2>Expressions</h2>
<p>You can also enter expressions that use the following operators and parentheses:
<ul>
<li><strong>+</strong> for addition</li>
<li><strong>-</strong> for subtraction</li>
<li><strong>*</strong> for multiplication</li>
<li><strong>/</strong> for division</li>
<li><strong>%</strong> for remainder</li>
<li><strong>^</strong> or <strong>**</strong> for exponentiation</li>
<li><strong>n!</strong>: factorial</li>
<li><strong>p#</strong>: primorial (product of all primes less or equal than <em>p</em>).</li>
<li><strong>B(n)</strong>: Previous probable prime before <em>n</em></li>
<li><strong>F(n)</strong>: Fibonacci number F<SUB>n</SUB></li>
<li><strong>L(n)</strong>: Lucas number L<SUB>n</SUB> = F<SUB>n-1</SUB> + F<SUB>n+1</SUB></li>
<li><strong>N(n)</strong>: Next probable prime after <em>n</em></li>
<li><strong>P(n)</strong>: Unrestricted Partition Number (number of decompositions of <em>n</em> into sums of integers without regard to order).</li>
<li><strong>Gcd(m,n)</strong>: Greatest common divisor of these two integers.</li>
<li><strong>Modinv(m,n)</strong>: inverse of <var>m</var> modulo <var>n</var>, only valid when gcd(m,n)=1.</li>
<li><strong>Modpow(m,n,r)</strong>: finds <var>m</var><sup><var>n</var></sup> modulo <var>r</var>.</li>
</ul>
<p>You can use the prefix <em>0x</em> for hexadecimal numbers, for example 0x38 is equal to 56.</p>
<p>The exponentiation symbol is not present in some mobile devices, so two asterisks ** can by typed as the exponentiation operator.</p>
<p>Example: Find the number <var>n</var> such that <span role="math" aria-label="7 raised to the power of n is congruent to 23 modulo 43241">7<sup>n</sup> ≡ 23 (mod 43241)</span>.</p>
<p>Type 7 in the Base input box, 23 in the Power input box and 43241 in the Mod input box. Then press the button named "Discrete logarithm".</p>
<p>The result is 3360 + 3930 k. As a check you can compute <span role="math" aria-label="7 raised to the power of 3360 is congruent to 23 modulo 43241">7<sup>3360</sup> ≡ 23 (mod 43241)</span> and <span role="math" aria-label="7 raised to the power of 3930 is congruent to 1 modulo 43241">7<sup>3930</sup> ≡ 1 (mod 43241)</span>.</p>
<h2>Source code</h2>
<p>
You can download the source of the current program and the old sum polynomial factorization applet from <a href="https://github.com/alpertron/calculators">GitHub</a>. Notice that the source code is in C language and you need the <a href="https://kripken.github.io/emscripten-site/docs/getting_started/downloads.html">Emscripten</a> environment in order to generate Javascript.
</p>
<p>Written by Dario Alpern. Last updated 9 December 2017.</p>
</div>
<div id="result" aria-live="polite" class="pad"></div>
<div>
<p class="pad">
If you find any error or you have a comment, please fill in the <a href="FORM.HTM?Discrete+logarithm+calculator+feedback">form</a>.
</p>
</div>
</article>
</body>
</html>