How to resolve the algorithm AKS test for primes step by step in the 11l programming language

Published on 12 May 2024 09:40 PM
#11l

How to resolve the algorithm AKS test for primes step by step in the 11l programming language

Table of Contents

Problem Statement

The AKS algorithm for testing whether a number is prime is a polynomial-time algorithm based on an elementary theorem about Pascal triangles. The theorem on which the test is based can be stated as follows: are divisible by

p

{\displaystyle p}

.

Using

p

3

{\displaystyle p=3}

:

And all the coefficients are divisible by 3,   so 3 is prime.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm AKS test for primes step by step in the 11l programming language

Source code in the 11l programming language

F expand_x_1(p)
   V ex = [BigInt(1)]
   L(i) 0 .< p
      ex.append(ex.last * -(p - i) I/ (i + 1))
   R reversed(ex)

F aks_test(p)
   I p < 2
      R 0B
   V ex = expand_x_1(p)
   ex[0]++
   R !any(ex[0 .< (len)-1].map(mult -> mult % @p != 0))

print(‘# p: (x-1)^p for small p’)
L(p) 12
   print(‘#3: #.’.format(p, enumerate(expand_x_1(p)).map((n, e) -> ‘#.#.#.’.format(‘+’ * (e >= 0), e, I n {(‘x^#.’.format(n))} E ‘’)).join(‘ ’)))

print("\n# small primes using the aks test")
print((0..100).filter(p -> aks_test(p)))

You may also check:How to resolve the algorithm Singly-linked list/Traversal step by step in the Scheme programming language
You may also check:How to resolve the algorithm Host introspection step by step in the TXR programming language
You may also check:How to resolve the algorithm Array concatenation step by step in the ATS programming language
You may also check:How to resolve the algorithm Arbitrary-precision integers (included) step by step in the Maxima programming language
You may also check:How to resolve the algorithm Non-decimal radices/Input step by step in the Common Lisp programming language