Well sorry... Kindly excuse my ignorance...
I believe nothing is known about the class to which the factorization problem belongs to... As with the AKS algorithm... yes! "primes is in p" but many more primality testing algorithms are also known to run in P type provided the extended riemann hypothesis is assumed... Nice to see some primo discussions on an algo group :-) Keep posting. sudarshan ----- Original Message ----- From: "Dhyanesh" <[EMAIL PROTECTED]> To: <algogeeks@googlegroups.com> Sent: Wednesday, November 30, 2005 8:41 PM Subject: [algogeeks] Re: how to find Previous Prime number? Hi It is not an NP complete problem, it has been one of the open problems for quite some time. And by the way determining whether a number is prime or not is surely not NP, it is in P. This is not an approximate algorithm or anything. Here is the link to the paper: http://www.cse.iitk.ac.in/users/manindra/primality_original.pdf Also read the last paragraph on this link: http://www.guajara.com/wiki/en/wikipedia/c/co/co_np.html -Dhyanesh On 11/30/05, SUDARSHAN IYENGAR <[EMAIL PROTECTED]> wrote: > > factoring is an np complete problem. No change of having a simple algorithm > for it. > > -sudarshan > > ----- Original Message ----- > From: "Dhyanesh" <[EMAIL PROTECTED]> > To: <algogeeks@googlegroups.com> > Sent: Wednesday, November 30, 2005 7:47 AM > Subject: [algogeeks] Re: how to find Previous Prime number? > > > > I believe there is an N^12 algorithm for integer factorization ... so > it isnt all that hard i think ... > > On 11/29/05, SUDARSHAN IYENGAR <[EMAIL PROTECTED]> wrote: > > > > primality testing is a very very very tough topic to discuss... > > > > > > There is no single algorithm for primality testing... and all that is > known > > so far is nothing but intelligent brute forcing... > > > > try peeping through http://primepages.org more like a bible for prime > number > > lovers. > > > > -Sudarshan > > > > > > > > The hardest thing to understand is why we can > > understand anything at all > > - Einstein > > ----- Original Message ----- > > From: "Venkatesh Dayalan" <[EMAIL PROTECTED]> > > To: <algogeeks@googlegroups.com> > > Sent: Tuesday, November 29, 2005 7:53 PM > > Subject: [algogeeks] Re: how to find Previous Prime number? > > > > > > thanks for the info.... > > but i am looking into the logic of finding the previous prime number... > > > > > > On 11/29/05, SUDARSHAN IYENGAR <[EMAIL PROTECTED]> wrote: > > > > > > > > > hey well... you must have a look at this package "pari gp" > > > > > > try googling and you can download this package, its very small and is > the > > > best of its kind available till date... You can also get the code for > the > > > same... > > > > > > -Sudarshan > > > > > > > > > ----- Original Message ----- > > > From: <[EMAIL PROTECTED]> > > > To: "Algorithm Geeks" <algogeeks@googlegroups.com> > > > Sent: Tuesday, November 29, 2005 7:45 PM > > > Subject: [algogeeks] how to find Previous Prime number? > > > > > > > > > > > > > > Hi everbody > > > > Given a number which can be as long as 10000 digits, is there a method > > > > to find the previous prime number to it? > > > > > > > > ~venkatesh > > > > > > > > > > > > > > > > -- > > "There is no Spoon" > > > > "asato ma sad gamaya - From delusion lead me to truth > > tamaso ma jyotir gamaya - From darkness lead me to light > > mrtyor mamrtam gamaya" - From death lead me to immortality > > > > > >
