mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-01-20, 10:14   #1
koders333
 

22×293 Posts
Angry 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.
  Reply With Quote
Old 2006-01-20, 13:46   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101110111002 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2006-01-20, 13:58   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

356210 Posts
Default

Quote:
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

Last fiddled with by jasonp on 2006-01-20 at 13:59
jasonp is offline   Reply With Quote
Old 2006-01-20, 17:47   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

37×317 Posts
Default

Quote:
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
xilman is offline   Reply With Quote
Old 2006-01-20, 19:22   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·13·137 Posts
Default

Quote:
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
jasonp is offline   Reply With Quote
Old 2006-01-20, 20:00   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23·3·313 Posts
Default

Quote:
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-01-20, 22:29   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·13·137 Posts
Default

Quote:
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
jasonp is offline   Reply With Quote
Old 2006-01-20, 22:38   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
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

Last fiddled with by akruppa on 2006-01-21 at 07:29
akruppa is offline   Reply With Quote
Old 2006-01-20, 23:47   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23·3·313 Posts
Default

Quote:
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 is offline   Reply With Quote
Old 2006-01-20, 23:52   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×3×313 Posts
Default

Quote:
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-01-21, 01:51   #11
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×13×137 Posts
Default

Quote:
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.

Quote:
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
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring projects algorithms - What is Aliqueit ? Romuald Factoring 75 2016-08-27 09:46
General factoring algorithms not using sieving mickfrancis Factoring 21 2016-02-22 19:38
Implementing Factoring Algorithms Raman Hobbies 45 2009-05-11 05:11
Overview of Factoring Algorithms ThiloHarich Factoring 0 2007-09-02 20:32
factoring algorithms are patented? koders333 Factoring 1 2006-01-19 20:04

All times are UTC. The time now is 20:07.


Fri Mar 31 20:07:14 UTC 2023 up 225 days, 17:35, 0 users, load averages: 1.13, 1.15, 0.90

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

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”