mersenneforum.org improving factorization method
 Register FAQ Search Today's Posts Mark Forums Read

 2017-06-24, 12:41 #1 bhelmes     Mar 2016 52·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
2017-06-24, 19:49   #2
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

223228 Posts

Quote:
 Originally Posted by bhelmes Is it useful to save some quadrats below a limit in order to use them by a collision of two quadrats.
You describe it as a technical problem, so why don't you try it as a technical problem?

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?

2017-06-25, 03:38   #3
CRGreathouse

Aug 2006

10111011000012 Posts

Quote:
 Originally Posted by Batalov 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)
PARI does a good job here: nice clean code which does the obvious thing, just like your sample code though a few more residue classes. (Also it has cleanup for sqrt misbehaving on 64-bit architectures.) Admittedly, they don't trust the compiler as you advise.

 2017-06-25, 03:44 #4 CRGreathouse     Aug 2006 32×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 2017-06-25 at 07:07
2017-06-25, 20:02   #5
bhelmes

Mar 2016

52·13 Posts

Quote:
 Originally Posted by Batalov You describe it as a technical problem, so why don't you try it as a technical problem? Time them and use the fastest of the three. Which of the three methods will win?
Thank you for the hint, i thought for really tough programming i should first
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 pollard-rho 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

 2017-06-25, 20:47 #6 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 22·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; } where isqrt is a proper integer sqrt (e.g. C's sqrt but ensuring overflow and rounding is done correctly, or one of many other methods), and it's up to your testing on your platform to decide if the third filter is worth using. For non-native size, I just use mpz_perfect_square_p. It does a single 32-byte 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.
2017-06-25, 22:25   #7
CRGreathouse

Aug 2006

176116 Posts

Quote:
 Originally Posted by bhelmes 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 pollard-rho algorithm considering 40 digits number (before the cycle starts) I use 1.000.000 squarings which use only 10 seconds calculation time.
PARI is written in C, much of it using GMP. If you compile the GMP version of PARI and you check if a number larger than one machine word is a square, it does the usual modular checks then calls the GMP version of sqrtremi to find the square root.

2017-06-26, 02:20   #8
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

90810 Posts

Quote:
 Originally Posted by bhelmes Is there a reasonable value for the noncyclic pre part of the pollard-rho algorithm considering 40 digits number (before the cycle starts) I use 1.000.000 squarings which use only 10 seconds calculation time.
Could you clarify this? For a 133-bit (high 40 digit) random semiprime with approximately equal-size factors, it takes my Macbook about 10 seconds for 20M rounds where each round is 3 squares. Using Brent's improvements gets to ~42M rounds. Neither is enough to typically find one of the two 20-digit factors.

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 P-1 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 40-digit composites, factors of {2,3,5} removed first, in 1 second my Pollard-Brent 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 P-1 and ECM (this will find more factors in less overall time).

 Similar Threads Thread Thread Starter Forum Replies Last Post henryzz Miscellaneous Math 4 2017-04-13 12:41 Unregistered Information & Answers 1 2011-04-02 02:17 10metreh Factoring 6 2010-04-08 11:51 cipher Prime Sierpinski Project 10 2009-07-01 13:34 Matthias C. Noc Software 3 2004-02-12 19:34

All times are UTC. The time now is 08:23.

Tue May 11 08:23:54 UTC 2021 up 33 days, 3:04, 1 user, load averages: 2.12, 1.87, 1.62