20120930, 19:35  #56  
∂^{2}ω=0
Sep 2002
República de California
2DA8_{16} Posts 
Quote:
Currently I am running k = 185 to depth 1e13 on 1 core, and shallower sieving runs for all other k < 1000 which passed my default Mfactor sieve (i.e. primes up to ~1e6) on this exponent. Last thing I need to do is to add the code needed to start at some userprovided lower bound on small primes (code currently always starts from 0, i.e. primes 3  [upper_bound]), which will be needed to support ranged (and distributed) sieving; once that's in place (hopefully by tomorrow), will post the code tarball here. p.s.: Largest factor I ound so far in my depth1e11 runs: MM(43112609): Q( k = 384 ) has a small factor: 93934458313 p.p.s.: Like the tifosithemed new improved subforum home for the thread. :) Last fiddled with by ewmayer on 20120930 at 19:43 

20121001, 11:08  #57 
Banned
"Luigi"
Aug 2002
Team Italia
4838_{10} Posts 
I hope to gather all ranges done... I'm losing you!
Luigi 
20121001, 12:22  #58 
Romulan Interpreter
"name field"
Jun 2011
Thailand
23215_{8} Posts 
From the tables I posted before, these are gone by raising the khaki rows to 10G:
Code:
M#39  k=225 has a factor : 7333051961 M#39  k=348 has a factor : 2363117143 M#39  k=368 has a factor : 1726045991 M#39  k=440 has a factor : 2733515233 M#39  k=909 has a factor : 6422117551 M#41  k=285 has a factor : 8224776893 M#41  k=393 has a factor : 3826927661 M#41  k=708 has a factor : 1156768079 M#41  k=833 has a factor : 1765835263 M#41  k=1017 has a factor : 1530212371 M#42  k=488 has a factor : 9213085003 M#42  k=593 has a factor : 7645079803 M#42  k=597 has a factor : 6131156639 M#42  k=660 has a factor : 1042419673 M#43  k=716 has a factor : 2821483351 Last fiddled with by LaurV on 20121001 at 12:24 
20121001, 13:42  #59  
Banned
"Luigi"
Aug 2002
Team Italia
2·41·59 Posts 
Quote:
Luigi 

20121001, 14:03  #60  
Jun 2003
5272_{10} Posts 
Quote:
Quote:
Quote:


20121001, 18:17  #61  
∂^{2}ω=0
Sep 2002
República de California
2^{3}×3×487 Posts 
Quote:
Quote:


20121002, 03:30  #62 
∂^{2}ω=0
Sep 2002
República de California
2^{3}×3×487 Posts 
Code tarball (use tar xvzf *.tgz to unpack) is attached. This took a few hours longer than anticipated due to a bug discovered late in testing. The fix slows the code down ~10%; once I find a reliable fix which allows the affected code sequence to again be computed via faster floatingpoint math I'll post it.
1line build instructions are near the top of the C source, beneath the #includes. After building, PLEASE make sure you can run both of the listed selftests (which also summarize the argument syntax) before doing any really deep testing. Have only tested under 64bit Mac OS X, but most of the components here have built OK under Win32. For Win64 users I suggest using a Linux/GCC emulator like mingw64, so you can enjoy the benefit of the 64bit inline ASM in the core modmul routine. The code prints some simple diagnostics for every 2^30 th candidate tried (every few minutes on my system); thus you should run in a dedicated shell or pipe the output to a file if you want to run in background mode. The diagnostics can be used for spotsanity checking using (say) Pari: The only composites appearing in the output should have only factors > the smallp sieve limit, which I have quasioptimized for factoring around depths 1e131e14, via use of the 100000 smallest odd primes; this gives Max sieving prime = 1299721 For imax <= the square of this you should only see base2 PRPs reported in the diagnostics; above that a gradually increasing proportion of composites will appear. I'll let someone else organize sieving ranges, etc  Note that due the aforementioned bugfind and fix I am currently rerunning my deep sieving of MM(43112609) with k = 185 to depth 1e13 (which will need ~2 days on one 2GHz core); suggest others test ranges which are multiples of that one, e.g. the next suchsized interval: Let me know about any build or run issues, and enjoy! ./factor_qmmp k 185 p 43112609 imin 10000000000000 imax 20000000000000 Last fiddled with by ewmayer on 20121002 at 19:05 Reason: .tar.gz > .tgz 
20121002, 06:48  #63 
∂^{2}ω=0
Sep 2002
República de California
10110110101000_{2} Posts 
The ( k = 384 ) Example #2 factor in the C source I first posted was a bogus one found due to the same bug I fixed in said source. (I just rechecked the alleged factor, 93934458313, via Pari, and it's bogus.)
I have uploaded new source tarball (now with a concatenated .tgz extension, which Mike just added to the allowed attachment types at my request.) No change in function, just an updated example which actually yields a factor (if you already downloaded the earlier tar.gz bundle, just modify the buildrelated comment with this new example #2): Test #2: This should find the smallprime factor 7450239943 in around 20 GHzseconds on x86_64: time ./factor_qmmp p 43112609 imin 7000000000 imax 8000000000 k 665 
20121002, 08:50  #64  
Jun 2003
12230_{8} Posts 
Quote:
if 2*k*Mp+1 == 0 (mod f), then k = (2*Mp)^1 (mod f). i.e. for a teensy little cost (of an extra modular inverse), you can figure out the k that f divides, thus turning it into a "all k at a single shot" sieve. Also, using a addition chain, (Mp mod f) can b calculated for all Mps at a fraction of a cost of calculating them individually. 

20121002, 16:28  #65  
Banned
"Luigi"
Aug 2002
Team Italia
12E6_{16} Posts 
Quote:
Code:
gcc factor_qmmp*.c Wall lm O3 o factor_qmmp Code:
$ time ./factor_qmmp time ./factor_qmmp p 43112609 k 5 imax 10000000000 Using first 100000 odd primes; max gap = 114 Max sieving prime = 1299721 Searching for small divisors of MM(43112609): Q( k = 5 ) in interval [3, 10000000000]... MM(43112609): Q( k = 5 ) has a small factor: 582994261 Tried 30482628 ints which passed smallp sieve.. real 0m8.556s user 0m8.530s sys 0m0.000s $time ./factor_qmmp p 43112609 imin 7000000000 imax 8000000000 k 665 Using first 100000 odd primes; max gap = 114 Max sieving prime = 1299721 Searching for small divisors of MM(43112609): Q( k = 665 ) in interval [7000000001, 8000000000]... MM(43112609): Q( k = 665 ) has a small factor: 7450239943 Tried 19833796 ints which passed smallp sieve.. real 0m5.672s user 0m5.650s sys 0m0.000s luigi@luigiubuntu:~/luigi/dm/factor_qmmp$ Last fiddled with by ET_ on 20121002 at 16:31 Reason: Added a red tag and reformatted the output 

20121002, 17:07  #66 
Banned
"Luigi"
Aug 2002
Team Italia
2×41×59 Posts 
M#47 to 10G
Range completed.
Reserving M#47 to 1T and don't mind the title... (185 has been done to 10T by Ernst). Luigi Last fiddled with by ET_ on 20121002 at 17:13 Reason: Raising the top... 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Is CEMPLLA 1.5 "the only software in the world capable of discovering" something? Not really.  CRGreathouse  Number Theory Discussion Group  51  20181216 21:55 
Official "World cup 2014/2018" teat  LaurV  Hobbies  74  20180711 19:33 
Problem E7 of Richard Guy's "Unsolved problems in number theory"  Batalov  Computer Science & Computational Number Theory  40  20130316 09:19 
Is the USA the "new" peacekeeper of the world??  outlnder  Soap Box  20  20050203 09:30 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 