Yafu

[bsquared]

Just curious, has anyone had a chance to confirm/deny the timings of my SIQS relative to msieve? I'm mostly interested in the performance on 64bit linux systems, core2 or otherwise.

p.s. there is a new version on my page, with a few bugfixes and a couple percent improvement over v1.0's SIQS timings for large factorizations.

Thanks,
- ben.

[Andi_HB]

Hi @ all!
I have tested the new Version Yafu 1.0.1.
It works fine with small numbers - but now I tried a 83 digit Number only for Testing and Yafu didn`t get a result.
The same Number was factoring with Msieve1.38 without Problems.
I used the win32 bin Version from Yafu
That`s the output from Yafu:

Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, starting SIQS on c83: 47400378883230338232775581390792470724641097776632053645187932911870219271898236101
Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, n = 83 digits, 277 bits
Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, ==== sieve params ====
Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, factor base: 50538 primes (max prime = 1318211)
Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, large prime cutoff: 125230045 (95 * pmax)
Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, sieve interval: 14 blocks of size 32768
Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, polynomial A has ~ 11 factors
Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, using multiplier of 5
Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, using small prime variation, with initial value 8
Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, bucket sieving beyond prime 49157
Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, trial factoring cutoff at 109 bits
Wed Oct 29 2008 10:33:23 v1.0.1 @ LAPPIE, ==== sieving started ====
Wed Oct 29 2008 10:54:41 v1.0.1 @ LAPPIE, sieve time = 424.1220, relation time = 154.4950, poly_time = 679.4220, reload_time = 0.0000
Wed Oct 29 2008 10:54:41 v1.0.1 @ LAPPIE, 50600 relations found: 25511 full + 25089 from 269700 partial, using 238090 polys
Wed Oct 29 2008 10:54:41 v1.0.1 @ LAPPIE, 1444563 relations checked for completeness
Wed Oct 29 2008 10:55:34 v1.0.1 @ LAPPIE, Lanczos elapsed time = 39.3140 seconds.
Wed Oct 29 2008 10:55:34 v1.0.1 @ LAPPIE, Sqrt elapsed time = 5.3270 seconds.
Wed Oct 29 2008 10:55:34 v1.0.1 @ LAPPIE, Total elapsed time = 1331.7420 seconds.
Wed Oct 29 2008 10:55:34 v1.0.1 @ LAPPIE, 
Wed Oct 29 2008 10:55:34 v1.0.1 @ LAPPIE,

Is this a bug in the Programm?
Greeting from Germany

[VolMike]

Heh, nice program with sence of humour.
When typing: rsa(123498768976896897689976968098709879087907890789078097812349876769876891234213412341234123421341234)
it replies:
"bitlength to small"
:)

BTW: What about primality proof algorithm including? Is it difficult to implement fast method of determine primality testing?

[jasonp]

People occaisionally ask for some kind of primality proving algorithm; implementations of these are much more unusual than implementations of factoring. The algorithms are fairly involved, which is why few have bothered. Primo is the implementation of choice (it uses elliptic curve primality proving), and also ppsiqs has APRCL code. The source for the latter is available.

Ben, congratulations on a major QS speedup. The performance increase is so large that there's no point in my trying to catch up :)

[bsquared]

Originally Posted by VolMike

Heh, nice program with sence of humour.
When typing: rsa(123498768976896897689976968098709879087907890789078097812349876769876891234213412341234123421341234)
it replies:
"bitlength to small"
:)

BTW: What about primality proof algorithm including? Is it difficult to implement fast method of determine primality testing?

That is funny it worked out that way, but it's regretably unintentional. The argument to rsa should be the bitlength of the rsa output, so your input is an interesting case of either bad documentation or extreme paranoia.

The input gets cast to an int, which is a large negative number in this case, hence the output. I've built in checks on the input size now, thanks for your test.

As far as primalty proofs, I just haven't delved much into that area. It may be sacriligious to say on this forum but large primes just don't excite me as much as factoring, so that's where I've spent my time/energy. Yafu does have an LLT implementation, because it's so easy to do, but it is extremely slow for large inputs (I have only N^2 multiplication).

Thanks for your interest,
- ben.

[bsquared]

This was a bug in the program, but I thought I fixed it. I haven't been able to reproduce it here using 1.0.1. If you still have the relations for that job (you haven't tried to factor anything else by SIQS since then), then maybe try it again. The particular version of msieve I'm using sometimes only finds 10 or fewer dependencies in the matrix, and when that happens I've seen it only find one factor before. Maybe here it just didn't find any.

I'll continue to test large inputs using the windows code to see if I can also see the problem.

Thanks for your interest and feedback,
- ben.

[jasonp]

Originally Posted by bsquared

It may be sacriligious to say on this forum but large primes just don't excite me as much as factoring, so that's where I've spent my time/energy.

I first got interested in computational number theory because of LL tests and large primes, but I feel exactly the same way. We should be fine as long as the sacrilege is limited to the factoring subforum :)

[VolMike]

Originally Posted by bsquared

That is funny it worked out that way, but it's regretably unintentional. The argument to rsa should be the bitlength of the rsa output, so your input is an interesting case of either bad documentation or extreme paranoia.

The only thing of using such inputes -to see if program is able to catch different kind of exceptions smoothly :)

[bsquared]

Originally Posted by VolMike

The only thing of using such inputes -to see if program is able to catch different kind of exceptions smoothly :)

Exactly. And I'm very grateful for any feedback of this kind. I wouldn't be surprised to see a lot more along these lines...

[bsquared]

Originally Posted by jasonp

Ben, congratulations on a major QS speedup. The performance increase is so large that there's no point in my trying to catch up :)

Thanks for that comment :) Definately a case of standing on the shoulders of giants, though. Much of the code is based on or otherwise inspired by your work or Contini's work. I don't know if you were the first to come up with bucket sieving for large primes but that is the trick that makes yafu so fast. One slight variant I added was "very large prime" bucket sieving. Basically making a distinction between primes larger than the blocksize and primes larger than the entire sieve interval. Many are in the latter category for large jobs, and I represent those with a single 32bit element (a 16 bit block offset and a 16 bit factor base index), half the size of a standard bucket.

And by the way, msieve still rules on opterons. I haven't figured out yet why I get such a performance hit between core2 and amd.

Anyway, as you say, happy factoring!

- ben.

[10metreh]

I think I have found a bug in yafu:

When I execute "factor(2^70-1)", the factors come out as follows:

prime:
[3 1]
[11 1]
[31 1]
[43 1]
[71 1]
[127 1]
[281 1]
prp:
[5 1]
composite:
[2002290899 1]

What appeared as 5 x 2002290899 should have been 86171 x 122921.
The bug appears to be in the rho method.

P.S. It would be good to add algebraic factors to yafu.