20170624, 12:41  #1 
Mar 2016
5^{2}·13 Posts 
improving factorization method
A peaceful day for all,
i try to improve some factorization algorithm and i am capable to factorize 40 digits numbers which is not bad. i do some matrix operations and some kind of pollard rho. Is it useful to save some quadrats below a limit in order to use them by a collision of two quadrats. I get the quadrat numbers by the matrix operations for free, but i could not calculate the probability of a collision. Besides i use 8 cores and i am afraid that the saving and lookup of quadrats could decrease the speed. Some nice greetings from the primes Bernhard 
20170624, 19:49  #2  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
22322_{8} Posts 
Quote:
Do a software implementation for three methods that follow: 1. At the initialization of the program, precompute all squares for 1<= x <= 10^9 and store them in memory: in an array, in a hash, in any other structure. 2. Create a file (it could be a database table, or an otherwise indexed file) with all squares for 1<= x <= 10^9, and at run time check if a number is a square by looking up the file. 3. Implement issquare(uint64_t x) by borrowing from Pari/gp source, or by writing your own, or even simplemindedly as: { const char b[16]={1,1,0,0,1,0,0,0,0,1}; return b[x&15] && (floor(sqrt(x))*floor(sqrt(x))==x); } (have faith in the compiler to do floor(sqrt(x)) just once) Time them and use the fastest of the three. Which of the three methods will win? 

20170625, 03:38  #3  
Aug 2006
1011101100001_{2} Posts 
Quote:


20170625, 03:44  #4 
Aug 2006
3^{2}×5×7×19 Posts 
There's also
https://cr.yp.to/papers/powers.pdf (see section 10) if you're really into speed. Edit: Also section 22, which you should likewise use if you're looking for speed, as well as section 21, which has an interesting variant. Last fiddled with by CRGreathouse on 20170625 at 07:07 
20170625, 20:02  #5  
Mar 2016
5^{2}·13 Posts 
Quote:
krypted the file with the saved quadratic numbers, dekrypt by runtime and change allways the key for security reasons By the way, i use gmp as language, i am not familiar with pari. Is there a reasonable value for the noncyclic pre part of the pollardrho algorithm considering 40 digits number (before the cycle starts) I use 1.000.000 squarings which use only 10 seconds calculation time. Greetings from the primes Bernhard 

20170625, 20:47  #6 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2^{2}·227 Posts 
I suspect we can improve on Pari's native int solution using a simple Bloom filter. It was definitely faster than the Cohen/Pari solution when I last checked. Important for native size SQUFOF and a couple other applications. E.g.
Code:
static int is_perfect_square(uint64_t n) { uint64_t m; m = n & 127; if ((m*0x8bc40d7d) & (m*0xa1e2f5d1) & 0x14020a) return 0; /* This cuts out another 80%: */ m = n % 63; if ((m*0x3d491df7) & (m*0xc824a9f9) & 0x10f14008) return 0; /* m = n % 25; if ((m*0x1929fc1b) & (m*0x4c9ea3b2) & 0x51001005) return 0; */ m = isqrt(n); return m*m == n; } For nonnative size, I just use mpz_perfect_square_p. It does a single 32byte table lookup to remove 82% of inputs, then 4 more tests for small primes. They claim 99.62% overall rejection. I'm sure improvements to this would be interesting. Bloom filters would be one direction (see the fantastic post at http://mersenneforum.org/showpost.php?p=110896), or the Bernstein paper referenced. 
20170625, 22:25  #7  
Aug 2006
1761_{16} Posts 
Quote:


20170626, 02:20  #8  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
908_{10} Posts 
Quote:
For random inputs, it's up to what you're going to do next. It's really fast at pulling out small factors and has low overhead, but P1 and ECM are both quite useful as well. Again 10 seconds seems quite excessive but I could be not understanding what you're asking or you could have a much slower machine. Given 1000 random 40digit composites, factors of {2,3,5} removed first, in 1 second my PollardBrent with 100k rounds has found a factor of all but 14, and all but 11 in 8 seconds with 1M rounds. The more efficent combination is less Rho followed by P1 and ECM (this will find more factors in less overall time). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New factorization method  henryzz  Miscellaneous Math  4  20170413 12:41 
Improving website speed  Unregistered  Information & Answers  1  20110402 02:17 
Fast factorization method or crankery?  10metreh  Factoring  6  20100408 11:51 
Improving Sieving by 18%.  cipher  Prime Sierpinski Project  10  20090701 13:34 
Improving the RAM allocation for Prime 95  Matthias C. Noc  Software  3  20040212 19:34 