Re: Question about the efficiency of integer factorization algorithms



On 2011-01-19, Scott Contini <the_great_contini@xxxxxxxxx> wrote:
On Jan 20, 7:11?am, unruh <un...@xxxxxxxxxxxxxxxxxxxxxxx> wrote:
On 2011-01-19, gaulois <n...@xxxxxxxx> wrote:



Hi,
I was just wondering about the following:
Suppose some integer n is composed of the two prime factors p1 and p2:

n = p1 * p2

Also suppose the difference between the two prime factors

d = |p2 - p1|

is about the size of (n)^(1/4) or less:

d < (n)^(1/4)

My question:
Are there any known algorithms to perform the factorization of n
efficiently for large n (n >> 10^100)?

Depends on what you mean by efficiently. If you mean better than n^2
operations, yes. If you mean better than 1000 operations, no.
I believe that the best is something like exp(1.92 ln2(n)^(1/3)(ln2(ln2(n))^(2/3))
which for n=10^100 is about 10^24 operations.
Is that efficient enough for you? (demanding d<n^1/4 really does not
help much AFAIK. If d<ln(n) then you would be able to do better.)



Hi Unruh, it does help a lot. These numbers can be
factored very quickly with Fermat's factoring method!
I'd have to search around for a good source but in
the mean time read first paragraph of section 2 of:
http://arxiv.org/ftp/math/papers/0702/0702227.pdf

Thanks. Learn something new every day.



Scott
.



Relevant Pages

  • Re: Surrogate factoring demonstrated
    ... The factorization is likely to pull out the smallest prime first. ... And notice the number of iterations. ... > That would be reflected in changes in the algorithms used. ... >> HUGE jump from algorithms where you factored T and j. ...
    (sci.math)
  • Re: Surrogate factoring demonstrated
    ... The factorization is likely to pull out the smallest prime first. ... And notice the number of iterations. ... > That would be reflected in changes in the algorithms used. ... >> HUGE jump from algorithms where you factored T and j. ...
    (sci.crypt)
  • Re: How to enable JIT?
    ... The best known factorization algorithms for big ... no known good algorithm for performing that computation on a cluster. ... Java or not Java, you will be famous. ... could support a number of algorithms with decent performance. ...
    (comp.lang.java.programmer)
  • Re: How to enable JIT?
    ... The best known factorization algorithms for big ... no known good algorithm for performing that computation on a cluster. ... Java or not Java, you will be famous. ... could support a number of algorithms with decent performance. ...
    (comp.lang.java.programmer)
  • Re: How to enable JIT?
    ... algorithms and other ones that require a lot of processing time. ... The best known factorization algorithms for big ... Java or not Java, you will be famous. ...
    (comp.lang.java.programmer)