20081029, 04:53  #1 
"Ben"
Feb 2007
3,271 Posts 
Yafu
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. 
20081029, 11:04  #2 
Mar 2007
Germany
2^{3}×3×11 Posts 
Yafu 1.0.1
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: Code:
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, Greeting from Germany 
20081029, 11:51  #3 
Jun 2007
Moscow,Russia
7×19 Posts 
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? 
20081029, 13:17  #4 
Tribal Bullet
Oct 2004
3,527 Posts 
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 :) 
20081029, 13:26  #5  
"Ben"
Feb 2007
3,271 Posts 
Quote:
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. 

20081029, 13:43  #6 
"Ben"
Feb 2007
110011000111_{2} Posts 
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. 
20081029, 15:12  #7 
Tribal Bullet
Oct 2004
3,527 Posts 
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 :)

20081029, 18:03  #8 
Jun 2007
Moscow,Russia
7·19 Posts 
The only thing of using such inputes to see if program is able to catch different kind of exceptions smoothly :)

20081029, 18:11  #9 
"Ben"
Feb 2007
3,271 Posts 

20081030, 03:51  #10  
"Ben"
Feb 2007
3,271 Posts 
Quote:
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. Last fiddled with by bsquared on 20081030 at 03:54 

20081108, 09:32  #11 
Nov 2008
2×3^{3}×43 Posts 
Rho method bug
I think I have found a bug in yafu:
When I execute "factor(2^701)", 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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Running YAFU via Aliqueit doesn't find yafu.ini  EdH  YAFU  8  20180314 17:22 
YAFU1.34  bsquared  YAFU  119  20151105 16:24 
Yafu bug.  storflyt32  YAFU  2  20150629 05:19 
yafu1.33  bsquared  YAFU  12  20121108 04:12 
yafu1.32.1  bsquared  YAFU  21  20120904 19:44 