Comments (4)
Do you want this to be a function of probability, or be fixed? That is, given b and x, one could choose numbers B1 and B2 such that x percent of b-bit numbers are B1-smooth plus at most one factor below B2 (according to the documentation of gmp-ecm, that is what is needed)...is that what you have in mind?
from flint2.
I don't think this ticket is correct. The pp1 factor method essentially requires p+1 to be B-smooth in order for the number to be able to be factored using this method. The B1 and B2 figures are just the limits in stage 1 and stage 2 that you are prepared to go to looking for B1-smoothness. So it's really just a measure of how much time you want to spend.
You really can't expect a decent proportion of factors of a given size to be found with this method.
Now that we have ECM, there is little point actually running this. It's just like using a single curve from ECM. Admittedly it is faster to run than ECM, so you can get lucky, especially for small numbers.
In summary, I'm not really sure this ticket is worth doing anything with, unless I misunderstood something.
from flint2.
I suppose we could do the following: Pick a given bitsize. We could generate random integers and trial factor them. If the cofactor has the given bitsize and is not prime, store the original number in an array. Once we have sufficiently many of them, try factoring with n_factor but calling n_factor_pp1 before n_factor_SQUFOF is called. Adjust B1 and the number of calls to n_factor_pp1 until we get the best time for factoring the array of numbers.
I'm not sure whether this will be successful or not. SQUFOF has time complexity conjecturally of O(n^5), which is pretty hard to beat. But we might find we can speed things up from about 53-64 bits or so. On the other hand, ECM would also possibly work in this range, and then you really have a multivariate optimisation problem.
from flint2.
I did exactly this, and it speeds up factorisation of numbers in the 50-64 bit range that make it this far, by up to a factor of 2.
Anyhow, now fixed in trunk.
from flint2.
Related Issues (20)
- AVX and nmod HOT 8
- FLINT license should be stated on the FLINT website HOT 1
- Gentoo Linux: sci-mathematics/flint-3.1.3_p1 QA Notice: Package triggers severe warnings which indicate that it may exhibit random runtime failures. HOT 1
- Missing functions in `fq_default` HOT 1
- `fq_default_poly_evaluate_fq_default` with context type `FMPZ_MOD` segfaults
- `make check` failing at `sub_dddmmmsss` under macOS (aarch64-apple-darwin22.6.0) HOT 12
- Compilation failure when including `qqbar.h` from within C++ HOT 1
- Documentation improvements for some ulong_extras functions
- Illegal instruction when built within singularity HOT 20
- Make failure under CentOS stream 8 HOT 6
- Make an issue template
- linker error during `make check` under macOS (duplicate symbol `_d_randtest2`) HOT 2
- Tuning thresholds for nmod vec/mat scalar multiplication HOT 5
- Faster NMOD_RED using different precomputation? HOT 3
- Strassen multiplication does more multiplications than necessary HOT 1
- Matrices using row stride instead of rows array HOT 2
- Fixed-point arithmetic (nfixed) improvements HOT 1
- Input and output not allowed to be same instance in composing? HOT 4
- Restricted partition function/Sylvester's denumerant
- Segfault in fq_default tests on Cygwin
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from flint2.