mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-01-02, 19:41   #1
Hermes
 
Hermes's Avatar
 
Oct 2008

52 Posts
Default SIQS implemantation... help needed :(

Hi guys

I've implemented a small version of the SIQS sieve some time ago.

now, after some changes I discovered that when growing the digits size of the number to be factorized, even if I can collect enough relations
(about 1.2 times the factor base size) i'm not able to factor it since that, after the linear algebra stage all the linear combination found
of smooth numbers for which holds:

x^2 = y^2 mod n

are of the form

x = +- y mod n

so them can't give any factor of n.

note that this behaviour is not sistematic, but it seems to happens more frequently by the growing of the number to be factorized.

Since I made some check, I have a little fear that the trouble is that my sieve stage is not really good...
infact if i try to factor:

25626911509016950901475527595812441191940963052854598209

my siqs implementation uses a FB_size of about 3500 primes in the sieve space [-320k; +320k]

I can collect about 4.200 smooth numbers by using 3950 polynomials (with several changes of the 'a' value)
so I can collect about 1.1 smooth numbers per-polynomial.

and can't find any factor!

Can Someone suggest me some checks that I may perform?

reallly thanks.

/Hermes

Last fiddled with by Hermes on 2009-01-02 at 19:59
Hermes is offline   Reply With Quote
Old 2009-01-03, 02:56   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

My usual sequence of debugging checks:

- start at the square root. Verify that all the powers of all primes are even. If yes, then probably your linear algebra is okay. If no, whatever is going on may have to do with your mapping of relations to matrix columns

- if the problem does not happen all the time, look for relations that may be bad somehow, i.e. the sieve value does not equal the product of the factors
jasonp is offline   Reply With Quote
Old 2009-01-03, 03:37   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by jasonp View Post
My usual sequence of debugging checks:

- start at the square root. Verify that all the powers of all primes are even. If yes, then probably your linear algebra is okay. If no, whatever is going on may have to do with your mapping of relations to matrix columns

- if the problem does not happen all the time, look for relations that may be bad somehow, i.e. the sieve value does not equal the product of the factors
Check for duplicate relations. They lead to a trivial dependency.
R.D. Silverman is offline   Reply With Quote
Old 2009-01-03, 13:30   #4
Hermes
 
Hermes's Avatar
 
Oct 2008

52 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Check for duplicate relations. They lead to a trivial dependency.
After some checks i found that my siqs finds a lots of duplicate values of Q(t).

all of them are of the form Q(t1) = Q(t2), where t1 != t2.

for example:

Code:
[info] Found congruence: [R1733,R4079,]
SmoothN:  t=46301 | 1 * -1^1 * 5^2 * 19^1 * 67^1 * 79^1 * 1009^1 * 1033^1 * 1039^1 * 1051^1 * 1283^1 * 1367^1 * 1871^1 * 2207^1 * 3929^1 * 3931^1 * 9613^1 * 18229^1 * 19447^1 * 21523^1 | 
  |-> Q(46301) = -23476796006856163782154327960562329776058468371263977025 | a = 30556163745815338145843 | b = 51546277647491137453284185

SmoothN: t=33381= | 1 * -1^1 * 5^2 * 19^1 * 67^1 * 79^1 * 1009^1 * 1033^1 * 1039^1 * 1051^1 * 1283^1 * 1367^1 * 1871^1 * 2207^1 * 3929^1 * 3931^1 * 9613^1 * 18229^1 * 19447^1 * 21523^1 | 
  |-> Q(33381) = -23476796006856163782154327960562329776058468371263977025 | a = 44560079788324627958591 | b = -21132808171577296941765243

[eureka] Combo Found:  | 1 * -1^2 * 5^4 * 19^2 * 67^2 * 79^2 * 1009^2 * 1033^2 * 1039^2 * 1051^2 * 1283^2 * 1367^2 * 1871^2 * 2207^2 * 3929^2 * 3931^2 * 9613^2 * 18229^2 * 19447^2 * 21523^2 |
this is correct since the 'a' and the 'b' params in:

Q(t) = ( at + b )^2 - N

are different in Q(t1) and Q(t2).

Since i use the graycode approach to generate the 'b' param, once that the 'a' param is generated, the problem seems to be on the 'a' param generation itself.

actually, since I've no found any algorithm that explains how to exactly compute 'a',
I just try to minimize the difference beetween 'a' and sqrt(2*N)/M, as explained in the Contini thesis.
Then, when all possibles 'b' values are generated with a given 'a', I update the 'a' value by change one prime factor of 'a'.

each 'a' value is generated once, but seems that my approach is too poor and causes a lots of not-uniques Q(t).

Unfortunately I've no idea how to improve my 'a' generation strategy.

can someone suggest me a better approach to generate the 'a' param? :)

really thanks.

/Hermes.
Hermes is offline   Reply With Quote
Old 2009-01-03, 16:40   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

Coming up with a scheme to generate 'a' values, where each batch of factors is close to the optimal 'a' and doesn't repeat previous choices, was much harder than I anticipated, especially if the method is supposed to work for any size input. If you have the msieve source, you can look in mpqs/poly.c (function poly_init) to see how that code solves the problem. The postprocessing still filters out duplicates, but I've never seen the library generate duplicate QS relations.

Basically the msieve source picks the anticipated size of each factor up front, then randomly chooses all factors but the last, then chooses the last to get as close as possible to the optimal 'a'. Other choices include iterating through all choices of k primes out of n possible (google 'NEXKSB' for a very elegant combinatorial algorithm that does that), and Percival's scheme of choosing most factors only rarely but making the last one an increasing sequence of primes just above the factor base limit.

Last fiddled with by jasonp on 2009-01-03 at 16:45
jasonp is offline   Reply With Quote
Old 2009-01-04, 17:57   #6
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32×11 Posts
Default

One strategy is to split the factors in two parts (say one with even one with odd index). I think it is called Carrier Wagstraff method. I read it in http://www.google.de/url?sa=t&source...q5f-H4EirKy1Yg
or search for kechlibar quardratic sieve in google.

Then some correctors are defined, which are a small product of the first group. Depending on the size you can choose 2 or 3 for it.
Then choose factors from the other group, find the corrector to achieve a 'a' in the near of the desired value. delete the corrector.
Choose the next set of factor from the other group without using the ones we had before. i'm not sure if we can always use new once, but you can force that they are different at many positions.

The factor should not be to small, since this causes doubles.
Think of a 2 in the a, which is an every second relation as well.

How are your a's for duplicate rows?

Last fiddled with by ThiloHarich on 2009-01-04 at 17:59
ThiloHarich is offline   Reply With Quote
Old 2009-01-04, 19:12   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110011102 Posts
Default

I don't understand your question; while duplicates are possible the way msieve generates 'a' values, I've never seen it happen. Even a pool of 40-100 factor base primes is enough to generate all the 'a' values required.
jasonp is offline   Reply With Quote
Old 2009-01-05, 08:08   #8
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

1438 Posts
Default

I had the problem as well, but i choose the factors of the a's to be rather small, since this gives more you more b's. But then you might get the problem of duplicates.
ThiloHarich is offline   Reply With Quote
Old 2009-01-05, 14:01   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,371 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
I had the problem as well, but i choose the factors of the a's to be rather small, since this gives more you more b's. But then you might get the problem of duplicates.
What is small? In my experience, choosing primes > 1000 works fine. Like msieve, I've never seen YAFU generate duplicates with that choice, and still get plenty of b's per a. Profiling shows that the 'a' poly initialization only takes a fraction of a percent, and any size job only typically requires a few hundred 'a' polys.
bsquared is offline   Reply With Quote
Old 2009-01-05, 15:56   #10
Hermes
 
Hermes's Avatar
 
Oct 2008

110012 Posts
Default

ok...
i updated my bad version of siqs

now the sieve can easily be able to change the 'a' generator...

to make some tests I've implemented the simpler algorithm... actually it generates a good 'a' values with a reasonable frequency ( about 80% of the generated values have a distance below the 2% from the ideal bound ).

it seems to works better now... so I will made some tests...

Just a question, can I use a multiplier of n, computed with the knuth schroeppel func
tion, as described in the Silverman paper for the MPQS?

would it be faster? :)

/hermes
Hermes is offline   Reply With Quote
Old 2009-01-05, 16:08   #11
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,371 Posts
Default

Quote:
Originally Posted by Hermes View Post
Just a question, can I use a multiplier of n, computed with the knuth schroeppel func
tion, as described in the Silverman paper for the MPQS?

would it be faster? :)

/hermes
Yes, just be sure to choose the multiplier before you compute your factor base. It will most likely be noticably faster.
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SIQS on GPU cgy606 Factoring 1 2016-10-21 13:37
SIQS problems henryzz Factoring 2 2013-08-26 23:02
SIQS Problem patrickkonsor Factoring 3 2008-10-20 12:03
partial relations in SIQS ThiloHarich Factoring 6 2007-12-03 18:48
Simple Idea for SIQS ThiloHarich Factoring 5 2006-03-16 08:22

All times are UTC. The time now is 04:19.

Thu Mar 4 04:19:16 UTC 2021 up 91 days, 30 mins, 1 user, load averages: 2.29, 1.86, 1.68

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