Re: Question about the efficiency of integer factorization algorithms
- From: Scott Contini <the_great_contini@xxxxxxxxx>
- Date: Wed, 19 Jan 2011 13:57:59 -0800 (PST)
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
Scott
.
- Follow-Ups:
- References:
- Prev by Date: Re: Need help with concealment cipher
- Next by Date: Re: Need help with concealment cipher
- Previous by thread: Re: Question about the efficiency of integer factorization algorithms
- Next by thread: Re: Question about the efficiency of integer factorization algorithms
- Index(es):
Relevant Pages
|
