Hi, the GMP has an implementation of the Rabin-Miller test and supports very large numbers.
http://www.swox.com/gmp/ http://www.swox.com/gmp/manual/Number-Theoretic-Functions.html#Number%20Theoretic%20Functions Regards, Daniel Nat (Padmanabhan Natarajan) wrote: > Hi, > > Mayur, even though primality testing has been proven to be polynomial in > time, the randomized ones are what are being used due to efficiency > considerations. > > Arul, you may be better off searching for Rabin-Miller test. Wikipedia > also has an interesting article with further links. > > Cheers, > Nat > > On 4/29/06, *Mayur* <[EMAIL PROTECTED] > <mailto:[EMAIL PROTECTED]>> wrote: > > Hi, > > If you are looking for primality testing, google for the paper > "Prime is in P". The original paper's by three IIT-Kanpur people. > The papers that followed up give the best algorithms for checking > primality. > > If you are looking for prime number generation, look out for "sieve > methods" - especiialy generalized sieves. > > > On 4/29/06, *B. P. TBC* < [EMAIL PROTECTED] > <mailto:[EMAIL PROTECTED]>> wrote: > > > This algorithm (in Pascal) returns True, if x is a prime number, > and > returns False, if x isn't prime. > > function Prime(x: word): boolean; > var i: word; > v: boolean; > Begin > v := False; > if x=1 then v := True; > for i:=2 to round(sqrt(x)) do Begin > if x mod i = 0 then v := True; > End; > Prime := not v; > End; > > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
