mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2008-10-29, 04:53   #1
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

64158 Posts
Default 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.
bsquared is offline   Reply With Quote
Old 2008-10-29, 11:04   #2
Andi_HB
 
Andi_HB's Avatar
 
Mar 2007
Germany

10816 Posts
Default 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,
Is this a bug in the Programm?
Greeting from Germany
Andi_HB is offline   Reply With Quote
Old 2008-10-29, 11:51   #3
VolMike
 
VolMike's Avatar
 
Jun 2007
Moscow,Russia

7·19 Posts
Default

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?
VolMike is offline   Reply With Quote
Old 2008-10-29, 13:17   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default

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 :)
jasonp is offline   Reply With Quote
Old 2008-10-29, 13:26   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

Quote:
Originally Posted by VolMike View Post
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 is offline   Reply With Quote
Old 2008-10-29, 13:43   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2008-10-29, 15:12   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default

Quote:
Originally Posted by bsquared View Post
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 :)
jasonp is offline   Reply With Quote
Old 2008-10-29, 18:03   #8
VolMike
 
VolMike's Avatar
 
Jun 2007
Moscow,Russia

13310 Posts
Default

Quote:
Originally Posted by bsquared View Post
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 :)
VolMike is offline   Reply With Quote
Old 2008-10-29, 18:11   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

Quote:
Originally Posted by VolMike View Post
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 is offline   Reply With Quote
Old 2008-10-30, 03:51   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

Quote:
Originally Posted by jasonp View Post
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
bsquared is offline   Reply With Quote
Old 2008-11-08, 09:32   #11
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default 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.
10metreh is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Running YAFU via Aliqueit doesn't find yafu.ini EdH YAFU 8 2018-03-14 17:22
YAFU-1.34 bsquared YAFU 119 2015-11-05 16:24
Yafu bug. storflyt32 YAFU 2 2015-06-29 05:19
yafu-1.33 bsquared YAFU 12 2012-11-08 04:12
yafu-1.32.1 bsquared YAFU 21 2012-09-04 19:44

All times are UTC. The time now is 22:21.

Mon Nov 23 22:21:50 UTC 2020 up 74 days, 19:32, 4 users, load averages: 2.16, 2.54, 2.61

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.