Date: Jan 4, 2013 2:10 PM
Author: amzoti
Subject: Re: Is factorization of big primeproducts a solved problem YET?

On Friday, January 4, 2013 10:50:32 AM UTC-8, Pubkeybreaker wrote:
> On Jan 4, 12:46 pm, amzoti <amz...@gmail.com> wrote:
>

> > On Friday, January 4, 2013 8:53:14 AM UTC-8, Pubkeybreaker wrote:
>
> > > On Jan 4, 9:13 am, JT <jonas.thornv...@gmail.com> wrote:
>
> >
>
> > > > On 4 Jan, 13:09, Pubkeybreaker <pubkeybrea...@aol.com> wrote:
>
> >
>
> > > > > On Jan 4, 12:01 am, JT <jonas.thornv...@gmail.com> wrote:
>
> >
>
> > > > > > Does the RSA challenges have a given time complexity of factoring the
>
> >
>
> > > > > > primeproduct, or did they have one that  changed during resent years?
>
> >
>
> > > > > If I could figure out what you are asking, I would answer.....
>
> >
>
> > > > > What is a "RSA challenges have a given time complexity"?  What does
>
> >
>
> > > > > "given"
>
> >
>
> > > > > mean in this context? Why do you ask only about RSA challenges?
>
> >
>
> > > > > Are you asking for the time complexity of the fastest known general
>
> >
>
> > > > >  purpose factoring algorithm?
>
> >
>
> > > > > It is   exp( (C+o(1)) (log N)^1/3  (loglog N)^2/3)  where C =
>
> >
>
> > > > > (64/9)^1/3
>
> >
>
> > > > > As for the second part, what do you mean by "recent"?
>
> >
>
> > > > > The time complexity has changed over the last 10 years,
>
> >
>
> > > > > but only the o(1) term.
>
> >
>
> > > > Well i thought that any task that require computational work had time
>
> >
>
> > > > complexity? And that time complexity describes the amount of work
>
> >
>
> > > > needed that is generally needed to solve a problem.
>
> >
>
> > > > Does not factoring primeproduct have time complexity?
>
> >
>
> > > I gave the time complexity for the fastest known algorithm (Number
>
> >
>
> > > Field Sieve). Reread my post.
>
> >
>
> > > > It was along time since i read about sorting algorithms or did any
>
> >
>
> > > > discrete math.
>
> >
>
> > > > And i thought the work of bruteforcing a primeproduct could be given a
>
> >
>
> > > > time complexity just like sorting problems.
>
> >
>
> > > It can.  But noone factors large numbers by brute force.
>
> >
>
> > Hi Pubkeybreaker
>
> >
>
> > I know you are an expert in this area, so I'd thought I'd ask for a personal opinion.
>
> >
>
> > You mention the NFS as the best that is currently know in terms of running time for solving the factoring problem.
>
> >
>
> > In your opinion, can you recommend some other areas that you might feel are worthy of exploring in order to improve upon that algorithm.
>
>
>
> Improve NFS? There are a variety of small refinements that can
>
> improve the o(1) term.
>
> But any major change would probably be a completely new algorithm.
>
> Noone can predict that.
>
>
>
>
>

> >
>
> > I know my question may be ill-formed, but I was just curious about your opinion on the matter.
>
> >
>
> > Are there avenues you feel are worth exploring and researching in order to find a better NFS? (Maybe know ones knows the answer yet to that either).
>
>
>
> I am unsure what you mean by "better NFS".
>
> Certainly the polynomial selection process can be improved.
>
> What else might you have in mind?
>
> The biggest improvement would come from something that decreases the
>
> size of the norms.
>
> But for NFS there isn't much that can be done. A procedure that
>
> produced norms smaller
>
> than NFS would no longer be NFS.


In addition to slight improvements on NFS, where is the research heading in terms of completely new algorithms?

Do you have any insights?

Thanks -A