mersenneforum.org > Math Elliptic Curve Method factoring - Fermat numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2002-09-19, 00:01 #2 Xyzzy     Aug 2002 5×1,697 Posts How much memory can this use? Will it use a pile if you let it?
 2002-09-22, 10:23 #3 patrik     "Patrik Johansson" Aug 2002 Uppsala, Sweden 1101010012 Posts lowm.txt and lowp.txt? What's the purpose of the files lowm.txt and lowp.txt? Does prime95 divide by all known factors before starting ECM on a number? And does that increase the chance of finding a remaining factor? Or are they just there for prime95 not to report any already known factor? If they are important then perhaps one should enter e.g. F0-F4 and all known factors of F5-F13 into lowm.txt as known factors of M32768 before running it. Or is prime95 smart enough to look in lowp.txt if you are factoring M(2^n)? Patrik Johansson
 2002-09-22, 10:53 #4 patrik     "Patrik Johansson" Aug 2002 Uppsala, Sweden 52·17 Posts This has in fact actually been done. I just discovered that the updated lowm.txt does inlcude these factors. /Patrik
 2002-09-22, 17:59 #5 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 111910 Posts ECM memory usage In response to the question of xyzzy on how much memory ECM will use: I believe that Prime95 is limited to the daytime and nighttime memory allocations which can be set via the Options/CPU dialog box. Default is 8M. This appears to be sufficient for small exponents, but I have found that even for exponents the size of P131072 (F17), that allocating more memory, say 16M or 24M, speeds up stage 2 processing by 10% to 30% or so. The reason is that the program precomputes a number of Fourier transforms that ideally should reside in RAM rather than on disk for best results. 8M may be enough for the basic program but not enough for the all the FFT precomputation results. George Woltman says in the readme file that ECM requires a minimum of 192 times the FFT size. I do not know, however, if the FFT size for various size exponents is readily available anywhere. He says that P-numbers can take a larger FFT size than M-numbers, so for the 25th Fermat number, P33554432, I took as a guide on the benchmarks page the information that FFT size for M-numbers in this range is 1792 K-bytes. Round up to 2M per FFT and you get 384M needed, which seemed sufficient for the one curve I ran on this number. But I also have found that F20 (or P1048576) runs fine on 24M, a little faster on 40M. My guess is that the optimum memory follows a formula like (minimum memory for the code) + 192*(FFT size). I will ask George Woltman if he has any additional information on this. As to the question of Patrik on factors in the lowm.txt or lowp.txt files, it appears that the program does a consistency check when it starts a curve to be sure that these are actually factors of the number it is attempting to factor. However, the curve is run by doing calculations modulo the full number 2^n+/-1 and my understanding is that it is only at the end of each stage that the program does a GCD (Greatest Common Divisor) calculation to determine whether it has turned up any factors not listed in the lowm.txt or lowp.txt file. Incidentally, while testing whether the program worked correctly on 2^(2^n)-1 numbers, one test was to remove known factors from the lowm.txt file to see if the program could "rediscover" these factors. It has been quite successful so far considering the number of curves run, but I am still looking for the 40 digit factor of F10, the 49 digit factor of F9, and the 33 digit factor of F15. More curves! Thanks for your questions! Phil Moore
 2002-09-22, 23:57 #6 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 3×373 Posts FFT sizes George Woltman just sent me the following information which I am passing on. I believe that for the Pentium-4, the crossover points may be slightly more conservative, but this should be enough information to estimate memory needs for ECM: Hi, Here are the V21 non-P4 FFT crossovers. 2^N+1 crossovers are the same except the FFT size must be a power of 2. 759 32 945 40 1121 48 1501 64 1861 80 2201 96 2951 128 3671 160 4371 192 5841 256 7221 320 8651 384 10100 448 11520 512 14250 640 17000 768 19900 896 22650 1024 28350 1280 33700 1536 39200 1792 45100 2048 55800 2560 66300 3072 77400 3584 88900 4096 110000 5120 131000 6144 153100 7168 175000 8192 217000 10240 258400 12288 302500 14336 345500 16384 429000 20480 511000 24576 597000 28672 682000 32768 846000 40960 1010000 49152 1180000 57344 1348000 65536 1672000 81920 1999000 98304 2335000 114688 2665000 131072 3300000 163840 3945000 196608 4598000 229376 5255000 262144 6520000 327680 7760000 393216 9040000 458752 10330000 524288 12830000 655360 15300000 786432 17850000 917504 20400000 1048576 25350000 1310720 30150000 1572864 35100000 1835008 40250000 2097152 50000000 2621440 59400000 3145728 69100000 3670016 79300000 4194304
 2002-09-23, 11:21 #7 Philippe   66228 Posts maybe a problem with ECM Hello last year, I spent months to compute many curves of fermat numbers with p95 v21 on a PC without access to internet. I just downloaded the program from another computer. That's why I didn't have access to the lowp.txt files. So, the curves rediscovered the known factors each time. And here, I noticed a strange fact : when you ran a row of, for example, 100 curves for F12, the first one ALWAYS find factors and then the next ones with a "normal" probability (for example 50 % to find a small f12 factor with b1=11000000). I did test it with large amount of curves, with small or large B1's. I send my complete results file to Mr WOLTMAN, asking him this question but he answered all was OK. I do believe him but (eeerh, in fact, I didn't completely believe him...;)): has someone noticed this problem ? is it reproductible? (I had a celeron 400 ) couldn't we imagine a pseudo-random number generator problem? (how is the seed computed for the first curve? with the date as in gmp-ecm?) As I couldn't find a solution to this problem, I joined another factoring project but it would interest me to have an answer. Thanks. Philippe
 2002-09-23, 16:16 #8 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 22·1,987 Posts If you run without a lowp.txt file the first curve reports all the factors it finds. The second curve reports any factors not found by the first curve, and so on until you exit prime95 and restart it.
 2002-09-24, 21:25 #9 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 3·373 Posts Fermat factors chart Attached is an Excel spreadsheet and chart showing all known factors of Fermat numbers up to 2^(2^32)+1. Notice that 2^(2^n)+1 is prime for n=0,1,2,3,4 and that these numbers are completely factored for n=5 through 11. The complete set of data is available at http://www.prothsearch.net/fermat.html Phil Moore
 2002-09-26, 10:22 #10 Xyzzy     Aug 2002 5×1,697 Posts I found a factor tonight, and it ain't in lowm.txt! Is this a good one, or am I getting excited over nothing? [code:1]Stage 1 complete. 1152466582 transforms, 1 modular inverses. Time: 2625.430 sec. M4096 has a factor: 4533797969079998187896395234756340228327120018230672063369857139206452673745645938373167615[/code:1] I think it is 91 digits long...
2002-09-26, 14:55   #11
binarydigits

Aug 2002

1101002 Posts

Quote:
 Originally Posted by Xyzzy I found a factor tonight, and it ain't in lowm.txt! Is this a good one, or am I getting excited over nothing?
Sorry but that 91-digit number is composite; it is at least divisible by 5.

 Similar Threads Thread Thread Starter Forum Replies Last Post EdH Other Mathematical Topics 52 2021-01-29 21:17 Dirac Factoring 11 2007-11-01 14:01 bongomongo Factoring 5 2006-12-21 18:19 Carlos Programming 0 2005-09-11 12:50 philmoore Math 2 2002-11-12 01:11

All times are UTC. The time now is 14:51.

Fri Aug 12 14:51:50 UTC 2022 up 36 days, 9:39, 2 users, load averages: 1.28, 1.31, 1.25

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔