improving factorization method

[bhelmes]

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

[Batalov]

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?

[CRGreathouse]

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.

[CRGreathouse]

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.

[bhelmes]

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

[danaj]

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.

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.

[CRGreathouse]

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.

[danaj]

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).