forked from alpertron/calculators
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ECM.HTM
409 lines (408 loc) · 34.7 KB
/
ECM.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
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
<!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 integers using ECM and SIQS algorithms. Written by Dario Alpern." />
<link rel="alternate" hreflang="es" href="ECMC.HTM" />
<link rel="manifest" href="ecm.webmanifest">
<meta name="theme-color" content="#db5945">
<link rel="icon" href="favicon.ico" type="image/x-icon" />
<title>Integer factorization calculator</title>
<style>
@media print {#smallheader {display:none;}}
@media screen {
#smallheader {background-color:#000080; color:#FFFFFF; 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%;}
.newline {clear:both;}
}
.atright {float:right;}
@media screen and (max-width: 400px) {#smallheader {font-size:0.7em;}}
@media screen and (min-width: 400px) {#smallheader {font-size:1em;}}
@media screen and (min-width: 500px) {#configleft {float:left;}}
body {font-family: arial; margin: 0; padding: 0; background-color:#FFFFFF; color:#000000}
h1 {text-align:center;}
.lf {padding:0.2em; clear:both;}
.blue {color: #0000FF;}
.applet {margin-left: auto;margin-right: auto; border: 0px none;width:90%;text-align:center;background-color:#c0c0c0;padding:10px;}
#cont {display:none;}
#digits {width:5em}
#value {white-space:pre;overflow-wrap:normal;overflow:auto;}
#wizard {display:none;}
.inline {display:inline;}
.pad {padding:10px;}
.hex {font-family: Courier, "Lucida Console", monospace}
.und {text-decoration: underline;}
#tableCurves {max-width:700px; margin-left:auto; margin-right:auto;}
#help,#result,#status,#footer {margin: 3px; padding: 3px;}
#more,#stop {display:none}
@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;}}
.modal-header {padding: 2px 10px; background-color: #5cb85c; color: white;}
.modal-body {padding: 2px 10px;}
.modal-content {
position: absolute; top: 50%; left: 50%; transform: translate(-50%, -50%);
background-color: #fefefe;
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);
}
.modal {
display: none;
position: fixed;
z-index: 1;
left: 0;
top: 0;
width: 100%;
height: 100%;
overflow: auto;
background-color: rgb(0,0,0);
background-color: rgba(0,0,0,0.4);
}
#close {float:right}
#modal-header-text {font-size:1.5em}
table, td, th { border: 1px solid gray }
</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>
<main id="main">
<article>
<h1>Integer factorization calculator</h1>
<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="ECM.HTM" itemprop="url">
<span itemprop="title">Integer factorization calculator</span>
</a>
</div>
</div>
<form class="applet">
<label for="value">Value</label><textarea id="value" rows="4" class="input"></textarea>
<br class="newline"/>
One numerical expression or loop per line. Example: x=3;x=n(x);c<=100;x‑1
<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" />
<input type="button" id="openwizard" value="Wizard" />
<div class="lf"></div>
<input type="hidden" id="app" value="0"/>
</form>
<div id="help" aria-live="polite">
<p>This application factors numbers or numeric expressions using fast algorithms ECM and SIQS.</p>
<p>The program uses local storage to remember the progress of the factorization, so you can complete the factorization of a large number in several sessions. Your computer will remember the state of the factorization. You only have to reload this page.</p>
<p>The execution time depends on the magnitude of the second largest prime factor and on your computer speed.</p>
<p>Since all calculations are performed in your computer, you can disconnect it from the Internet while the factorization is in progress. You can even start this application without Internet connection after the first run.</p>
<p>The source code is written in C and compiled to asm.js and WebAssembly. The latter is faster, but it is not supported in all Web browsers. You can see the version while a number is being factored.</p>
<p>See <a href="ECMREC.HTM" title="ECM Factorization records">factorization records</a> for this application.</p>
<h2>Expressions</h2>
<p>You can 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
<li> % for modulus (remainder of the integer division)
<li> ^ or ** for exponentiation (the exponent must be greater than or equal to zero).
<li> <strong><</strong>, <strong>==</strong>, <strong>></strong>; <strong><=</strong>, <strong>>=</strong>, != for comparisons. The operators return zero for false and -1 for true.
<li> <strong>AND</strong>, <strong>OR</strong>, <strong>XOR</strong>, <strong>NOT</strong> for binary logic.
<li> <strong>SHL</strong>: Shift left the number of bits specified on the right operand.
<li> <strong>SHR</strong>: Shift right the number of bits specified on the right operand.
<li> <strong>n!</strong>: factorial (<var>n</var> must be greater than or equal to zero).
<li> <strong>p#</strong>: primorial (product of all primes less or equal than <var>p</var>).
<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> <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>N(n)</strong>: Next probable prime after <em>n</em></li>
<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>Gcd(m,n)</strong>: Greatest common divisor of these two 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>.
<li> <strong>Totient(n)</strong>: finds the number of positive integers less than <var>n</var> which are relatively prime to <var>n</var>.
<li> <strong>IsPrime(n)</strong>: returns zero if <var>n</var> is not probable prime, -1 if it is.
<li> <strong>NumDivs(n)</strong>: Number of positive divisors of <var>n</var> either prime or composite.
<li> <strong>SumDivs(n)</strong>: Sum of positive divisors of <var>n</var> either prime or composite.
<li> <strong>NumDigits(n,r)</strong>: Number of digits of <var>n</var> in base <var>r</var>.
<li> <strong>SumDigits(n,r)</strong>: Sum of digits of <var>n</var> in base <var>r</var>.
<li> <strong>RevDigits(n,r)</strong>: finds the value obtained by writing backwards the digits of <var>n</var> in base <var>r</var>.
<li> <strong>ConcatFact(m,n)</strong>: Concatenates the prime factors of <var>n</var> according to the mode expressed in <var>m</var> which follows this table:<br><br>
<table>
<caption>ConcatFact function modes</caption>
<tr><th scope="col">Mode</th><th scope="col">Order of factors</th><th scope="col">Repeated factors</th></tr>
<tr><td>0</td><td>Ascending</td><td>No</td></tr>
<tr><td>1</td><td>Descending</td><td>No</td></tr>
<tr><td>2</td><td>Ascending</td><td>Yes</td></tr>
<tr><td>3</td><td>Descending</td><td>Yes</td></tr>
</table>
</li>
</ul>
<p>You can use the prefix <em>0x</em> for hexadecimal numbers, for example 0x38 is equal to 56.</p>
<div class="tableCurves"><table>
<caption>Optimal values of B1 and expected curves</caption>
<tr><th scope="col">Digits</th><th scope="col">Values of B1</th><th scope="col">Expected curves</th></tr>
<tr><td>15</td><td>2000</td><td>25</td></tr>
<tr><td>20</td><td>11000</td><td>90</td></tr>
<tr><td>25</td><td>50000</td><td>300</td></tr>
<tr><td>30</td><td>250000</td><td>700</td></tr>
<tr><td>35</td><td>1 000000</td><td>1800</td></tr>
<tr><td>40</td><td>3 000000</td><td>5100</td></tr>
<tr><td>45</td><td>11 000000</td><td>10600</td></tr>
<tr><td>50</td><td>43 000000</td><td>19300</td></tr>
<tr><td>55</td><td>110 000000</td><td>49000</td></tr>
<tr><td>60</td><td>260 000000</td><td>124000</td></tr>
<tr><td>65</td><td>850 000000</td><td>210000</td></tr>
<tr><td>70</td><td>2900 000000</td><td>340000</td></tr>
</table></div>
<p>The program runs 25 curves with limit B1 = 2000, 300 curves with limit B1 = 50000, 1675 curves with limit B1 = 1000000 and finally it uses curves with limit B1 = 11000000 until all factors are found.</p>
<h2>Factoring a number in several machines</h2>
<p>The ECM factoring algorithm can be easily parallelized in several machines. In order to do it, run the factorization in the first computer from curve 1, run it in the second computer from curve 10000, in the third computer from curve 20000, and so on.
In order to change the curve number when a factorization is in progress, press the button named <strong>More</strong>, type this number on the input box located on the new window and press the <strong>New Curve</strong> button.</p>
<p>When one of the machines discovers a new factor, you should enter this factor in the other computers by typing it in the bottom-right input box and pressing Enter (or clicking the <strong>Factor</strong> button).</p>
<h2>Factoring using the Self Initializing Quadratic Sieve (SIQS)</h2>
<p>When the number to be factorized is in the range 31 to 95 digits, after computing some curves in order to find small factors, the program switches to SIQS (if the checkbox located below the applet enables it), which is an algorithm that is much faster than ECM when the number has two large prime factors. Since this method needs a large amount of your computer's memory, if you restart the applet the factorization begins from scratch. In order to start factoring immediately using SIQS, you can enter 0 in the New Curve box.</p>
<table>
<caption>Threshold for switching to SIQS</caption>
<tr><th scope="row">Digits</th><td>31-55</td><td>56-60</td><td>61-65</td><td>66-70</td><td>71-75</td><td>76-80</td><td>81-85</td><td>86-90</td><td>91-95</td></tr>
<tr><th scope="row">Curve</th><td>10</td><td>15</td><td>22</td><td>26</td><td>35</td><td>50</td><td>100</td><td>150</td><td>200</td></tr>
</table>
<h2>Configuration</h2>
<p>You can change settings for this application by pressing the Config button when a factorization is not in progress. A new window will pop up where you can select different settings:</p>
<ul>
<li><strong>Digits per group</strong>: In order to improve readability, big numbers are separated by spaces forming groups of a fixed number of digits. With this input box, you can determine the number of digits in a group.</li>
<li><strong>Verbose mode</strong>: Not ready yet.</li>
<li><strong>Pretty print</strong>: If this checkbox is set, the exponents are shown in superscripts and the multiplication sign is " × ". The application also shows the number of digits for numbers with more than 30 digits.
If the checkbox is not set, the exponents are preceded by the exponentiation sign " ^ " and the multiplication is indicated by asterisks. Also the number of digits is never displayed. This mode eases copying the results to other mathematical programs.</li>
<li><strong>Hexadecimal output</strong>: If this checkbox is set, the numbers are shown in hexadecimal format instead of decimal, which is the common notation.
To enter numbers in hexadecimal format, you will need to precede them by the string 0x. For instance 0x38 = 56. The program shows hexadecimal numbers with monospaced font.</li>
<li><strong>Use Cunningham tables on server</strong>: When selected, if the number to be factored has the form a<sup>b</sup> ± 1, the application will attempt to retrieve the known factors from the Web server.
In order to reduce the database, only factors with at least 14 digits are included, so the application will find the small factors. These factors comes from <a href="http://myfactors.mooo.com/">Jonathan Crombie list</a> and it includes 2674850 factors of Cunningham numbers.</li>
</ul>
<p>The configuration is saved in your device, so when you start again the Web browser, all settings remain the same.
<p>
<h2>Batch factorization</h2>
<p>Write an expression per line, then press the appropriate button. The output will be placed in the lower pane.</p>
<p>Blank lines or comment lines (which start with a numeral '#' character) will be replicated on the lower pane.</p>
<p>Expression loop: with the following syntax you can factor or determine primality of several numbers typing only one line.
You have to type four or five expressions separated by semicolons:</p>
<ul>
<li>First expression: It must start with the string 'x=' and it sets the first value of x.</li>
<li>Second expression: It must start with the string 'x=' and it sets the next value of x.
<li>Third expression: It holds the end expression condition. If it is equal to zero (meaning false) the loop finishes, otherwise the loop continues.
<li>Fourth expression: It holds the expression to be factored.</li>
<li>Optional fifth expression: If this expression is different from zero (meaning true), the fourth expression is displayed or factored, and if is zero (meaning false), the fourth expression is ignored.
</ul>
<p>Except for the first expression, all other expressions must include the variable <var>x</var> and/or the counter <var>c</var>.</p>
<p>If the end expression is false after processing 1000 numbers, the Continue button will appear. Pressing this button will make the program to process the next 1000 numbers and so on.</p>
<p>Example 1: Find the factors of the first 100 numbers of the form prime minus one.
The line to type is: <code>x=3;x=n(x);c<=100;x-1</code>.</p>
<p>Example 2: Find the Smith numbers less than 10000. A Smith number, according to Wikipedia, is a composite number for which, in a given base (in base 10 by default), the sum of its digits is equal to the sum of the digits in its prime factorization.
The line to type is: <code>x=1;x=x+1;x<10000;x;sumdigits(x, 10)==sumdigits(concatfact(2,x),10) and not isprime(x)</code>
<h2>Source code</h2>
<p>You can download the source of the current program and the old 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 22 May 2018.</p>
</div>
<div id="helphelp"></div>
<div id="result" aria-live="polite"></div>
<div id="status"></div>
<form id="cont" class="pad">
<input type="button" id="continue" value="Continue" />
</form>
<div id="footer">
<p>If you find any error or you have a comment, please fill in the <a href="FORM.HTM?Integer+factorization+calculator+feedback">form</a>.</p>
</div>
</article>
</main>
<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">
<div 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" />
</div>
</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">
<div class="applet">
<fieldset>
<legend>Configuration parameters</legend>
<div id="configleft">
<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="verbose"><label for="verbose">Verbose mode</label></p>
</div>
<div id="configright">
<p><input type="checkbox" id="pretty"><label for="pretty">Pretty print</label></p>
<p><input type="checkbox" id="hex"><label for="hex">Hexadecimal output</label></p>
<p><input type="checkbox" id="cunnin"><label for="cunnin">Use Cunningham tables on server</label></p>
</div>
</fieldset>
<p><input type="button" id="save-config" value="Save" /><input type="button" id="cancel-config" value="Cancel" /></p>
</div>
</div></div></div>
<aside id="wizard">
<h1>Factorization wizard</h1>
<form class="applet">
<fieldset id="output" class="atright">
<legend>Output</legend>
<input type="radio" name="output" id="decW"><label for="decW"><span class="und">D</span>ecimal</label><br>
<input type="radio" name="output" id="hexW"><label for="hexW"><span class="und">H</span>exadecimal</label><br>
</fieldset>
<fieldset id="mode">
<legend>Wizard mode</legend>
<input type="radio" name="mode" id="oneexpr"><label for="oneexpr"><span class="und">P</span>rocess one expression</label><br>
<input type="radio" name="mode" id="loop"><label for="loop"><span class="und">P</span>rocess several expressions in a loop</label><br>
</fieldset>
<label for="wzdinput" id="wzddesc"> </label>
<br class="newline"/>
<input type="text" id="wzdinput" value="" placeholder="Number or numerical expression" class="input"/>
<br class="newline"/>
<p id="wzdexam"> </p>
<input type="button" id="next" value="Next" />
<input type="button" id="cancel" value="Cancel" />
</form>
<h2>Expressions</h2>
<p>You can 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
<li> % for modulus (remainder of the integer division)
<li> ^ or ** for exponentiation (the exponent must be greater than or equal to zero).</li>
<li> <strong><</strong>, <strong>==</strong>, <strong>></strong>; <strong><=</strong>, <strong>>=</strong>, != for comparisons. The operators return zero for false and -1 for true.</li>
<li> <strong>AND</strong>, <strong>OR</strong>, <strong>XOR</strong>, <strong>NOT</strong> for binary logic.
<li> <strong>SHL</strong>: Shift left the number of bits specified on the right operand.
<li> <strong>SHR</strong>: Shift right the number of bits specified on the right operand.
<li> <strong>n!</strong>: factorial (<var>n</var> must be greater than or equal to zero).</li>
<li> <strong>p#</strong>: primorial (product of all primes less or equal than <var>p</var>).</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><var>n</var>-1</sub> + F<sub><var>n</var>+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 <var>n</var> 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>
<li> <strong>Totient(n)</strong>: finds the number of positive integers less than <var>n</var> which are relatively prime to <var>n</var>.</li>
<li> <strong>IsPrime(n)</strong>: returns zero if <var>n</var> is not probable prime, -1 if it is.</li>
<li> <strong>NumDivs(n)</strong>: Number of positive divisors of <var>n</var> either prime or composite.</li>
<li> <strong>SumDivs(n)</strong>: Sum of positive divisors of <var>n</var> either prime or composite.</li>
<li> <strong>NumDigits(n,r)</strong>: Number of digits of <var>n</var> in base <var>r</var>.</li>
<li> <strong>SumDigits(n,r)</strong>: Sum of digits of <var>n</var> in base <var>r</var>.</li>
<li> <strong>RevDigits(n,r)</strong>: finds the value obtained by writing backwards the digits of <var>n</var> in base <var>r</var>.</li>
<li> <strong>ConcatFact(m,n)</strong>: Concatenates the prime factors of <var>n</var> according to the mode expressed in <var>m</var> which follows this table:<br><br>
<table>
<caption>ConcatFact function modes</caption>
<tr><th scope="col">Mode</th><th scope="col">Order of factors</th><th scope="col">Repeated factors</th></tr>
<tr><td>0</td><td>Ascending</td><td>No</td></tr>
<tr><td>1</td><td>Descending</td><td>No</td></tr>
<tr><td>2</td><td>Ascending</td><td>Yes</td></tr>
<tr><td>3</td><td>Descending</td><td>Yes</td></tr>
</table>
</li>
<li id="C">Variable <var>C</var>: number of expressions already processed.</li>
<li id="X">Variable <var>X</var>: variable changed on each iteration of the loop.</li>
</ul>
<p>You can use the prefix <em>0x</em> for hexadecimal numbers, for example 0x38 is equal to 56.</p>
</aside>
<script async>
<!--
(function(q){function t(){a("next").value=d&1?"Hecho":"Done";a("wzddesc").innerHTML=d&1?"Paso 1 de 1: Expresi\u00f3n a factorizar":"Step 1 of 1: Expression to factor";a("wzdexam").innerHTML=" ";g="";k=9}function a(a){return document.getElementById(a)}function u(c,b){a("eval").style.display=c;a("factor").style.display=c;a("config").style.display=c;a("openwizard").style.display=c;a("stop").style.display=b;a("more").style.display=b}function l(c){a("modal-more").style.display="none";m.terminate();
m=0;n(c)}function p(c){m||(v?w||(w=new Blob([new Uint8Array(x)])):w||(w=new Blob(Array.prototype.map.call(document.querySelectorAll("script[type='text/js-worker']"),function(a){return a.textContent}),{type:"text/javascript"})),m=new Worker(window.URL.createObjectURL(w)),m.onmessage=function(b){var c=b.data.substring(0,1);"9"==c&&console.log(b.data.substring(1));if("8"==c)b=b.data.substring(1),localStorage.setItem("ecmFactors",b),localStorage.setItem("ecmCurve","");else if("7"==c)b=b.data.substring(1),
localStorage.setItem("ecmCurve",b);else if("4"==c)a("status").innerHTML=b.data.substring(1);else if(a("result").innerHTML=b.data.substring(1),"2"==c||"6"==c)a("status").innerHTML="",u("inline","none"),a("modal-more").style.display="none","6"==c&&(a("cont").style.display="block")});v?m.postMessage(c):m.postMessage([c,x])}function n(c){var b;d=parseInt(a("app").value)+c;b=a("result");var A=a("value").value.replace(/\u2011/g,"-"),h=String.fromCharCode(0),g=a("helphelp");a("cont").style.display="none";
a("help").style.display="none";g.style.display="block";g.innerHTML=d&1?'<p class="pad">Aprieta el bot\u00f3n <strong>Ayuda</strong> para obtener ayuda para esta aplicaci\u00f3n. Apri\u00e9talo de nuevo para retornar a la factorizaci\u00f3n. Los usuarios con teclado pueden presionar CTRL+ENTER para comenzar la factorizaci\u00f3n. Esta es la versi\u00f3n '+(v?"asm.js":"WebAssembly")+".</p>":'<p class="pad">Press the <strong>Help</strong> button to get help about this application. Press it again to return to the factorization. Keyboard users can press CTRL+ENTER to start factorization. This is the '+
(v?"asm.js":"WebAssembly")+" version.</p>";b.style.display="block";if(""==A)b.innerHTML=d&1?"<p>Por favor ingrese una expresi\u00f3n.</p>":"<p>Please type an expression.</p>";else if("undefined"===typeof Worker)b.innerHTML=d&1?"<p>Esta calculadora necesita Web Workers. Por favor use otro navegador Web.</p>":"<p>This calculator requires Web Workers. Please use another Web browser.</p>";else{u("none","inline");b.innerHTML=d&1?"<p>Factorizando la expresi\u00f3n...</p>":"<p>Factoring expression...</p>";
-2>c&&(d+=6);b=f+","+d+","+e+A+h+localStorage.getItem("ecmFactors");if(-1==c||-2==c)b+=h+a("curve").value;if(-3==c||-4==c)b+="*"+a("curve").value+"^1(2)";x?p(b+h):y=b+h}}function B(){a("next").value=d&1?"Siguiente":"Next";a("wzddesc").innerHTML=d&1?"Paso 1 de 5: Valor inicial de x":"Step 1 of 5: Initial value of x";a("wzdexam").innerHTML=d&1?"No usar variables <var>x</var> o <var>c</var>. Ejemplo para n\u00fameros de Smith menores que 10000: <code>1</code>":"Do not use variables <var>x</var> or <var>c</var>. Example for Smith numbers less than 10000: <code>1</code>";
k=1}function C(){var c=a("next"),b=a("wzddesc"),e=a("wzdexam"),h=a("wzdinput"),f=a("value");c.disabled=!0;switch(++k){case 2:g+="x="+h.value;a("mode").style.display="none";b.innerHTML=d&1?"Paso 2 de 5: Valor de x para la nueva iteraci\u00f3n":"Step 2 of 5: Value of x for new iteration";e.innerHTML=d&1?"Variables <var>x</var> y/o <var>c</var> requeridas. Ejemplo para n\u00fameros de Smith menores que 10000: <code>x+1</code>":"Variables <var>x</var> and/or <var>c</var> required. Example for Smith numbers less than 10000: <code>x+1</code>";
break;case 3:g+=";x="+h.value;b.innerHTML=d&1?"Paso 3 de 5: Condici\u00f3n para finalizar el ciclo":"Step 3 of 5: End loop condition";e.innerHTML=d&1?"Variables <var>x</var> y/o <var>c</var> requeridas. Ejemplo para n\u00fameros de Smith menores que 10000: <code>x<10000</code>":"Variables <var>x</var> and/or <var>c</var> required. Example for Smith numbers less than 10000: <code>x<10000</code>";break;case 4:g+=";"+h.value;b.innerHTML=d&1?"Paso 4 de 5: Expresi\u00f3n a factorizar":"Step 4 of 5: Expression to factor";
e.innerHTML=d&1?"Variables <var>x</var> y/o <var>c</var> requeridas. Ejemplo para n\u00fameros de Smith menores que 10000: <code>x</code>":"Variables <var>x</var> and/or <var>c</var> required. Example for Smith numbers less than 10000: <code>x</code>";break;case 5:g+=";"+h.value;c.value=d&1?"Hecho":"Done";c.disabled=!1;b.innerHTML=d&1?"Paso 5 de 5: Condici\u00f3n para procesar la expresi\u00f3n":"Step 5 of 5: Process expression condition";e.innerHTML=d&1?"Variables <var>x</var> y/o <var>c</var> requeridas. Ejemplo para n\u00fameros de Smith menores que 10000: <code>sumdigits(x,10) == sumdigits(concatfact(2,x),10) and not isprime(x)</code>":
"Variables <var>x</var> and/or <var>c</var> required. Example for Smith numbers less than 10000: <code>sumdigits(x,10) == sumdigits(concatfact(2,x),10) and not isprime(x)</code>";break;case 6:""!=h.value&&(g+=";"+h.value);f.value=g;k=0;a("hex").checked=a("hexW").checked;z();a("main").style.display="block";a("wizard").style.display="none";f.focus();break;default:k=0,f.value=h.value,a("hex").checked=a("hexW").checked,z(),a("main").style.display="block",a("wizard").style.display="none",f.focus()}k&&
(h.value="",h.focus())}function z(){e="1"+(a("verbose").checked?"1":"0")+(a("pretty").checked?"1":"0")+(a("cunnin").checked?"1":"0")+(a("hex").checked?"1":"0");f=a("digits").value;localStorage.setItem("ecmConfig",f+","+e)}var k=0,g,m=0,x=0,d,w,f,e,y,v="undefined"===typeof WebAssembly,r=new XMLHttpRequest;r.open("GET",v?"ecmW0057.js":"ecm0057.wasm",!0);r.responseType="arraybuffer";r.onreadystatechange=function(a){4==r.readyState&&200==r.status&&(x=r.response,y&&p(y))};r.send(null);addEventListener("load",
function(){var c;d=parseInt(a("app").value);a("value").wrap="off";a("eval").onclick=function(){localStorage.setItem("ecmFactors","");n(0)};a("factor").onclick=function(){localStorage.setItem("ecmFactors","");n(2)};a("more").onclick=function(){a("modal-more").style.display="block"};a("config").onclick=function(){a("digits").value=f;a("verbose").checked="1"==e.substr(1,1);a("pretty").checked="1"==e.substr(2,1);a("cunnin").checked="1"==e.substr(3,1);a("hex").checked="1"==e.substr(4,1);a("modal-config").style.display=
"block"};a("openwizard").onclick=function(){a("main").style.display="none";a("wizard").style.display="block";a("mode").style.display="block";a("oneexpr").checked=!0;a("next").disabled=!0;a("wzdinput").value="";a("wzdinput").focus();a("hexW").checked="1"==e.substr(4,1);a("decW").checked="1"!=e.substr(4,1);t()};a("wzdinput").onkeydown=function(b){if(10==b.keyCode||13==b.keyCode)b.preventDefault(),0==a("next").disabled&&C();b.altKey&&(80==b.keyCode?(b.preventDefault(),a("oneexpr").checked?(a("oneexpr").checked=
!1,a("loop").checked=!0,B()):(a("oneexpr").checked=!0,a("loop").checked=!1,t())):68==b.keyCode?(b.preventDefault(),a("decW").checked=!0,a("hexW").checked=!1):72==b.keyCode&&(b.preventDefault(),a("decW").checked=!1,a("hexW").checked=!0));return!0};a("oneexpr").onclick=function(){t()};a("loop").onclick=function(){B()};a("next").onclick=function(){C()};a("wzdinput").oninput=function(){var b=a("wzdinput").value,c=a("next");""!=b?1==k||9==k||0<=b.lastIndexOf("x")||0<=b.lastIndexOf("c")||0<=b.lastIndexOf("X")||
0<=b.lastIndexOf("C")?c.disabled=!1:c.disabled=!0:c.disabled=5==k?!1:!0};a("cancel").onclick=function(){a("main").style.display="block";a("wizard").style.display="none"};a("close-config").onclick=function(){a("modal-config").style.display="none"};a("cancel-config").onclick=function(){a("modal-config").style.display="none"};a("save-config").onclick=function(){oldconfig=e;z();a("modal-config").style.display="none"};a("close-more").onclick=function(){a("modal-more").style.display="none"};a("ncurve").onclick=
function(){l(-2)};a("nfactor").onclick=function(){l(-4)};a("curve").onkeypress=function(a){return 8==a.charCode||0==a.charCode?null:48<=a.charCode&&57>=a.charCode};a("stop").onclick=function(){m.terminate();m=0;u("inline","none");a("result").innerHTML=d&1?"<p>C\u00e1lculo detenido por el usuario.</p>":"<p>Calculation stopped by user</p>";a("status").innerHTML=""};a("value").onkeydown=function(a){10!=a.keyCode&&13!=a.keyCode||!a.ctrlKey||(a.preventDefault(),localStorage.setItem("ecmFactors",""),n(2));
return!0};a("helpbtn").onclick=function(){var b=a("help").style,c=a("helphelp").style,d=a("result"),e=d.style;"block"==b.display&&""!=d.innerHTML?(b.display="none",c.display=e.display="block"):(b.display="block",c.display=e.display="none")};a("continue").onclick=function(){a("cont").style.display="none";p("C")};window.onclick=function(b){var c=a("modal");b.target==c&&(c.style.display="none")};f=localStorage.getItem("ecmConfig");if(null==f||""==f)f=6,e="00100",localStorage.setItem("ecmConfig",f+","+
e);else if(c=f.indexOf(","),0>c)f=6,e="00100",localStorage.setItem("ecmConfig",f+","+e);else{for(e=f.substr(c+1);5>e.length;)e+="0";f=f.substr(0,c)}if(c=localStorage.getItem("ecmFactors"))a("value").value=c.slice(0,c.indexOf("=")),a("curve").value=localStorage.getItem("ecmCurve"),n(-2),a("curve").value="";"serviceWorker"in navigator&&navigator.serviceWorker.register("calcSW.js").then(function(){},function(){})})})(this);
addEventListener("load",function(){(function(q,t,a,u,l,p,n){q.GoogleAnalyticsObject=l;q[l]=q[l]||function(){(q[l].q=q[l].q||[]).push(arguments)};q[l].l=1*new Date;p=t.createElement(a);n=t.getElementsByTagName(a)[0];p.async=1;p.src=u;n.parentNode.insertBefore(p,n)})(window,document,"script","https://www.google-analytics.com/analytics.js","ga");ga("create","UA-4438475-1","auto");ga("send","pageview")});
//-->
</script>
<script type="text/js-worker">
var exports,HEAPU8,wasmLoaded,env={databack:function(b){self.postMessage(PtrToString(b))},tenths:function(){return Math.floor((new Date).getTime()/100)},getCunn:function(b){var a=new XMLHttpRequest;a.open("GET","https://www.alpertron.com.ar/"+PtrToString(b),!1);a.send(null);200==a.status&&ConvertToString(exports.getFactorsAsciiPtr(),a.responseText)}},info={env:env};
self.onmessage=function(b){wasmLoaded?(ConvertToString(exports.getInputStringPtr(),b.data[0]),exports.doWork()):WebAssembly.instantiate(b.data[1],info).then(function(a){wasmLoaded=1;exports=a.instance.exports;HEAPU8=new Uint8Array(exports.memory.buffer);ConvertToString(exports.getInputStringPtr(),b.data[0]);exports.doWork()})};
function PtrToString(b){var a=-1,c=0,e="",d="";do{for(c=0;1024>c;c++){a=HEAPU8[b++>>0];if(0==a)break;128<=a&&(a=(a-192<<6)+HEAPU8[b++>>0]-128);e+=String.fromCharCode(a)}d+=e;e=""}while(0!=a);return d+e}function ConvertToString(b,a){var c=b,e=a.length,d,f;for(d=0;d<e;d++)f=a.charCodeAt(d),128>f?HEAPU8[c++]=f:(HEAPU8[c++]=(f>>6)+192,HEAPU8[c++]=(f&63)+128);HEAPU8[c]=0};
</script>
</body>
</html>