[Caml-list] Miller-Rabin primality test

[Caml-list] Miller-Rabin primality test

[Richard Jones]

To save me writing this over again, does someone have an
implementation of a probabilistic primality test in Ocaml?

Assuming I have to write one, is the 'Nat' module the best (ie.  most
mature) way to represent natural numbers in Ocaml? Or is there some
other module I ought to be using instead?

Thanks,

Rich.

-- 
Richard Jones, Red Hat Inc. (London) and Merjis Ltd. http://www.merjis.com/
http://www.annexia.org/ Freshmeat projects: http://freshmeat.net/users/rwmj
MONOLITH is an advanced framework for writing web applications in C, easier
than using Perl & Java, much faster and smaller, reusable widget-based arch,
database-backed, discussion, chat, calendaring:
http://www.annexia.org/freeware/monolith/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Miller-Rabin primality test

[Yaron M. Minsky]

There's an implementation that's part of SKS
(http://sks.sourceforge.net).  It's based on the Numerix library,
although I'm not sure that's necessarily the best way to go.  The key
files are number.ml and prime.ml, which you can get from the CVS
repository:

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/sks/sks/

(Or you can look at sks.sourceforge.net to download the distribution.) 

Anyone know what the status of Numerix is these days?  Is it still
faster than the alternatives  (gmp, Nat)?  

y

On Tue, 2003-06-03 at 07:05, Richard Jones wrote:
> To save me writing this over again, does someone have an
> implementation of a probabilistic primality test in Ocaml?
> 
> Assuming I have to write one, is the 'Nat' module the best (ie.  most
> mature) way to represent natural numbers in Ocaml? Or is there some
> other module I ought to be using instead?
> 
> Thanks,
> 
> Rich.
-- 
|--------/            Yaron M. Minsky              \--------|
|--------\ http://www.cs.cornell.edu/home/yminsky/ /--------|

Open PGP --- KeyID B1FFD916 (new key as of Dec 4th)
Fingerprint: 5BF6 83E1 0CE3 1043 95D8 F8D5 9F12 B3A9 B1FF D916



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Miller-Rabin primality test

[David Monniaux]

On Tue, 3 Jun 2003, Richard Jones wrote:

> Assuming I have to write one, is the 'Nat' module the best (ie.  most
> mature) way to represent natural numbers in Ocaml? Or is there some
> other module I ought to be using instead?

MLGMP has extended-precision integers and a builtin primality test. Get
the latest version from

http://www.di.ens.fr/~monniaux/download

David Monniaux            http://www.di.ens.fr/~monniaux
Laboratoire d'informatique de l'École Normale Supérieure,
Paris, France

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Miller-Rabin primality test

[David Brown]

On Tue, Jun 03, 2003 at 12:05:55PM +0100, Richard Jones wrote:

> To save me writing this over again, does someone have an
> implementation of a probabilistic primality test in Ocaml?

There is also one in the cryptokit.  It isn't accessible, but you could
take the code out of the library.

Dave

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Miller-Rabin primality test

[Michel Quercia]

Le 03 Jun 2003 07:48:52 -0400 "Yaron M. Minsky" <yminsky@CS.Cornell.EDU>
écrivit:

> Anyone know what the status of Numerix is these days?  Is it still
> faster than the alternatives  (gmp, Nat)?  

I'm presently writing Numerix version 0.21. First measurements show that it is 20% faster than GMP 4.0.1 ... and 8% slower than GMP 4.1.2. ETA is end of August.

Regards,
-- 
Michel Quercia
23 rue de Montchapet, 21000 Dijon
http://michel.quercia.free.fr (maths)
http://pauillac.inria.fr/~quercia (informatique)
mailto:michel.quercia@prepas.org

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Miller-Rabin primality test

[Richard Jones]

On Tue, Jun 03, 2003 at 06:52:06PM +0200, Michel Quercia wrote:
> Le 03 Jun 2003 07:48:52 -0400 "Yaron M. Minsky" <yminsky@CS.Cornell.EDU>
> ?crivit:
> 
> > Anyone know what the status of Numerix is these days?  Is it still
> > faster than the alternatives  (gmp, Nat)?  
> 
> I'm presently writing Numerix version 0.21. First measurements show that it is 20% faster than GMP 4.0.1 ... and 8% slower than GMP 4.1.2. ETA is end of August.

Be cool if you could include some of the simpler standard number theory
tests, such as primality testing, in your library.

Rich.

-- 
Richard Jones, Red Hat Inc. (London) and Merjis Ltd. http://www.merjis.com/
http://www.annexia.org/ Freshmeat projects: http://freshmeat.net/users/rwmj
PTHRLIB is a library for writing small, efficient and fast servers in C.
HTTP, CGI, DBI, lightweight threads: http://www.annexia.org/freeware/pthrlib/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Miller-Rabin primality test

[Michel Quercia]

Le Tue, 3 Jun 2003 18:05:51 +0100 Richard Jones <rich@annexia.org>
écrivit:

> Be cool if you could include some of the simpler standard number
> theory tests, such as primality testing, in your library.

I intend to call for suggestions when the new version will be usable, before the actual release time. However there is something that I don't like about the Rabin-Miller compositeness test : the output is not well defined from a mathematical viewpoint as it depends on a random sequence of bases. I'd prefer a test that returns reproducible results, perhaps by hard-coding the sequence of bases, or letting the user provide them.

Stay tuned ...
-- 
Michel Quercia
23 rue de Montchapet, 21000 Dijon
http://michel.quercia.free.fr (maths)
http://pauillac.inria.fr/~quercia (informatique)
mailto:michel.quercia@prepas.org

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners