There is an algorithm that tests primes with a polynomial running time:

http://fatphil.org/maths/AKS/

Has anyone coded it in Ruby?

There is an algorithm that tests primes with a polynomial running time:

http://fatphil.org/maths/AKS/

Has anyone coded it in Ruby?

On Mon, Mar 31, 2008 at 10:42 AM, Kyle S. [email protected]

wrote:

Well, I’m gonna guess that if anyone has, they would post it on that website.

I can’t get to the original paper (server’s offline, file removed?),

For those of you interested in tackling this monster…

http://en.wikipedia.org/wiki/AKS_primality_test

I’ll try my hand at it eventually, but I don’t think I could do it in

an afternoon.

Todd

Well, I’m gonna guess that if anyone has, they would post it on that

website.

I can’t get to the original paper (server’s offline, file removed?),

but a cursory overview of the c++ implementations makes me think a

decent ruby hacker could pound out an implementation in an afternoon.

Why don’t you code it, post it here for everyone to enjoy, and to that

website?

–Kyle

Charles Z. wrote:

There is an algorithm that tests primes with a polynomial running time:

http://fatphil.org/maths/AKS/Has anyone coded it in Ruby?

Hello Charles:

My head hurt trying to understand the wikipedia description for

polynomial time so I stopped read it. That aside, a cool algorithm was

pointed out by Tim P. in March of 2007. It uses regular expressions

to achieve, to a point, non-exponential solving times for prime numbers.

Here is an example of that algorithm demonstrated via a method which

extends the Fixnum class.

class Fixnum

def is_prime?

(((“1” * self) =~ /^1$|^(11+?)\1+$/) == nil)

end

end

irb(main):009:0> 2.is_prime?

=> true

irb(main):010:0> 113.is_prime?

=> true

irb(main):008:0> 123457.is_prime?

=> true

The turnaround time on solving is almost instantaneous for this

algorithm until the numbers start gets really big (i.e. like the 123457

above). I don’t know if this matches the criteria for “polynomial

running time” but thought you might find this interesting if you didn’t

know about it.

Tim made reference to this web site for credit:

http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

I used the above example to demonstrated Ruby’s ability to modify base

classes and support advanced regular expressions to a Python programming

friend. He was both impressed and a little confused by the example

Prior to using this Ruby trick the equivalent Python program was about

2.25 times faster when solving into the low 100s on Windows. After

using this trick the Ruby program was 1.1 times faster than Python which

couldn’t do the same trick according to my friend. FYI, both Ruby and

Python were still 32 times slow than CodeGear’s Delphi even though

Delphi didn’t use the regular expression trick.

Michael

On Mon, Mar 31, 2008 at 11:43 AM, Todd B. [email protected]

wrote:

I’ll try my hand at it eventually, but I don’t think I could do it in

an afternoon.

Scratch that. I found a way to sort of “cheat” using a stdlib. But,

I think you should try it the hard way for fun.

Todd

On Apr 1, 2008, at 4:23 , Charles Z. wrote:

know about it.

MichaelThat is pretty cool. It is not of polynomial running time since it

tries

to factor the number brute-force, but that is a very nifty reg EXP

trick.

The author is Perl hacker Abigail, it first appeared in

comp.lang.perl.misc:

– fxn

Michael B. wrote:

Hello Charles:

Here is an example of that algorithm demonstrated via a method which

extends the Fixnum class.class Fixnum

def is_prime?

(((“1” * self) =~ /^1$|^(11+?)\1+$/) == nil)

end

end

…

The turnaround time on solving is almost instantaneous for this

algorithm until the numbers start gets really big (i.e. like the 123457

above). I don’t know if this matches the criteria for “polynomial

running time” but thought you might find this interesting if you didn’t

know about it.

Michael

That is pretty cool. It is not of polynomial running time since it tries

to factor the number brute-force, but that is a very nifty reg EXP

trick.

On Tue, Apr 1, 2008 at 5:19 AM, Todd B. [email protected] wrote:

Charles, take a peak at the mathn library for your greatest prime factor…

require ‘mathn’

n = 12345654321

p n.prime_division.last[0]

Funny, I tried this with the same number with a 1 attached to the end

(123456543211). It took about 20 minutes, but determined it was prime

(i.e. returned [123456543211, 1]) which means 123456543211 to the

power of 1. Coincidence

Todd

On Tue, Apr 1, 2008 at 5:19 AM, Todd B. [email protected] wrote:

def is_prime?

MichaelThat is pretty cool. It is not of polynomial running time since it tries

to factor the number brute-force, but that is a very nifty reg EXP

trick.Charles, take a peak at the mathn library for your greatest prime factor…

require ‘mathn’

n = 12345654321

p n.prime_division.last[0]

Oh, btw, “n” was a bad choice of variable name here if you go by the

wikipedia article. In their notation, you want to find the greatest

prime factor of (r-1).

Just pointing out what probably is obvious.

cheers,

Todd

On Mon, Mar 31, 2008 at 9:23 PM, Charles Z. [email protected]

wrote:

end

That is pretty cool. It is not of polynomial running time since it tries

to factor the number brute-force, but that is a very nifty reg EXP

trick.

Charles, take a peak at the mathn library for your greatest prime

factor…

require ‘mathn’

n = 12345654321

p n.prime_division.last[0]

hth a little,

Todd

Posted by Todd B. (Guest) on 01.04.2008 14:08

On Tue, Apr 1, 2008 at 5:19 AM, Todd B. [email protected] wrote:

Charles, take a peak at the mathn library for your greatest prime factor…

require ‘mathn’

n = 12345654321

p n.prime_division.last[0]Funny, I tried this with the same number with a 1 attached to the end

(123456543211). It took about 20 minutes, but determined it was prime

(i.e. returned [123456543211, 1]) which means 123456543211 to the

power of 1. CoincidenceTodd

Well, you could use the Miller-Rabin prime test for a speed up! See:

http://snippets.dzone.com/posts/show/4636

You may check the outcome with primegen, http://cr.yp.to/primegen.html

time -p primes 123456543211 123456543211 # done in well under a second

Cheers,

j. k.

Yes, try Miller-Rabin or some other test like it. They’re not

absolutely perfect but very fast and usually good enough.

The original AKS is like O(d^12) , where d is the number of digits of

n. It is more of a theoretical result than a practical algorithm.

Simply testing all numbers up to sqrt(n) is 2^(d/2), which is faster

for numbers up to about 200 digits (at which they both already take

far too long, of course).

Charles Z. wrote:

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.

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs