forked from alpertron/calculators
-
Notifications
You must be signed in to change notification settings - Fork 0
/
GAUSSIAN.HTM
251 lines (249 loc) · 15.2 KB
/
GAUSSIAN.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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
<!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 factors Gaussian integers of the form (a+bi). Written by Dario Alpern." />
<meta name="theme-color" content="#db5945">
<link rel="alternate" hreflang="es" href="GAUSIANO.HTM" />
<link rel="prefetch" href="gaussianW0026.js" />
<link rel="manifest" href="gaussian.webmanifest">
<title>Gaussian integer factorization calculator</title>
<style >
@media print {#smallheader {display:none;}}
@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%;}
.atright {float:right;}
.newline {clear:both;}
}
@media screen and (max-width: 400px) { #smallheader { font-size:0.7em; } }
@media screen and (min-width: 400px) { #smallheader { font-size:1em; } }
.modal-header {padding: 2px 10px; background-color: #5cb85c; color: white;}
.modal-body {padding: 2px 10px;}
.modal-content {
position: relative;
background-color: #fefefe;
margin: auto;
padding: 0;
border: 1px solid #888;
width: 80%;
box-shadow: 0 4px 8px 0 rgba(0,0,0,0.2),0 6px 20px 0 rgba(0,0,0,0.19);
-webkit-animation-name: animatetop;
-webkit-animation-duration: 0.4s;
animation-name: animatetop;
animation-duration: 0.4s
}
.modal {
display: none;
position: fixed;
z-index: 1;
padding-top: 100px;
left: 0;
top: 0;
width: 100%;
height: 100%;
overflow: auto;
background-color: rgb(0,0,0);
background-color: rgba(0,0,0,0.4);
}
body {font-family: arial;margin: 0; padding: 0;}
h1 {text-align:center;}
.lf {padding:0.2em; clear:both;}
.blue {color: #0000FF;}
.inline {display:inline;}
.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% - 6em);float:right;padding:3px;margin:0px;}}
@media (max-width: 400px) { .input{width:100%;padding:3px;margin:0px;}}
#help,#result,#status,#footer {margin: 3px; padding: 3px;}
#more,#stop {display:none}
</style>
</head>
<body>
<nav id="smallheader">
<div class="atright"><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 class="newline"/>
</nav>
<article>
<h1>Gaussian integer factorization calculator</h1>
<script async="async" src="gaussian0026.js"></script>
<div class="pad">
<div id="a" itemscope="itemscope" itemtype="http://data-vocabulary.org/Breadcrumb" itemref="b" class="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" class="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" class="inline">
<a href="GAUSSIAN.HTM" itemprop="url">
<span itemprop="title">Gaussian integer factorization calculator</span>
</a>
</div>
</div>
<form id="applet">
<label for="value">Value</label><input type="text" id="value" value="" class="input"/>
<div class="lf"></div>
<input type="button" id="more" value="More" />
<input type="button" id="eval" value="Only evaluate" />
<input type="button" id="factor" value="Factor" />
<input type="button" id="stop" value="Stop" />
<input type="button" id="helpbtn" value="Help" />
<input type="button" id="config" value="Config" />
<div class="lf"></div>
<input type="hidden" id="app" value="0"/>
</form>
<div id="help" aria-live="polite">
<p>The Gaussian integers are complex numbers of the form <var>a</var> + <var>bi</var>, where both <var>a</var> and <var>b</var> are integer numbers and <var>i</var> is the square root of -1.</p>
<p>This applet is able to factor a Gaussian integer as a product of Gaussian primes. This decomposition is unique, if we do not consider the order of the factors.</p>
<h2>Factoring Gaussian integers</h2>
<p>An important concept needed for Gaussian integer factorization is the norm. This is defined as: <span role="math" aria-label="norm of a plus b times i equals a squared plus b squared">N(<var>a</var>+<var>b</var><var>i</var>) = <var>a</var><sup>2</sup> + <var>b</var><sup>2</sup></span>.
<p>The product of the norm of two Gaussian integers is equal to the norm of the products of these numbers as can be easily seen as follows:</p>
<p>N(<var>a</var>+<var>b</var><var>i</var>) N(<var>c</var>+<var>d</var><var>i</var>) =
(<var>a</var><sup>2</sup> + <var>b</var><sup>2</sup>) (<var>c</var><sup>2</sup> + <var>d</var><sup>2</sup>) =
(<var>a</var><var>c</var>)<sup>2</sup> + (<var>b</var><var>d</var>)<sup>2</sup> + (<var>a</var><var>d</var>)<sup>2</sup> + (<var>b</var><var>c</var>)<sup>2</sup> =
(<var>a</var><var>c</var>)<sup>2</sup> - 2<var>a</var><var>b</var><var>c</var><var>d</var> + (<var>b</var><var>d</var>)<sup>2</sup> + (<var>a</var><var>d</var>)<sup>2</sup> + 2<var>a</var><var>b</var><var>c</var><var>d</var> + (<var>b</var><var>c</var>)<sup>2</sup> =
(<var>a</var><var>c</var>-<var>b</var><var>d</var>)<sup>2</sup> + (<var>a</var><var>d</var>+<var>b</var><var>c</var>)<sup>2</sup> =
N((<var>a</var><var>c</var>-<var>b</var><var>d</var>)+(<var>a</var><var>d</var>+<var>b</var><var>c</var>)<var>i</var>) =
N(<var>a</var>(<var>c</var>+<var>d</var><var>i</var>) + <var>b</var>(-<var>d</var>+<var>c</var><var>i</var>)) =
N(<var>a</var>(<var>c</var>+<var>d</var><var>i</var>) + <var>b</var><var>i</var>(<var>c</var>+<var>d</var><var>i</var>)) =
N((<var>a</var>+<var>b</var><var>i</var>) (<var>c</var>+<var>d</var><var>i</var>))</p>
<p>In the next to last expression we used the fact that <var>i</var><sup>2</sup> = -1.</p>
<p>This means that the first step when trying to factor a Gaussian integer is to factor its norm into integer primes, so we get the norm of the factors of the original number.</p>
<p>The second step is to obtain the factors from the norm of the factor.</p>
<p>There are three cases:</p>
<ol>
<li>The prime factor <var>p</var> of the norm is 2: This means that the factor of the Gaussian integer is 1+i or 1-i.</li>
<li>The prime factor <var>p</var> of the norm is multiple of 4 plus 3: this value cannot be expressed as a sum of two squares, so <var>p</var> is not a norm, but <var>p</var><sup>2</sup> is.
Since <var>p</var><sup>2</sup> = <var>p</var><sup>2</sup> + 0<sup>2</sup>, and there is no prime norm that divides <var>p</var><sup>2</sup>, the number <var>p</var> + 0<var>i</var> is a Gaussian prime, and the repeated factor <var>p</var> must be discarded.
<li>The prime factor <var>p</var> of the norm is multiple of 4 plus 1: this number can be expressed as a sum of two squares, by using the methods explained in the <a href="https://www.alpertron.com.ar/4SQUARES.HTM">sum of squares</a> page.
If <var>p</var> = <var>m</var><sup>2</sup> + <var>n</var><sup>2</sup>, then you can check whether <var>m</var> + <var>n</var><var>i</var> or <var>m</var> − <var>n</var><var>i</var> are divisors of the original Gaussian number.</li>
</ol>
<p>Why does a number which is multiple of 4 plus 3 cannot be expressed as a sum of two squares? This is because the square of an even number is multiple of 4, and the square of an odd number is multiple of 4 plus 1. So we get:</p>
<ul>
<li>even<sup>2</sup> + even<sup>2</sup> = multiple of 4</li>
<li>even<sup>2</sup> + odd<sup>2</sup> = multiple of 4 plus 1</li>
<li>odd<sup>2</sup> + even<sup>2</sup> = multiple of 4 plus 1</li>
<li>odd<sup>2</sup> + odd<sup>2</sup> = multiple of 4 plus 2</li>
</ul>
<p>So under no circumstances a sum of two squares can be multiple of 4 plus 3.</p>
<p>Of course the first step is a lot more difficult than the second step. This is because we do not know efficient integer factorization for huge numbers.</p>
<p>Example: factor the Gaussian integer 440 − 55i</p>
<p>The norm is 440<sup>2</sup> + 55<sup>2</sup> = 196625 = 5 × 5 × 5 × 11 × 11 × 13</p>
<p>Both 5 and 13 are multiples of 4 plus 1 while 11 is a multiple of 4 plus 3. We can use the fact the 5 = 2<sup>2</sup> + 1<sup>2</sup> and 13 = 3<sup>2</sup> + 2<sup>2</sup></p>
<p>Since 11 is a Gaussian prime, we can divide the original number by 11 and get 44 − 5i.</p>
<p>For the three factors of the norm equal to 5, we have to divide the result of the previous step 44 − 5i by 2−i or 2+i. So we get: 44 − 5i = (2+i)<sup>2</sup> × (2-i) × (3 − 2i)</p>
<p>For the factor 13 we have to divide the result of the previous step 3 − 2i by 3 + 2i or 3 − 2i. Of course only 3 − 2i divides 3 − 2i.</p>
<p>The complete factorization is: 440 − 55i = 11 × (2 + i)<sup>2</sup> × (2 − i) × (3 − 2i).</p>
<h2>Expressions</h2>
<p>In order to enter the imaginary part of a Gaussian integer you can use the symbol <var>i</var>, as in the next example: 3+4i.</p>
<p>You can also enter expressions that use the following operators, functions and parentheses:</p>
<p>
<UL>
<li> + for addition
<li> - for subtraction
<li> * for multiplication
<li> / for integer division (the dividend must be multiple of the divisor)
<li> % for modulus (remainder of the integer division)
<li> ^ for exponentiation (the exponent must be real and greater than or equal to zero).
<li> <strong>n!</strong>: factorial (<var>n</var> must be real and greater than or equal to zero).
<li> <strong>p#</strong>: primorial (product of all primes less or equal than <var>p</var>).
<li> <strong>F(n)</strong>: Fibonacci number F<sub>n</sub>
<li> <strong>L(n)</strong>: Lucas number L<sub>n</sub> = F<sub><var>n</var>-1</sub> + F<sub><var>n</var>+1</sub>
<li> <strong>P(n)</strong>: Unrestricted Partition Number (number of decompositions of <var>n</var> into sums of integers without regard to order).
<li> <strong>Re(n)</strong>: Real part of <var>n</var>.
<li> <strong>Im(n)</strong>: Imaginary part of <var>n</var>.
<li> <strong>Norm(n)</strong>: Norm of <var>n</var>, it equals Re(<var>n</var>)<sup>2</sup> + Im(<var>n</var>)<sup>2</sup>.
<li> <strong>Gcd(m,n)</strong>: Greatest common divisor of these two gaussian integers.
<li> <strong>Modinv(m,n)</strong>: inverse of <var>m</var> modulo <var>n</var>, only valid when gcd(m,n)=1.
<li> <strong>Modpow(m,n,r)</strong>: finds <var>m</var><sup><var>n</var></sup> modulo <var>r</var> (<var>n</var> must be real).
</ul>
<p>You can use the prefix <em>0x</em> for hexadecimal numbers, for example 0x38 is equal to 56.</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="helphelp"></div>
<div id="result" aria-live="polite"></div>
<div id="status"></div>
<div id="footer">
<p>If you find any error or you have a comment, please fill in the <a href="FORM.HTM?Gaussian+integer+factorization+calculator+feedback">form</a>.</p>
</div>
</article>
<div id="modal-more" class="modal" role="dialog" aria-labelledby="moreopt">
<div class="modal-content">
<div class="modal-header"><span id="close-more" aria-label="close" class="atright">×</span><p id="moreopt">More options</p></div>
<div class="modal-body">
<form class="applet">
<p><label for="curve">New curve number or factor:</label></p><input type="number" id="curve" value="" class="input" min="0" step="1"/>
<input type="button" id="ncurve" value="New curve" />
<input type="button" id="nfactor" value="New factor" />
</form>
</div></div></div>
<div id="modal-config" class="modal" role="dialog" aria-labelledby="conf">
<div class="modal-content">
<div class="modal-header"><span id="close-config" aria-label="close" class="atright">×</span><p id="conf">Configuration</p></div>
<div class="modal-body">
<form class="applet">
<p><label for="digits">Digits per group</label> <input type="number" id="digits" value="6" min="0" max="10000" step="1"/></p>
<p><input type="checkbox" id="batch"><label for="batch">Batch mode</label></p>
<p><input type="checkbox" id="verbose"><label for="verbose">Verbose mode</label></p>
<p><input type="checkbox" id="pretty"><label for="pretty">Pretty print</label></p>
<p><input type="checkbox" id="cunnin"><label for="cunnin">Use Cunningham tables on server</label></p>
<p><input type="button" id="save-config" value="Save" /><input type="button" id="cancel-config" value="Cancel" /></p>
</form>
</div></div></div>
</body>
</html>