20200331, 15:42  #23  
"Tilman Neumann"
Jan 2016
Germany
11·43 Posts 
Quote:
Sorry, didn't see this before... True, the paper tells us that they use the same sieve as for factoring, and that sieving is the most expensive step in the class group computations. I also wouldn't doubt your estimated performance comparison. Nonetheless, I think that Kleinjungs SIQS is pretty interesting because it takes such a different approach, resulting in a very different parametrization (very small sieve array etc.). And a factor of 4.88 does not mean much. Knowing that they do have a pretty good GNFS, maybe it was just a kind of toy and the implementation not that highly optimized. 

20200331, 19:42  #24  
"Ben"
Feb 2007
6772_{8} Posts 
Quote:
If you or anyone else is motivated enough to implement the algorithm I would love to see it. Or maybe someone can request the code from Thorsten and then make the changes necessary for integer factorization problems? 

20200401, 12:58  #25  
"Tilman Neumann"
Jan 2016
Germany
11·43 Posts 
Quote:
Agreed. I meant that in the context of his usual standards, but "not fully optimized" would have been better wording. Quote:
Not me at the moment... Asking for the code wouldn't help me either because I'ld rather be interested in a Java implementation. (as strange as that might seem to most of you ;) 

20200507, 13:52  #26 
"Ben"
Feb 2007
110111111010_{2} Posts 
I found this thesis comparing Kleinjung's algorithm with traditional SIQS:
https://prism.ucalgary.ca/bitstream/...=2&isAllowed=y The reexplanation of the algorithm is very helpful. Lots of comparisons are presented on up to 480bit discriminants. One thing it appears to be lacking, however, is a comparison of a welltuned traditional siqs with a welltuned Kleinjung approach. Of course, traditional siqs will be very slow in comparison with Kleinjung when the parameters are the same (e.g., block size 2048). And vice versa (Kleinjung does not do well with large sieve area). I am most curious to see how they compare when each are tuned to their respective strengths. Still, it is a very nice thesis report. I can see better now that Kleinjung's algorithm is compatible with the rest of siqs factorization (e.g., polynomial generation, filtering and matrix steps), which might ease integration of the new approach with existing implementations. 
20200507, 16:04  #27  
"Tilman Neumann"
Jan 2016
Germany
11·43 Posts 
Quote:
Quite a lengthy read, but currently being on rehab from an abscess op, thats just the right thing for me and I will certainly enjoy it. Thanks for posting! 

20200520, 17:00  #28 
Tribal Bullet
Oct 2004
3·1,181 Posts 
Colin Percival, in a blog post around ~2005, called this method the subset sum self initializing quadratic sieve (SSSIQS). I actually implemented most of it, at least enough to test the performance; the good news is that for moderately large QS problems one can indeed get a 2x speedup in the time taken to sieve through a given number of sieve locations. Put another way, if you compare Msieve's default choice of sieve size, times number of SIQS polynomials, and then reparametrize so that instead you use much larger SIQS batches of primes and much fewer sieve locations per polynomial, such that the number of sieve locations is constant, then completing the sieve problem takes half the time.
Unfortunately, the actual relation discovery rate dropped by a factor of 4. Maybe that's because I messed up something, or maybe it's because of the asymptotic smoothness properties of the sieve locations, but it was really surprising that it wasn't a net win. 
20200521, 15:42  #29 
Romulan Interpreter
"name field"
Jun 2011
Thailand
97·101 Posts 
To put it in a way we could understand it, this would just give you 5 or 6 digits more for the crossover between SIQS and GNFS, if I read it right?
(as the effort/factorization time doubles with every 56 digits, about) Last fiddled with by LaurV on 20200521 at 15:48 
20200521, 16:49  #30 
Tribal Bullet
Oct 2004
3·1,181 Posts 
Percival predicted a factor of two speedup from the method; maybe the factor is larger if one uses a much larger factor base to improve the relation yield and use the subset sum technique to avoid the sieving time increasing as a result. Maybe the factor would be larger if you used the method on problems for which SIQS is illsuited in the first place. The choice of parameters has a huge effect on the total time for the sieving, it's easy to see a factor of two change either way.
But yes, this only buys a few digits in the crossover between SIQS and GNFS. 2005 was a different time, there were several good implementations of the quadratic sieve but very little publicly available for nontrivial size NFS 
20200521, 17:20  #31 
Romulan Interpreter
"name field"
Jun 2011
Thailand
97×101 Posts 
Well, then, ok, 7 digits...
So, I still can't beat Ben's record... Loops and screws, remember? hihi. It seems I won't be able to check that box this lifetime 
20200521, 18:26  #32  
"Ben"
Feb 2007
2×1,789 Posts 
Quote:
It is hugely inefficient and clumsy but you can loop and if! Even nested loops/ifs, if you are patient enough to craft such a thing: Code:
./yafu "for(x=3;x<100;x=x+1;for(y=2;y<x;y=y+1;if(isprime(x^y+y^x);x^y+y^x)))" 17 593 32993 2097593 59604644783353249 43143988327398957279342419750374600193 8589935681 5052785737795758503064406447721934417290878968063369478337 4318114567396436564035293097707729426477458833 523347633027360537213687137 814539297859635326656252304265822609649892589675472598580095801187688932052096060144958129 205688069665150755269371147819668813122841983204711281293004769 7259701736680389461922586102342375953169154793471358981661239413987142371528493467259545421437269088935158394128249 3329896365316142756322307042065269797678257903507506764421250291562312417 14612087592038378751152858509524512533536096028044190178822935218486730194880516808459166772134240378240755073828170296740373082348622309614668344831750401 123696767198741648186287940563721003128015158572134981161748692560225922426827257262789498753729852662122870454448694253249972402126255218031127222474177 Code:
>> sum=0; >> forprime(p=2;100;sum=sum+p*p) 4 13 38 87 208 377 666 1027 1556 2397 3358 4727 6408 8257 10466 13275 16756 20477 24966 30007 35336 41577 48466 56387 65796 >> Code:
>> input=randb(200); >> sum_distinct=0; >> forfactors(factor(input);sum_distinct=sum_distinct+_f;) fac: factoring 784170029379726309723236630974985183483957194272594097782676 fac: using pretesting plan: normal fac: using specified qs/gnfs crossover of 93 digits fac: using specified qs/snfs crossover of 75 digits div: primes less than 10000 fmt: 1000000 iterations rho: x^2 + 3, starting 200 iterations on C59 Total factoring time = 0.0406 seconds ***factors found*** P1 = 2 P1 = 2 P2 = 13 P8 = 46630757 P51 = 323395840918624684084681503147649779523761535543109 >> print(sum_distinct); 323395840918624684084681503147649779523761582173881 >> I don't think I ever even published a help document on how to use it. Here is what I remember off the top of my head: for(start_expression;stop_expression;statement) Not sure if "statement" can be more than one line. But it can have an assignment in it or another "for" forprime(start_expression; end_condition; statement) end_condition checks the value of the variable defined in start_expression forfactors(factor_statement; statement) factor_statement must be of the form: factor(something) within your "statement", the variable "_f" refers to each factor in turn and "_fpow" its corresponding power. if(condition_statement; statement; else_statement) if the condition statement evaluates to nonzero, then execute statement and optionally execute else_statement if zero (you can omit else_statement if desired) I think that post had a script with these examples in it. Not sure if anyone has used it since 

20200521, 18:29  #33  
"Ben"
Feb 2007
2×1,789 Posts 
Quote:
Code:
./yafu "for(input=840; input>1; print(input); forfactors(sum=1, factor(input); t=1;, for(i=1; lte(i,_fpow); i=i+1; t=t+_f^i;), sum=sum*t;), input=suminput;)" silent Last fiddled with by bsquared on 20200521 at 18:30 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Where do I send my PRP primes with large k?  Trilo  Riesel Prime Search  3  20130820 00:32 
48bit large primes!  jasonp  Msieve  24  20100601 19:14 
NFS with 5 and 6 large primes  jasonp  Factoring  4  20071204 18:32 
Why only three large primes  fivemack  Factoring  18  20070510 12:14 
What is the use of these large primes  Prime Monster  Lounge  34  20040610 18:12 