mersenneforum.org > YAFU Yafu
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2008-10-29, 04:53 #1 bsquared     "Ben" Feb 2007 23×419 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.
 2008-10-29, 11:04 #2 Andi_HB     Mar 2007 Germany 23·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 didnt get a result. The same Number was factoring with Msieve1.38 without Problems. I used the win32 bin Version from Yafu Thats 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, Is this a bug in the Programm? Greeting from Germany
 2008-10-29, 11:51 #3 VolMike     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?
 2008-10-29, 13:17 #4 jasonp Tribal Bullet     Oct 2004 22·883 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 :)
2008-10-29, 13:26   #5
bsquared

"Ben"
Feb 2007

23×419 Posts

Quote:
 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.

 2008-10-29, 13:43 #6 bsquared     "Ben" Feb 2007 1101000110002 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.
2008-10-29, 15:12   #7
jasonp
Tribal Bullet

Oct 2004

22·883 Posts

Quote:
 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 :)

2008-10-29, 18:03   #8
VolMike

Jun 2007
Moscow,Russia

8516 Posts

Quote:
 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 :)

2008-10-29, 18:11   #9
bsquared

"Ben"
Feb 2007

23×419 Posts

Quote:
 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...

2008-10-30, 03:51   #10
bsquared

"Ben"
Feb 2007

23·419 Posts

Quote:
 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.

Last fiddled with by bsquared on 2008-10-30 at 03:54

 2008-11-08, 09:32 #11 10metreh     Nov 2008 2×33×43 Posts Rho method bug 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post EdH YAFU 8 2018-03-14 17:22 bsquared YAFU 119 2015-11-05 16:24 storflyt32 YAFU 2 2015-06-29 05:19 bsquared YAFU 12 2012-11-08 04:12 bsquared YAFU 21 2012-09-04 19:44

All times are UTC. The time now is 17:55.

Fri Dec 4 17:55:06 UTC 2020 up 1 day, 14:06, 0 users, load averages: 1.38, 1.64, 1.72