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/.