From: Andrew Mitchell Date: 2008-05-20T18:55:59+09:00 Subject: Re: Primes in P? Charles Zheng wrote: > There is an algorithm that tests primes with a polynomial running time: > http://fatphil.org/maths/AKS/ > > Has anyone coded it in Ruby? Yes. A few times. I included a tweak that greatly reduces runtime for composites, at the cost of slightly increased runtime for primes. The first time I used ruby-algebra for the polynomials. ruby-algebra Z/nZ rings precalculate and cache all multiplicative inverses rendering the runtime exponential. I changed a few lines, making precalculation into calculate on demand and cache. The second time I wrote my own Modular Polynomial class using an array for the coefficients. This allowed slightly larger numbers before running out of memory. Array became a Hash, and the maximum tolerable number increased. Still run out of memory for many large primes. Time is nearly instantaneous for all composites pq. And significantly slower for some composites of the form pqr. And very slow for primes. Under this version all the RSA challenge numbers return composite within a few seconds. Currently working on a libgmp version to speed up the polynomial math. -- Posted via http://www.ruby-forum.com/.