AKS - A polynomial-time algorithm for testing primality. - Page 2

Maybeso · 2002-11-20, 23:39

Sorry about that;
After reading that paragraph again, I realise that I was thinking about aspects of sieving and trial factoring, but trying to apply them to primality testing.

I should have limited myself to --
Use AKS when you have an actual number to test for primality that wasn't generated by plugging values into a formula, or was given to you with no formula + parameters to regenerate it. If you have the formula, its form and the relative scale of the parameters should be enough to select (or write) a primality-testing program that will out-perform AKS.

I also noticed I forgot to mention a few things:

Yes, AKS is a test-until-you-fail method.
- You evaluate the equation for a given a, then check for non-zero terms.
- If you find one, then n is composite and you can stop.
- Otherwise you try again with the next value of a.
- If you check the entire range of values, then n is prime.

The math behind evaluating f(x) (mod (x^r - 1).

Consider x^7 mod (x^7 - 1), If we plug in any value, we get
(N + 1) mod N == 1 mod N

Now Consider
Ax^11 + Bx^10 + Cx^9 + Dx^8 + Ex^7 + Fx^6 + Gx^5 + Hx^4 + Ix^3 + Jx^2 + Kx + L mod (x^7 - 1)
= (Ax^4 + Bx^3 + Cx^2 + Dx + E)x^7 + Fx^6 + Gx^5 + Hx^4 + Ix^3 + Jx^2 + Kx + L mod (x^7 - 1)

But x^7 = 1 mod (x^7 - 1), so
= (Ax^4 + Bx^3 + Cx^2 + Dx + E)(1) + Fx^6 + Gx^5 + Hx^4 + Ix^3 + Jx^2 + Kx + L mod (x^7 - 1)
= Fx^6 + Gx^5 + (A+H)x^4 + (B+I)x^3 + (C+J)x^2 + (D+K)x + (E+L) mod (x^7 - 1)

And this gives us the wrap-around behavior described before.

Finally, after processing the convolution matrix, to subtract (x^n - a), simply subtract -a from the first term and 1 from the (n mod r) term.

Regards,

Bruce

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
18th Test of primality and factorization of Lepore in 5 * log_25 (N) (New Year's algorithm)	Alberico Lepore	Alberico Lepore	2	2018-01-01 21:31
Yet another new factoring algorithm\primality test:Digital Coding ??	tServo	Miscellaneous Math	3	2014-04-10 18:52
Polynomial algorithm	diep	Factoring	7	2012-09-29 12:09
aks algorithm and polynomial	jocelynl	Math	1	2004-02-11 05:20
fastest general number primality-proving algorithm?	ixfd64	Math	3	2003-12-17 17:06

2002-11-20, 23:39	#12
Maybeso Aug 2002 Portland, OR USA 2×137 Posts	Sorry about that; After reading that paragraph again, I realise that I was thinking about aspects of sieving and trial factoring, but trying to apply them to primality testing. I should have limited myself to -- Use AKS when you have an actual number to test for primality that wasn't generated by plugging values into a formula, or was given to you with no formula + parameters to regenerate it. If you have the formula, its form and the relative scale of the parameters should be enough to select (or write) a primality-testing program that will out-perform AKS. I also noticed I forgot to mention a few things: Yes, AKS is a test-until-you-fail method. - You evaluate the equation for a given a, then check for non-zero terms. - If you find one, then n is composite and you can stop. - Otherwise you try again with the next value of a. - If you check the entire range of values, then n is prime. The math behind evaluating f(x) (mod (x^r - 1). Consider x^7 mod (x^7 - 1), If we plug in any value, we get (N + 1) mod N == 1 mod N Now Consider Ax^11 + Bx^10 + Cx^9 + Dx^8 + Ex^7 + Fx^6 + Gx^5 + Hx^4 + Ix^3 + Jx^2 + Kx + L mod (x^7 - 1) = (Ax^4 + Bx^3 + Cx^2 + Dx + E)x^7 + Fx^6 + Gx^5 + Hx^4 + Ix^3 + Jx^2 + Kx + L mod (x^7 - 1) But x^7 = 1 mod (x^7 - 1), so = (Ax^4 + Bx^3 + Cx^2 + Dx + E)(1) + Fx^6 + Gx^5 + Hx^4 + Ix^3 + Jx^2 + Kx + L mod (x^7 - 1) = Fx^6 + Gx^5 + (A+H)x^4 + (B+I)x^3 + (C+J)x^2 + (D+K)x + (E+L) mod (x^7 - 1) And this gives us the wrap-around behavior described before. Finally, after processing the convolution matrix, to subtract (x^n - a), simply subtract -a from the first term and 1 from the (n mod r) term. Regards, Bruce