Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Is factorization of big primeproducts a solved problem YET?
Replies: 19   Last Post: Jan 30, 2013 5:05 AM

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 amzoti Posts: 1,113 Registered: 3/6/07
Re: Is factorization of big primeproducts a solved problem YET?
Posted: Jan 4, 2013 12:46 PM
 Plain Text Reply

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.

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).

Thanks for any opinions or insights or avenues to explore!

-A

Date Subject Author
1/4/13 JT
1/4/13 David Bernier
1/8/13 Michael Stemper
1/8/13 Pubkeybreaker
1/10/13 Phil Carmody
1/10/13 Pubkeybreaker
1/10/13 Richard Tobin
1/11/13 Pubkeybreaker
1/11/13 Phil Carmody
1/11/13 Phil Carmody
1/11/13 Phil Carmody
1/4/13 Pubkeybreaker
1/4/13 JT
1/4/13 Pubkeybreaker
1/4/13 amzoti
1/4/13 Pubkeybreaker
1/4/13 amzoti
1/10/13 Graham Cooper
1/11/13 David Bernier
1/30/13 Rosario1903

© The Math Forum at NCTM 1994-2016. All Rights Reserved.