prime factorization algorithms?

[cheesehead]

Originally Posted by science_man_88

is http://en.wikipedia.org/wiki/Factor_base a good source ? If so I partially understand but not to a level that I could help yet.

Let's not forget that MathWorld (formerly Eric Weisstein's World of Mathematics, now at http://mathworld.wolfram.com/ ) is a good source of concise definitions, though it doesn't go into history and such.

[MathBoy]

well, I have been looking at the Wikipedia , and Mathworld definitions but still don't fully think I understand it.

definition of a factor bases:
The primes with Legendre symbol (n/p)=1 (less than pi(d) for trial divisor d) which need be considered when using the quadratic sieve factorization method

Question
From this definition how do you know what d should be so that you can find a nontrivial square congruence relation for n? (i.e x^2 = y^2 mod n)


From this definition it seems that a factor bases is just a set of prime numbers under a randomly chosen pi(d) such that n is a quadratic residue mod all those primes in that set.

sorry if I am not getting the obvious.

[CRGreathouse]

Originally Posted by MathBoy

From this definition how do you know what d should be so that you can find a nontrivial square congruence relation for n?

Choose whatever you like. If it works, you find a factor; if it fails, choose a larger d and start over.

There are tables and heuristics and data to help you choose a number large enough without being so large that it's slow.

Originally Posted by MathBoy

From this definition it seems that a factor bases is just a set of prime numbers under a randomly chosen pi(d) such that n is a quadratic residue mod all those primes in that set.

Right. Depending on what method you use, it's either easy to build the factor base or entirely trivial.

[davar55]

Originally Posted by R.D. Silverman

For general algorithms yes. But ECM is better at factoring when
factors are relatively small.

Is that so? Could you please quantify this claim?

[MathBoy]

Choose whatever you like. If it works, you find a factor; if it fails, choose a larger d and start over.

There are tables and heuristics and data to help you choose a number large enough without being so large that it's slow.

So the QS , GNFS , and their variants
Won't give you any factors provided you don't choose d high enough / correctly?
If this is true then these methods really don't guarantee you a factor necessarily only if their is a guaranteed way to find d such that a nontrivial relation holds in your factor bases and you can reasonable calculate the factor bases set.

Correct me if I am wrong

[CRGreathouse]

Originally Posted by MathBoy

So the QS , GNFS , and their variants
Won't give you any factors provided you don't choose d high enough / correctly?

Only insofar as trial division won't give you a factor if you don't go high enough.

With trial division, you know that there is a factor to find if you search long enough. With, e.g., QS you know that there are enough relations if you search long enough. It would be easy to come up with a value that would be guaranteed high enough to work in all cases, but it's much better to choose a good value rather than a worst-case value. (In practice, you never change the size of the factor base; if the size was a little off you just sieve slightly longer than you'd otherwise sieve.)

[MathBoy]

OK

But obtaining a factor bases would be equivalent to finding all primes that have the relation x^2 = n mod p in the set of numbers pi(d).

I would think this is still a long process to do and takes brute force.
Unless their is an easy way to compute if n is a quadratic residue mod a prime fast? And to compute it fast for all primes under pi(d). Either way won't this be equivalent to trial divisors for numbers up to pi(d) for runtime. Seems it to me.

Also is this definition of a factor bases for the QS the same for the GNFS , SNFS , RNFS ,...etc?
Or is their a different definition for each method?


Thank you for all your help in understanding this.

[R.D. Silverman]

Originally Posted by MathBoy

well, I have been looking at the Wikipedia , and Mathworld definitions but still don't fully think I understand it.

definition of a factor bases:
The primes with Legendre symbol (n/p)=1 (less than pi(d) for trial divisor d) which need be considered when using the quadratic sieve factorization method

No. The part about "trial divisor d" is wrong.

We are discussing only QS here. The factor base is a set of primes
that are quadratic residues of the number being factored. The set consists
of all primes less than a specified bound B. This bound is an input
parameter.

We use a quadratic polynomial Ax^2 + 2Bx + C whose discriminant
is a multiple k, of n. k is chosen to maximize the Knuth-Schroeppel
function.

READ my 1987 paper: The Multiple Polynomial Quadratic Sieve. Math. Comp.

From this definition it seems that a factor bases is just a set of prime numbers under a randomly chosen pi(d) such that n is a quadratic residue mod all those primes in that set.

"under a randomly chosen pi(d)" is gibberish. The correct statement should
be "all primes less than a chosen bound B". [you also need the unit
-1 to hold the sign bit]

[R.D. Silverman]

Originally Posted by MathBoy

OK

But obtaining a factor bases would be equivalent to finding all primes that have the relation x^2 = n mod p in the set of numbers pi(d).

This is more gibberish. You want all primes p < B, such that (p|n) = 1
[Legendre symbol]. This takes a few seconds at most for even fairly
large B [e.g. B = 10^7]

I would think this is still a long process to do and takes brute force.
Unless their is an easy way to compute if n is a quadratic residue mod a prime fast?

Get hold of Crandall & Pomerance: Prime Numbers, A computational
perspective.

It is TRIVIAL to compute the Legendre symbol.

And to compute it fast for all primes under pi(d). Either way won't this be equivalent to trial divisors for numbers up to pi(d) for runtime. Seems it to me.

"seems to me"???? You don't know enough to have an opinion.

You need to learn some basic number theory. Without it, understanding
these algorithms will be hopeless. Start by looking up "Quadratic Reciprocity"

And stop using the word "under". If you mean "less than", than say it!

Also is this definition of a factor bases for the QS the same for the GNFS , SNFS , RNFS ,...etc?
Or is their a different definition for each method?

I already discussed this. Go back and read what I wrote.

[R.D. Silverman]

Originally Posted by MathBoy

So the QS , GNFS , and their variants
Won't give you any factors provided you don't choose d high enough / correctly?
If this is true then these methods really don't guarantee you a factor necessarily only if their is a guaranteed way to find d such that a nontrivial relation holds in your factor bases and you can reasonable calculate the factor bases set.

Correct me if I am wrong

Stop making guesses and go read my Math. Comp. paper. It explains
everything you need to know.

[CRGreathouse]

Originally Posted by R.D. Silverman

Stop making guesses and go read my Math. Comp. paper. It explains
everything you need to know.

Actually, he shouldn't -- it's not yet within his reach. He'll need to learn more before tackling that paper, and the forums are a passable place for that.