mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2017-06-24, 12:41   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

52·13 Posts
Default 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
bhelmes is online now   Reply With Quote
Old 2017-06-24, 19:49   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

223228 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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?
Batalov is offline   Reply With Quote
Old 2017-06-25, 03:38   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111011000012 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-06-25, 03:44   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

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
CRGreathouse is offline   Reply With Quote
Old 2017-06-25, 20:02   #5
bhelmes
 
bhelmes's Avatar
 
Mar 2016

52·13 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
bhelmes is online now   Reply With Quote
Old 2017-06-25, 20:47   #6
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

22·227 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2017-06-25, 22:25   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

176116 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-06-26, 02:20   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

90810 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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).
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New factorization method henryzz Miscellaneous Math 4 2017-04-13 12:41
Improving website speed Unregistered Information & Answers 1 2011-04-02 02:17
Fast factorization method or crankery? 10metreh Factoring 6 2010-04-08 11:51
Improving Sieving by 18%. cipher Prime Sierpinski Project 10 2009-07-01 13:34
Improving the RAM allocation for Prime 95 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.