design factoring algorithms

All the factoring algorithms are based on number theory concepts.Nothing wrong with this.But we cann't succeded with number thory alone.Why not we try to design factoring algorithms based on machine learning and genetic algorithms etc.Atleast try to embed these concepts with existing algorithms to improve its performance.I see some papers on monto carlo based factoring algorithms etc.But these are not popular yet.

[alpertron]

Well, if you can show us that the computer can learn how to factor faster than GNFS, I will gladly program that algorithm.

Wait!! In that case the computer should also be able to program itself, so I don't have to work this time.

[jasonp]

Originally Posted by koders333

All the factoring algorithms are based on number theory concepts.Nothing wrong with this.But we cann't succeded with number thory alone.Why not we try to design factoring algorithms based on machine learning and genetic algorithms etc.Atleast try to embed these concepts with existing algorithms to improve its performance.I see some papers on monto carlo based factoring algorithms etc.But these are not popular yet.

You're not the first to wonder about that. The problem with using combinatorial optimization techniques for factoring is that the search space is essentially flat except at the solution, so there are no 'clues' where the answer is unless you use number theory.

Besides, most combinatorial algorithms are exponential-time, and the best current factoring algorithms do much better than that. People can solve the traveling salesman problem for large numbers of cities because of approximation algorithms that give a 'good enough' solution, but close doesn't count with factoring.

That being said, this territory is largely unexplored. There are plenty of good books on combinatorial optimization, but the subject is really hard.

jasonp

[xilman]

Originally Posted by jasonp

You're not the first to wonder about that. The problem with using combinatorial optimization techniques for factoring is that the search space is essentially flat except at the solution, so there are no 'clues' where the answer is unless you use number theory.

Besides, most combinatorial algorithms are exponential-time, and the best current factoring algorithms do much better than that. People can solve the traveling salesman problem for large numbers of cities because of approximation algorithms that give a 'good enough' solution, but close doesn't count with factoring.

That being said, this territory is largely unexplored. There are plenty of good books on combinatorial optimization, but the subject is really hard.

jasonp

In principle, we could also program computers to develop their own number theoretical knowledge and then to apply that to the development of novel algorithms. The first part of this proposal is a very hard problem to solve. However, it is almost certainly not an insoluble problem. Some success in creating theorem-creating programs has been reported. Discoveries (really re-discoveries) in Euclidean plane geometry by a program were first reported at least 20 years ago.


Paul

[jasonp]

Originally Posted by xilman

In principle, we could also program computers to develop their own number theoretical knowledge and then to apply that to the development of novel algorithms. The first part of this proposal is a very hard problem to solve. However, it is almost certainly not an insoluble problem.

My personal belief is that much more can be squeezed out of NFS than is currently available, and that squeezing should happen before anyone considers throwing it out and starting over.

jasonp

[R.D. Silverman]

Originally Posted by jasonp

My personal belief is that much more can be squeezed out of NFS than is currently available, and that squeezing should happen before anyone considers throwing it out and starting over.

jasonp

Enlighten us. What is the basis for your belief? Explain how you think
the method can be improved.

[jasonp]

Originally Posted by R.D. Silverman

Enlighten us. What is the basis for your belief? Explain how you think the method can be improved.

Well, Dan Bernstein has several ideas that nobody has implemented yet. On top of those:

- the only practical choices for polynomials is a pair of quadratics and the polynomials produced by the base-m method. Both Murphy and Crandall/Pomerance believe that other choices of polynomials (say, a pair of cubics or degree-4 / degree 2) can have better yield, especially if they're chosen so that their roots almost coincide. Does nobody know how to go about looking for such oddball polynomials? I certainly don't, but this has the potential to drastically increase sieving speed if C&P are to be believed.

- is there a way to have a hybrid between line sieving and lattice sieving? Can data structures like a compressing radix tree (i.e. Hewlett-Packard's Judy library) replace a sieve as a practical way of handling extremely long lines? What about using Judy to sieve for several special-Q at once? What about making each special Q a product of several small primes? If each small prime has several roots, then each combination of roots is a separate special-Q and you get more special-Q that are are small (and so keep the relation yield high for longer)

- nobody understands the behavior of cycles generated in the filtering phase. What if you took large primes found during sieving and turned them into the next 'special Q' for use in a lattice siever? Would suddenly having lots more of each large prime cause a cycle explosion sooner? (one of my friends is a chemist, and when I explained the cycle explosion problem and how it looks like a phase change, he said that in physical phenomena a phase change somehow needs a 'seed' to get started)

I've wondered about these for a while, and they may go nowhere. But the point is that these ideas do not sound obviously dumb to me, and nobody has looked at them seriously. Why try to apply some unrelated field to factoring when the basics still need exploring?

jasonp

[akruppa]

Originally Posted by jasonp

Well, Dan Bernstein has several ideas that nobody has implemented yet. On top of those:

- nobody understands the behavior of cycles generated in the filtering phase. What if you took large primes found during sieving and turned them into the next 'special Q' for use in a lattice siever?

That is something I had wondered about as well. It should be reasonable to favour primes/ideals that appeared before. They are certain not to end up being singletons, and if the prime occurred only once before, they actually save a second relation from being discarded. I.e., would it make sense to add large primes that occurred before to the factor base at some point during the sieving?

Alex

[R.D. Silverman]

Originally Posted by akruppa

That is something I had wondered about as well. It should be reasonable to favour primes/ideals that appeared before. They are certain to not end up being singletons, and if the prime occurred only once before, they actually save a second relation from being discarded. I.e., would it make sense to add large primes that occurred before to the factor base at some point during the sieving?

Alex

I've done that. The speed-up, if any, was tiny.

[R.D. Silverman]

Originally Posted by jasonp

Well, Dan Bernstein has several ideas that nobody has implemented yet. On top of those:

- the only practical choices for polynomials is a pair of quadratics and the polynomials produced by the base-m method. Both Murphy and Crandall/Pomerance believe that other choices of polynomials (say, a pair of cubics or degree-4 / degree 2) can have better yield, especially if they're chosen so that their roots almost coincide. Does nobody know how to go about looking for such oddball polynomials? I certainly don't, but this has the potential to drastically increase sieving speed if C&P are to be believed.

- is there a way to have a hybrid between line sieving and lattice sieving? Can data structures like a compressing radix tree (i.e. Hewlett-Packard's Judy library) replace a sieve as a practical way of handling extremely long lines? What about using Judy to sieve for several special-Q at once? What about making each special Q a product of several small primes? If each small prime has several roots, then each combination of roots is a separate special-Q and you get more special-Q that are are small (and so keep the relation yield high for longer)

- nobody understands the behavior of cycles generated in the filtering phase. What if you took large primes found during sieving and turned them into the next 'special Q' for use in a lattice siever? Would suddenly having lots more of each large prime cause a cycle explosion sooner? (one of my friends is a chemist, and when I explained the cycle explosion problem and how it looks like a phase change, he said that in physical phenomena a phase change somehow needs a 'seed' to get started)

I've wondered about these for a while, and they may go nowhere. But the point is that these ideas do not sound obviously dumb to me, and nobody has looked at them seriously. Why try to apply some unrelated field to factoring when the basics still need exploring?

jasonp

Finding two cubics or a quartic/quadratic pair seems to involve some
very difficult lattice basis reduction computations. If it is possible to
find such pairs it will require extensive pre-computation.

None of the proposed ideas are going to have a dramatic impact.
All of them only affect the o(1) term in the run time. At best, they will
have only a constant time speed improvement. It all depends on the
size of the norms being sieved, and none of these ideas reduce the
asymptotic size of those norms. One could get a speed improvement
from 2 cubics if both have 3 real roots. But it will not be that large.

Dan's idea of replacing sieving with ECM is TOTALLY impractical.

[jasonp]

Originally Posted by R.D. Silverman

None of the proposed ideas are going to have a dramatic impact.
All of them only affect the o(1) term in the run time. At best, they will
have only a constant time speed improvement. It all depends on the
size of the norms being sieved, and none of these ideas reduce the
asymptotic size of those norms. One could get a speed improvement
from 2 cubics if both have 3 real roots. But it will not be that large.

The sieving ideas don't change the size of the underlying norms, but I wonder if some combination of those ideas can simulate the use of triple large primes without actually having to factor big composites, After all, if you sieve enough then you don't need to do anything else :)

For the record, the qsieve package has an MPQS implementation whose factor base grows over time to incorporate large primes found during sieving. From what I can tell of the results available online, it doesn't seem to help, but it does reduce the number of cofactors that need factoring via non-sieving means.

I suppose I should have stated up front that I'd be happy with a constant time improvement. MPQS is a constant-time improvement over QS (I think), and one is practical while the other really is not.

Originally Posted by R.D. Silverman

Dan's idea of replacing sieving with ECM is TOTALLY impractical.

Agreed. I likewise have a hard time believing that batch factoring methods can exceed the speed of sieve-based methods in practice.

Another possibility for the linear algebra stage: is it possible to leverage the huge literature on sparse matrix methods to make the linear algebra easier? CWI's filtering algorithms don't reference the scientific computing literature on this subject at all; is that because there's nothing worth borrowing?

jasonp