OT: Re: Prime number algo... what's wrong?

[Anton Vredegoor]

Lulu of the Lotus-Eaters <mertz at gnosis.cx> wrote:

>I've mentioned to Phil (the site maintainer for the prime number
>resources) that I think he is overbroad in his block--only three
>countries (USA, UK, Australia) are engaging in direct aggression.  The

Some antidote against the "country as person metaphor" - not implying
any signs of you being poisoned by it - :

Metaphor and War, Again
George Lakoff, AlterNet
March 18, 2003
http://www.alternet.org/story.html?StoryID=15414

An older text from the same author is providing more detail and
introduces subtle terminology such as the "ruler for state" metonym.
Sorry, no webpage here, just some info to google it up:

from: Dave Touretzky (dst at dst.boltz.cs.cmu.edu)
subject: George Lakoff on "Metaphor and War" 
newsgroups: comp.ai
date: 1990-12-31 03:54:52 PST 


>Just to attempt a slight thread connection, perhaps one could filter
>access by the primality of incoming IP addresses.  I'll have to check
>the site for efficient techniques.

Nah, just post some magma code, that will keep them busy trying to
implement the functionality in python :-)

Anton.

ps. the magma code (Not sure where I found it, so I'm posting
the code instead of the link, also I've edited it a bit in order to
avoid line breaks):

/*
Magma implementation of AKS primality proof algorithm, by 
Allan K. Steel (note my initials -- nice coincidence :-)), 
<[Allan's first name]@maths.usyd.edu.[Australia]>, 8/8/02.

The power test is done at the beginning in polynomial time 
(with a log factor). Note that I use NextPrime to loop through
the values of r.  This is faster than testing whether each new 
r is prime: NextPrime(r) computes with proof the first prime 
greater than r (and in deterministic polynomial time for 
r < 3.4*10^14). This is ironic of course, in that we have can 
prove any number < 3.4*10^14 prime in deterministic 
polynomial time (and in < 0.001 secs in practice), which is way
above the reasonable testing range for the AKS algorithm.
*/

function AKS(n)
    if IsPower(n) or n gt 2 and IsEven(n) then
        return false;
    end if;

    logn := Log(2, n);
    r := 3;
    while r lt n do
        if GCD(n, r) ne 1 then
            return false;
        end if;

        q := D[#D] where D := PrimeDivisors(r - 1);
        if q ge 4*Sqrt(r)*logn and Modexp(n, (r - 1) div q, r) \
                ne 1 then
            break;
        end if;

        r := NextPrime(r);
    end while;
    

    P<x> := PolynomialRing(IntegerRing(n));
    for a := 1 to Floor(2*Sqrt(r)*logn) do
        if Modexp(x - a, n, x^r - 1) ne x^(n mod r) - a then
            return false;
        end if;
    end for;

    return true;
end function;