Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Pubkeybreaker

Posts: 1,350
Registered: 2/12/07
Re: Is factorization of big primeproducts a solved problem YET?
Posted: Jan 4, 2013 1:50 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.


Date Subject Author
1/4/13
Read Is factorization of big primeproducts a solved problem YET?
JT
1/4/13
Read Re: Is factorization of big primeproducts a solved problem YET?
David Bernier
1/8/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Michael Stemper
1/8/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Pubkeybreaker
1/10/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Phil Carmody
1/10/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Pubkeybreaker
1/10/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Richard Tobin
1/11/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Pubkeybreaker
1/11/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Phil Carmody
1/11/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Phil Carmody
1/11/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Phil Carmody
1/4/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Pubkeybreaker
1/4/13
Read Re: Is factorization of big primeproducts a solved problem YET?
JT
1/4/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Pubkeybreaker
1/4/13
Read Re: Is factorization of big primeproducts a solved problem YET?
amzoti
1/4/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Pubkeybreaker
1/4/13
Read Re: Is factorization of big primeproducts a solved problem YET?
amzoti
1/10/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Graham Cooper
1/11/13
Read Re: Is factorization of big primeproducts a solved problem YET?
David Bernier
1/30/13
Read Re: Is factorization of big primeproducts a solved problem YET?
Rosario1903

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.