[QUOTE=YuL;359184]Thank you all for your help;

I lack the knowledge necessary to understand the various posts above especially
the one from Mr Silverman. I am just a software engineer who graduated in mathematics
more than 13 years ago, I wasn't even into number theory at that time.
BUT I'm willing to learn because I love mathematics and it is a lot a fun to factor big numbers.
[/QUOTE]

Get hold of the following:

Hardy & Wright: Introduction to Number Theory
Crandall & Pomerance : Prime Numbers, a Computational Perspective
Knuth: TAOCP, VOl 2.

Read them from cover to cover. DO THE EXERCIZES. If you have trouble
with the text or exercizes, ASK. If you want additional references we
can provide them.

I assume that as part of your degree that you did take at least one
course in modern algebra and one in linear algebra and that you have some
mathematical maturity.

What is it that you don't understand about my post?

I think we are going a little bit off topic.. anyway here is my answer.

[QUOTE=R.D. Silverman;359187]
...Crandall & Pomerance : Prime Numbers, a Computational Perspective...
[/QUOTE]

I bought the second edition of that one two years ago, it is a fantastic book but I think it can hardly be considered as an introduction to the subject so I was going to get the Hardy & Wright soon.
Thanks for the references.

[QUOTE=R.D. Silverman;359187]
...
Read them from cover to cover. DO THE EXERCIZES. If you have trouble
with the text or exercizes, ASK.
[/QUOTE]

I'll try.

[QUOTE=R.D. Silverman;359187]
I assume that as part of your degree that you did take at least one
course in modern algebra and one in linear algebra...
[/QUOTE]

Yes I did.

[QUOTE=R.D. Silverman;359187]
...and that you have some mathematical maturity.
[/QUOTE]

I hope so :)

[QUOTE=R.D. Silverman;359187]
What is it that you don't understand about my post?
[/QUOTE]

What does it mean concretely to sieve "on one side"?
You wrote that you compute the actual factorizations of the smooth
relations via a re-sieve, does it mean that you relaunch the siever
on the same range?
You also wrote that you store the factors found during the re-sieve in a
hash table. I suppose you use a program to do so?
How do you know whether an overflow occurs when storing the factors in the hash-table?

[QUOTE=YuL;359217]

What does it mean concretely to sieve "on one side"?
You wrote that you compute the actual factorizations of the smooth
relations via a re-sieve, does it mean that you relaunch the siever
on the same range?
You also wrote that you store the factors found during the re-sieve in a
hash table. I suppose you use a program to do so?
How do you know whether an overflow occurs when storing the factors in the hash-table?[/QUOTE]

Let's take this one piece at a time.

How much do you know about how NFS works? You need to gain a basic
understanding of what it does before we can have further discussion.

We have two fields: One is typically Q, another is Q(alpha) for some
alpha a root of an irreducible polynomial f. We also have an integer N
that we are trying to factor and a second polynomial g. f and g
share a common root M mod N, so there is a ring homomorphism phi from
alpha to M over Z/NZ. This yields a congruence (a + bM) =
(a + b phi(alpha)) mod N. Thus the congruence has "two sides"


We look for lattice points (a,b) such that
the norm of a + bM and the norm of a + b alpha are simultaneously smooth.
We sieve over (a,b) for one set of norms/polynomial, and over a sub-lattice of (a,b) for the other polynomial such that the norms in the sub-lattice are always divisible by the special q.

The siever isn't 'relaunched'. It is all one program. Once we find
points whose norm might be smooth, we need to reconstruct the factorization. This is partially done by running the sieve again, but
instead of adding log(p) to lattice locations, we store p itself
in a hash table.

If you do not know what a hash table is, or how it works you have
more reading to do. Read the Knuth volume (3?) that discusses it.

One gets a hash overflow when there isn't enough vacant space in the
table to store more primes.

An NFS siever is complicated. You might first want to learn how
QS works.

[QUOTE=R.D. Silverman;359222]Let's take this one piece at a time.[/QUOTE]

:goodposting::smile:

[QUOTE=wblipp;359225]:goodposting::smile:[/QUOTE]
:goodposting:+1. (I like this new Mr. Silverman! ... :razz:)

[QUOTE=YuL;359217]so I was going to get the Hardy & Wright soon
[/QUOTE]
I goth [URL="https://archive.org/details/AnIntroductionToTheTheoryOfNumbers-4thEd-G.h.HardyE.m.Wright"]this link[/URL] long ago, also by RDS's "recommendation" (don't wanna say a stronger word here, hehe). The book is very good, and the forth edition printed in '75 is already public domain. See the links on the left, where different e-reader versions are also available.

[QUOTE]
What does it mean concretely to sieve "on one side"?
[/QUOTE]
Like in "rational" versus "algebraic"?

[QUOTE=R.D. Silverman;359222]
...
An NFS siever is complicated. You might first want to learn how
QS works.
[/QUOTE]

Thank you for your careful explanation. Regarding that last statement,
looking into the QS is what I was doing over the last few days mainly
by the reading the Crandall & Pomerance and I think I got the idea.

[QUOTE=R.D. Silverman;359222]
....so there is a ring homomorphism phi from
alpha to M over Z/NZ. This yields a congruence (a + bM) =
(a + b phi(alpha)) mod N. Thus the congruence has "two sides"
[/QUOTE]

OK so now I got the explanation for the "sieving on the rational side" vs
"sieving on the algebraic side", it comes from the congruence
a + bM = (a + b phi(alpha)) mod N. I can directly map that to the
corresponding command line options in the GGNFS siever.

I know what an hash-table is but I don't see how it can overflow
I think it depends on the implementation.. If we temporarily
forget about the hash-table, is what you wrote equivalent
to setting a bound B on the number of primes obtained
by re-sieving and saying that an overflow occurs iff the
number of primes becomes >= B. If so, how is B computed?

Generally speaking I have a hard time finding the correspondence
between the theory and all those values in the poly file.
I've seen various posts were people talk about sieving on both sides
but AFAIK factmsieve.py(*) sieves only one side.

(*) Brian Gladman's python script I've been using for months
as a fire and forget tool for my factorizations.


[QUOTE=LaurV;359245]
I goth [URL="https://archive.org/details/AnIntroductionToTheTheoryOfNumbers-4thEd-G.h.HardyE.m.Wright"]this link[/URL] long ago, also by RDS's "recommendation" (don't wanna say a stronger word here, hehe). The book is very good, and the forth edition printed in '75 is already public domain. See the links on the left, where different e-reader versions are also available.
...
[/QUOTE]

Thanks but I'm going to get the french translation (will be easier for me).

[QUOTE=YuL;359266]
I know what an hash-table is but I don't see how it can overflow
I think it depends on the implementation..
[/QUOTE]

huh? One allocates space for the table. If there are more primes
to store than space allows one gets an overflow. Why is this a
mystery? One can also get an "overflow" as the table starts to get full.
If a collision occurs it has to be resolved. There are a variety of ways
to do this. But once the table starts to get full one spends TOO MUCH
TIME resolving the *()!#&*@#&* collisions. It isn't worth it.

Yes. I could re-code to dynamically allocate more space for the table
as it starts to get full. I never thought it worth the effort.

[QUOTE]
If we temporarily
forget about the hash-table, is what you wrote equivalent
to setting a bound B on the number of primes obtained
by re-sieving and saying that an overflow occurs iff the
number of primes becomes >= B. If so, how is B computed?
[/QUOTE]

No.

[QUOTE]
Generally speaking I have a hard time finding the correspondence
between the theory and all those values in the poly file.
I've seen various posts were people talk about sieving on both sides
but AFAIK factmsieve.py(*) sieves only one side.
[/QUOTE]

No. It sieves both sides. It only applies the special-q value to one
side, but both sides get sieved.

Perhaps you might want to read "Development of the Number Field Sieve",
by Lenstra et.al.?

[QUOTE=YuL;359266]I've seen various posts where people talk about sieving on both sides
but AFAIK factmsieve.py(*) sieves only one side.[/quote]

This is an abuse of language: "sieve on the algebraic side" is being used there to mean "sieving using algebraic special-Q" (that is, doing some lattice manipulations so that you are looking only at X,Y where a given medium-sized prime Q is guaranteed to divide f_algebraic(X,Y) )

You have regardless to end up with X,Y where f_algebraic and f_rational are only divisible by moderately-sized primes.

Regarding the confusion about using hashtables: Sieving in NFS requires finding places where the values of two polynomials are simultaneously divisible by small factors. The goal is never to find all such places but to maximize the number of such places found per unit time. All those sieving parameters are there to set up approximations that reduce the work in return for missing a few 'hits' that we would otherwise find.

Hits are expected to be rare. Rather than evaluating the sieve for both polynomials simultaneously, we can evaluate one sieve, remember any (approximate) hits found, and then evaluate the other sieve at only those locations. Another possibility is to run both sieves but not bother to remember the list of primes dividing each hit. Then for simultaneous hits in both sieves we can go back and reconstruct the list of primes later. These techniques both benefit from using hashtables; putting too many hits in the hashtable is not impossible, but it does mean the approximations used are too loose and you will spend too much time sorting usable hits from unusable ones. This is the 'overflow' condition Bob refers to.

[QUOTE=YuL;359217]
What does it mean concretely to sieve "on one side"?
[/QUOTE]

You can sieve on two sides -- the 'algebraic' side and the 'rational' side. If your .poly file has "type: snfs" then the factMsieve.pl script will sieve on the 'rational' side. If your .poly file has "type: gnfs" then it sieves on the 'algebraic' side. I believe the .py script is just a straight port from the perl script, so this should also apply there.

For the parameters, you'll notice that about half end in "r" and half end in "a". The "r" ones apply to the 'rational' sieving and the "a" ones apply to the 'algebraic' sieving.

Concretely, if you are manually calling the siever or modifying the scripts, you will have know that the "-a" parameter is for specifying 'algebraic' sieving and "-r" for 'rational' sieving.

Hope that helps a bit:smile:.

For what that means mathematically, you will have to listen RDS, Fivemack, jasonp, etc.