QS - lin. algebra phase - Page 2

Wacky · 2007-07-20, 13:20

Quote:

Originally Posted by SilverMan

The idea of removing lines with only one zero surprised me at first, but then i realized its absolutely logical

I hope that you meant "only one 1".

jasonp · 2007-07-20, 14:15

Quote:

Originally Posted by SilverMan

So i will be able to reduce the size of the matrix, that is great.

Im only a little bit confused with the "removing of columns". In my example i had two zero lines, so you mean i should also remove these and also two columns? And which ones?

I meant removing empty rows before doing the gauss elimination; if you have empty rows after gauss elimination, that means things are working :)

For very small examples like the above 4x5 case, preprocessing is less important, otherwise you run the risk of deleting the entire matrix. When the matrix gets to 50x50 or larger, you should expect to have to do some compressing.

SilverMan · 2007-07-20, 18:25

Quote:

Originally Posted by Wacky

I hope that you meant "only one 1".

Yes of course

sorry for that mistake.

jasong · 2007-07-22, 22:00

Off-topic: Am I the only one thinking,"OMG! Similar name, similar hobby?"

At least in my case, jasonp and I don't seem to cross paths all that much. (Not that I'd mind, it's just I'm sure he doesn't want to be confused with a poster who's a paranoid schizophrenic. :) )

SilverMan · 2007-08-05, 13:22

Hehe, no actually my name is not SilverMan, if thats what you had in mind. Its just my nickname over 10 years and i use it everywhere.

EDIT: FOUND THE ANSWER in another topic, sorry.

2007-09-18, 10:23

Hi Everybody,
I am working on the QS and my problem is that I find very often trivial solutions, especially if the number has only 2 factors. I read here http://www.nada.kth.se/~joel/qs.pdf, that we have a 50% chance of receiving trivial solutions (less if n is the product of more than two primes). Does exist any way or trick to find non-trivial solution?
P.S. My program use Gaussian elimination and compute GCD of n with the difference (or sum) of the two square roots (Wikipedia)

Please help!

R.D. Silverman · 2007-09-21, 11:46

Quote:

Originally Posted by Student

Hi Everybody,
I am working on the QS and my problem is that I find very often trivial solutions, especially if the number has only 2 factors. I read here http://www.nada.kth.se/~joel/qs.pdf, that we have a 50% chance of receiving trivial solutions (less if n is the product of more than two primes). Does exist any way or trick to find non-trivial solution?
P.S. My program use Gaussian elimination and compute GCD of n with the difference (or sum) of the two square roots (Wikipedia)

Please help!

If the composite has exactly 2 factors, then the probability of a
trivial solution is 1/2. If it has k factors, the chance is 1/2^(k-1).

If you frequently get trivial solutions, you should start by looking at
where these come from. My first guess would be from duplicate
relations in your matrix.

Peter Hackman · 2007-10-17, 08:56

Short introduction: I'm new here. I'm a former lecturer at Linköping University; took early retirement last year. Computational Number Theory is not my specialty (my field is Commutative Algebra)
but I prefer computing to bowling and bingo.

I recently worked up a fairly simple MPQS program. For reasons to be discussed in another thread I chose my a=q^2 by a random process
in a somewhat narrow interval about the ideal a= sqrt(2M)/N.
I was puzzled to sometimes get 100 relations and no non-trivial factors. It turned out that there were repeats. Rewriting my routine eliminated these
and the whole problem.

SilverMan · 2009-10-20, 20:47

Hello all,

sorry for digging up such an old thread, but i think it's better to continue in my own thread rather than starting a new one. A few months ago I found my old implementation of Quadratic Sieve on an old hard drive and after playing with it for a while I sadly realized that it's slower than i thought it was. This led me to the idea of reimplementing it all over again but this time better and more importantly - with optimizations of course. My goal is to implement a decent MPQS algorithm. At first i thought going for SIQS would be better, but this thread ( http://www.mersenneforum.org/showthread.php?t=10743 ) proved that maybe that's not the best idea. Better take small steps, one at a time :)

My first problem is in the sieving stage. For all primes in my factor base i have solved the modular quadratic equation using the Shanks-Tonelli algorithm. This gave me two solutions for each prime. But how can i compute the exact indexes into the array which i sieve? Currently in my old implementation of QS i first test the numbers in my interval for divisibility and when i find the first one that is divisible by the prime, i can compute the indexes and sieve effectively. But the searching consumes a lot of time and makes sieving by large primes extremely ineffective. Surely there must be a way how to avoid this!

This is just the first major problem i ran into while reimplementing QS and going through my code. There are many other topics that i'm interested in, but i know that it would be very stupid to ask questions on all of them. Instead i would be very grateful if someone could point me in the right directions - where should i look for answers and tips? I'm interested in papers on the problematic of MPQS and it's implementations, preferably as pdf's which i could download. I know the theory how QS/MPQS works, but i failed to find any good papers which are more specific.

Thanks for any advice or answer!

jasonp · 2009-10-20, 23:06

See the list of QS references in the Msieve readme for some good papers on getting started.

You problem boils down to moving an arithmetic progression r + k * p from the origin (k = 0) to some other point on the number line. You can do that with one division. Alternately, you can start at the origin and sieve positive k, then start again at the origin and sieve negative k; no moving the origin required.

SilverMan · 2009-10-22, 14:05

Thank you very much jasonp, i will definetly go through those papers.

Maybe i'm missing something, but i still don't understand your hint about "one division" (regarding the index in the sieved interval). So for example, if i try to factor N = 250 and i have the prime 13 in my factor base, i get 4 and 9 as the results of Shanks-Tonelli. I compute the interval values using the basic polynomial: (x + sqrt(N)) - N .

Now for example, the first field in my interval I is:
I[0]: 16 = 6 (meaning that 16^2 is 6 (mod 250))

Now what i need is to get the index in I where the first number divisible by 13 will be. The correct answer is I[1] (the second field, with 17^2 = 39 mod 250). Sorry if the answer to this question is in some of those papers, i will start reading the one by Contini today...

2007-08-05, 13:22	#16
SilverMan Jul 2007 10010₂ Posts	Hehe, no actually my name is not SilverMan, if thats what you had in mind. Its just my nickname over 10 years and i use it everywhere. EDIT: FOUND THE ANSWER in another topic, sorry. Last fiddled with by SilverMan on 2007-08-05 at 13:30

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial Algebra	R.D. Silverman	Other Mathematical Topics	15	2014-10-29 19:42
8 phase 12 phase, blah blah	kracker	Hardware	5	2014-01-20 02:33
Core i5 2500K vs Core i7 2600K (Linear algebra phase)	em99010pepe	Hardware	0	2011-11-11 15:18
can anyone here do algebra :)	Joshua2	Homework Help	11	2010-01-29 21:37
Beta user stats for Phase 2 - Test of 210885	SlashDude	15k Search	1	2003-12-16 23:09

2007-07-22, 22:00	#15
jasong "Jason Goatcher" Mar 2005 3507₁₀ Posts	Off-topic: Am I the only one thinking,"OMG! Similar name, similar hobby?" At least in my case, jasonp and I don't seem to cross paths all that much. (Not that I'd mind, it's just I'm sure he doesn't want to be confused with a poster who's a paranoid schizophrenic. :) )

2007-09-18, 10:23	#17
Student 1111111011000₂ Posts	Hi Everybody, I am working on the QS and my problem is that I find very often trivial solutions, especially if the number has only 2 factors. I read here http://www.nada.kth.se/~joel/qs.pdf, that we have a 50% chance of receiving trivial solutions (less if n is the product of more than two primes). Does exist any way or trick to find non-trivial solution? P.S. My program use Gaussian elimination and compute GCD of n with the difference (or sum) of the two square roots (Wikipedia) Please help!

2007-10-17, 08:56	#19
Peter Hackman Oct 2007 linköping, sweden 14₁₆ Posts	Short introduction: I'm new here. I'm a former lecturer at Linköping University; took early retirement last year. Computational Number Theory is not my specialty (my field is Commutative Algebra) but I prefer computing to bowling and bingo. I recently worked up a fairly simple MPQS program. For reasons to be discussed in another thread I chose my a=q^2 by a random process in a somewhat narrow interval about the ideal a= sqrt(2M)/N. I was puzzled to sometimes get 100 relations and no non-trivial factors. It turned out that there were repeats. Rewriting my routine eliminated these and the whole problem.

2009-10-20, 20:47	#20
SilverMan Jul 2007 10010₂ Posts	Hello all, sorry for digging up such an old thread, but i think it's better to continue in my own thread rather than starting a new one. A few months ago I found my old implementation of Quadratic Sieve on an old hard drive and after playing with it for a while I sadly realized that it's slower than i thought it was. This led me to the idea of reimplementing it all over again but this time better and more importantly - with optimizations of course. My goal is to implement a decent MPQS algorithm. At first i thought going for SIQS would be better, but this thread ( http://www.mersenneforum.org/showthread.php?t=10743 ) proved that maybe that's not the best idea. Better take small steps, one at a time :) My first problem is in the sieving stage. For all primes in my factor base i have solved the modular quadratic equation using the Shanks-Tonelli algorithm. This gave me two solutions for each prime. But how can i compute the exact indexes into the array which i sieve? Currently in my old implementation of QS i first test the numbers in my interval for divisibility and when i find the first one that is divisible by the prime, i can compute the indexes and sieve effectively. But the searching consumes a lot of time and makes sieving by large primes extremely ineffective. Surely there must be a way how to avoid this! This is just the first major problem i ran into while reimplementing QS and going through my code. There are many other topics that i'm interested in, but i know that it would be very stupid to ask questions on all of them. Instead i would be very grateful if someone could point me in the right directions - where should i look for answers and tips? I'm interested in papers on the problematic of MPQS and it's implementations, preferably as pdf's which i could download. I know the theory how QS/MPQS works, but i failed to find any good papers which are more specific. Thanks for any advice or answer!

2009-10-20, 23:06	#21
jasonp Tribal Bullet Oct 2004 3,541 Posts	See the list of QS references in the Msieve readme for some good papers on getting started. You problem boils down to moving an arithmetic progression r + k * p from the origin (k = 0) to some other point on the number line. You can do that with one division. Alternately, you can start at the origin and sieve positive k, then start again at the origin and sieve negative k; no moving the origin required.

2009-10-22, 14:05	#22
SilverMan Jul 2007 2×3² Posts	Thank you very much jasonp, i will definetly go through those papers. Maybe i'm missing something, but i still don't understand your hint about "one division" (regarding the index in the sieved interval). So for example, if i try to factor N = 250 and i have the prime 13 in my factor base, i get 4 and 9 as the results of Shanks-Tonelli. I compute the interval values using the basic polynomial: (x + sqrt(N)) - N . Now for example, the first field in my interval I is: I[0]: 16 = 6 (meaning that 16^2 is 6 (mod 250)) Now what i need is to get the index in I where the first number divisible by 13 will be. The correct answer is I[1] (the second field, with 17^2 = 39 mod 250). Sorry if the answer to this question is in some of those papers, i will start reading the one by Contini today...