Re: Question about the efficiency of integer factorization algorithms
- From: unruh <unruh@xxxxxxxxxxxxxxxxxxxxxxx>
- Date: Thu, 20 Jan 2011 03:26:41 GMT
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
- References:
- Prev by Date: Re: Sort of OT: The weakest link
- Next by Date: Re: Sort of OT: The weakest link
- 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
|
