Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 JT Posts: 1,448 Registered: 4/7/12
Re: Is factorization of big primeproducts a solved problem YET?
Posted: Jan 4, 2013 9:13 AM

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?
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.
The maximum number of tries to divide primeproduct with x to find the
factors must be SQRT primeproduct, but maybe this isn't at all time
complexity.

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