forked from alpertron/calculators
-
Notifications
You must be signed in to change notification settings - Fork 0
/
GAUSIANO.HTM
251 lines (249 loc) · 15.7 KB
/
GAUSIANO.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="es">
<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="Aplicación Javascript que factoriza enteros gausianos de la forma (a+b*i). Hecho por Dario Alpern." />
<meta name="theme-color" content="#db5945">
<link rel="alternate" hreflang="en" href="GAUSSIAN.HTM" />
<link rel="prefetch" href="gaussianW0026.js" />
<link rel="manifest" href="gausiano.webmanifest">
<title>Factorización de enteros gausianos</title>
<style type="text/css">
@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="ENGLISH.HTM" hreflang="en" title="Dario Alpern's Web site in English">ENG</a></div>
<ul>
<li>
Electrónica
<ul class="alignleft">
<li><a href="INTEL.HTM" title="Todos los microprocesadores de Intel desde el 4004 al Pentium">Microprocesadores Intel</a></li>
</ul>
</li>
<li>
Matemáticas
<ul class="alignleft">
<li><a href="CALDORAS.HTM" title="Programas en Java y Javascript que implementan calculadoras">Calculadoras</a></li>
<li><a href="TNUMEROS.HTM" title="Artículos y programas sobre teoría de números">Teoría de números</a></li>
<li><a href="PROBLEMAS.HTM" title="Problemas matemáticos interesantes">Problemas</a></li>
</ul>
</li>
<li>
Programas
<ul class="alignright">
<li><a href="ENSAM386.HTM" title="Programas escritos en lenguaje ensamblador del 80386">Assembler 80386</a></li>
<li><a href="PROGJAVA.HTM" title="Programas escritos en Java">Java</a></li>
<li><a href="JUEGOS.HTM" title="Juegos en línea y para descargar">Juegos</a></li>
</ul>
</li>
<li class="alignright">
Contacto
<ul class="alignright">
<li><a href="PERSONAL.HTM" title="Información personal">Personal</a></li>
<li><a href="FORMULAR.HTM" title="Formulario para enviar comentarios">Comentarios</a></li>
<li><a href="GBOOK.HTM" title="Viejo y nuevo libro de visitas">Libro de invitados</a></li>
<li><a href="DONATION.HTM" title="Donaciones al autor de este sitio Web">Donaciones</a></li>
</ul>
</li>
</ul>
<br class="newline"/>
</nav>
<article>
<h1>Factorización de enteros gausianos</h1>
<script async="async" type="application/javascript" src="gaussian0026.js"></script>
<div class="pad">
<div id="a" itemscope="itemscope" itemtype="http://data-vocabulary.org/Breadcrumb" itemref="b" class="inline">
<a href="/" 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="PROGJAVA.HTM" itemprop="url">
<span itemprop="title">Programas</span>
</a> ›
</div>
<div id="c" itemscope="itemscope" itemtype="http://data-vocabulary.org/Breadcrumb" itemprop="child" class="inline">
<a href="GAUSIANO.HTM" itemprop="url">
<span itemprop="title">Factorización de enteros gausianos</span>
</a>
</div>
</div>
<form id="applet">
<label for="value">Valor</label><input type="text" id="value" value="" class="input"/>
<div class="lf"></div>
<input type="button" id="more" value="Más" />
<input type="button" id="eval" value="Solo evaluar" />
<input type="button" id="factor" value="Factorizar" />
<input type="button" id="stop" value="Parar" />
<input type="button" id="helpbtn" value="Ayuda" />
<input type="button" id="config" value="Config" />
<div class="lf"></div>
<input type="hidden" id="app" value="1"/>
</form>
<div id="help" aria-live="polite">
<p>Los enteros gausianos son números complejos que tienen la forma <var>a</var> + <var>b</var>i, donde <var>a</var> y <var>b</var> son números enteros en la recta real.</p>
<p>Este applet es capaz de factorizar un entero gausiano como un producto de primos gausianos. Esta descomposición es única, si no consideramos el orden de los factores y los primos asociados. Estos conjuntos de primos asociados se obtienen multiplicando un primo por una potencia de i (por eso cada número primo tiene tres asociados). Para eliminar este problema, tomamos el primo tal que a >= |b|.</p>
<h2>Cómo factorizar enteros gausianos</h2>
<p>Un comcepto importante necesario para la factorización de enteros gausianos es la norma. Ésta se define como: <span role="math" aria-label="norma de a más b i es igual a a al cuadrado más b al cuadrado">N(<var>a</var>+<var>b</var><var>i</var>) = <var>a</var><sup>2</sup> + <var>b</var><sup>2</sup></span>.
<p>El producto de la norma de dos enteros gausianos es igual a la norma del producto de estos números como se muestra a continuación:</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>En la penúltima expresión nos valemos de la propiedad <var>i</var><sup>2</sup> = -1.</p>
<p>Esto significa que como primer paso para factorizar números gausianos, debemos hallar los factores primos de su norma, así obtenemos las normas de los factores del número original.</p>
<p>El segundo paso consiste en obtener los factores a partir de las normas halladas.</p>
<p>Existen tres casos:</p>
<ol>
<li>El factor primo <var>p</var> de la norma es 2: en este caso los factores primos del entero gausiano pueden ser 1+i o 1-i (hay que probar cuál divide al número).</li>
<li>El factor primo <var>p</var> de la norma es múltiplo de 4 más 3: este valor no se puede expresar como suma de dos cuadrados, así que <var>p</var> no es una norma, pero <var>p</var><sup>2</sup> sí lo es.
Como <var>p</var><sup>2</sup> = <var>p</var><sup>2</sup> + 0<sup>2</sup>, y no existe una norma prima que divida <var>p</var><sup>2</sup>, el número <var>p</var> + 0<var>i</var> es un primo gausiano, y deberemos descartar el factor repetido <var>p</var>.
<li>El factor primo <var>p</var> de la norma es múltiplo de 4 más 1: este número se puede expresar como suma de dos cuadrados utilizando los métodos explicados en la página de <a href="https://www.alpertron.com.ar/4CUADR.HTM">suma de cuadrados</a>.
Si <var>p</var> = <var>m</var><sup>2</sup> + <var>n</var><sup>2</sup>, entonces deberemos verificar si <var>m</var> + <var>n</var><var>i</var> o <var>m</var> − <var>n</var><var>i</var> son divisores del número gausiano original.</li>
</ol>
<p>¿Por qué un número que es múltiplo de 4 más 3 no puede expresarse como suma de cuadrados? Esto se debe a que el cuadrado de un número par es múltiplo de 4 y el cuadrado de un número impar es múltiplo de 4 más 1. De esta manera obtenemos:</p>
<ul>
<li>par<sup>2</sup> + par<sup>2</sup> = múltiplo de 4</li>
<li>par<sup>2</sup> + impar<sup>2</sup> = múltiplo de 4 más 1</li>
<li>impar<sup>2</sup> + par<sup>2</sup> = múltiplo de 4 más 1</li>
<li>impar<sup>2</sup> + impar<sup>2</sup> = múltiplo de 4 más 2</li>
</ul>
<p>Así que bajo ninguna circunstancia una suma de dos cuadrados puede ser múltiplo de 4 más 3.</p>
<p>Por supuesto el primer paso es mucho más complicado que el segundo. Esto es porque no conocemos métodos eficientes de factorización de números enteros.</p>
<p>Ejemplo: factorizar el entero gausiano 440 − 55i</p>
<p>La norma es 440<sup>2</sup> + 55<sup>2</sup> = 196625 = 5 × 5 × 5 × 11 × 11 × 13</p>
<p>Tanto 5 como 13 son múltiplos de 4 más 1 mientras que 11 es múltiplo de 4 más 3. Podemos valernos de 5 = 2<sup>2</sup> + 1<sup>2</sup> y 13 = 3<sup>2</sup> + 2<sup>2</sup></p>
<p>Como 11 es un primo gausiano, podemos dividir el número original por 11 y hallamos el cociente 44 − 5i.</p>
<p>Para los tres factores de la norma iguales a 5, deberemos dividir el resultado del paso anterior 44 − 5i por 2−i o 2+i. Obtenemos: 44 − 5i = (2+i)<sup>2</sup> × (2-i) × (3 − 2i)</p>
<p>Para el factor 13 deberemos dividir el resultado del paso antrerior 3 − 2i por 3 + 2i ó 3 − 2i. Por supuesto solo 3 − 2i divide a 3 − 2i.</p>
<p>La factorización completa es: 440 − 55i = 11 × (2 + i)<sup>2</sup> × (2 − i) × (3 − 2i).</p>
<h2>Expresiones</h2>
<p>Para ingresar la parte imaginaria de un entero gausiano podrá utilizar el símbolo <var>i</var>, como por ejemplo en 3+4i.</p>
<p>Además puede entrar expresiones que usen los siguientes operadores, funciones y paréntesis:</p>
<p>
<ul>
<li> + para suma.</li>
<li> - para resta.</li>
<li> * para multiplicación.</li>
<li> / para división entera.</li>
<li> % para módulo (resto de la división).</li>
<li> ^ para exponenciación (el exponente debe ser real y mayor o igual que cero).</li>
<li> <B>n!</B>: factorial (<var>n</var> debe ser real y mayor o igual que cero).</li>
<li> <B>p#</B>: primorial (producto de todos los primos menores o iguales que <var>p</var>).</li>
<li> <B>F(n)</B>: número de Fibonacci F<SUB>n</SUB>.</li>
<li> <B>L(n)</B>: número de Lucas L<SUB>n</SUB> = F<SUB>n-1</SUB> + F<SUB>n+1</SUB>.</li>
<li> <B>P(n)</B>: particiones irrestrictas (cantidad de descomposiciones de <var>n</var> en sumas de numeros enteros sin tener en cuenta el orden).</li>
<li> <B>Re(n)</B>: parte real de <var>n</var>.</li>
<li> <B>Im(n)</B>: parte imaginaria de <var>n</var>.</li>
<li> <B>Norm(n)</B>: norma de <var>n</var>, equivale a Re(n)<SUP>2</SUP> + Im(n)<SUP>2</SUP>.</li>
<li> <B>Gcd(m,n)</B>: máximo común divisor de estos dos enteros gausianos.</li>
<li> <B>Modinv(m,n)</B>: inverso del valor <var>m</var> módulo <var>n</var>, sólo válido si gcd(m,n)=1.</li>
<li> <B>Modpow(m,n,r)</B>: Calcula <var>m</var><sup><var>n</var></sup> módulo <var>r</var> (<var>n</var> debe ser real).</li>
</ul>
<p>Puedes usar el prefijo <em>0x</em> para números hexadecimales, por ejemplo 0x38 es igual a 56.</p>
<h2>Código fuente</h2>
<p>Puedes bajar el código fuente del programa actual y del viejo applet de factorización de enteros gausianos desde <a href="https://github.com/alpertron/calculators">GitHub</a>. El código fuente está escrito en lenguaje C, por lo que es necesario <a href="https://kripken.github.io/emscripten-site/docs/getting_started/downloads.html">Emscripten</a> para generar Javascript.</p>
<p>Escrito por Dario Alpern. Actualizado el 9 de diciembre de 2017.</p>
</div>
<div id="helphelp"></div>
<div id="result" aria-live="polite"></div>
<div id="status"></div>
<div id="footer">
<p>Si encuentra algún error o tiene algún comentario, por favor llene el <a href="FORM.HTM?Comentario+de+factorizacion+de+enteros+gausianos">formulario</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">Más opciones</p></div>
<div class="modal-body">
<form class="applet">
<p><label for="curve">Nuevo número de curva o factor:</label></p><input type="number" id="curve" value="" class="input" min="0" step="1"/>
<input type="button" id="ncurve" value="Nueva curva" />
<input type="button" id="nfactor" value="Nuevo 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">Configuración</p></div>
<div class="modal-body">
<form class="applet">
<p><label for="digits">Dígitos por grupo</label> <input type="number" id="digits" value="6" min="0" max="10000" step="1"/></p>
<p><input type="checkbox" id="batch"><label for="batch">Factorización en lotes</label></p>
<p><input type="checkbox" id="verbose"><label for="verbose">Información</label></p>
<p><input type="checkbox" id="pretty"><label for="pretty">Impresión bonita</label></p>
<p><input type="checkbox" id="cunnin"><label for="cunnin">Usar tablas de Cunningham en el servidor</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>