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:

   a number   



p


{\displaystyle p}

   is prime   if and only if   all the coefficients of the polynomial expansion of
 



(
x
−
1

)

p


−
(

x

p


−
1
)


{\displaystyle (x-1)^{p}-(x^{p}-1)}


are divisible by   



p


{\displaystyle p}

.



Example

Using   



p
=
3


{\displaystyle p=3}

:

         (x-1)^3 - (x^3 - 1)
            = (x^3 - 3x^2 + 3x - 1) - (x^3 - 1)
            = -3x^2 + 3x



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





 Note:
This task is not the AKS primality test.   It is an inefficient exponential time algorithm discovered in the late 1600s and used as an introductory lemma in the AKS derivation.



Task



 Create a function/subroutine/method that given   



p


{\displaystyle p}

   generates the coefficients of the expanded polynomial representation of   



(
x
−
1

)

p




{\displaystyle (x-1)^{p}}

.
 Use the function to show here the polynomial expansions of   



(
x
−
1

)

p




{\displaystyle (x-1)^{p}}

   for   



p


{\displaystyle p}

   in the range   0   to at least   7,   inclusive.
 Use the previous function in creating another function that when given   



p


{\displaystyle p}

   returns whether   



p


{\displaystyle p}

   is prime using the theorem.
 Use your test to generate a list of all primes under   35.
 As a stretch goal,   generate all primes under   50   (needs integers larger than 31-bit).


References

 Agrawal-Kayal-Saxena (AKS) primality test (Wikipedia) 
 Fool-Proof Test for Primes - Numberphile (Video). The accuracy of this video is disputed -- at best it is an oversimplification.


 
/* ARM assembly Raspberry PI  or android 32 bits */
/*  program AKS.s   */ 
 
/* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.inc"
.equ MAXI,       32
.equ NUMBERLOOP, 10
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessResult:        .asciz " (x-1)^@ = "
szMessResult1:       .asciz " @ x^@   "
szMessResPrime:      .asciz "Number @ is prime. \n"
szCarriageReturn:    .asciz "\n"
 
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:        .skip 24
iTabCoef:         .skip 4 * MAXI
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                               @ entry of program 
 
    mov r4,#1
1:                                  @ loop
    mov r0,r4
    bl computeCoef                  @ compute coefficient
    ldr r0,iAdriTabCoef
    mov r0,r4
    bl displayCoef                  @ display coefficient
    add r4,r4,#1
    cmp r4,#NUMBERLOOP
    blt 1b
 
    mov r4,#1
2:
    mov r0,r4
    bl isPrime                      @ is prime ?
    cmp r0,#1
    bne 3f
    mov r0,r4
    ldr r1,iAdrsZoneConv
    bl conversion10                  @ call decimal conversion
    add r1,r0
    mov r5,#0
    strb r5,[r1]
    ldr r0,iAdrszMessResPrime
    ldr r1,iAdrsZoneConv             @ insert value conversion in message
    bl strInsertAtCharInc
    bl affichageMess
 
3:
    add r4,r4,#1
    cmp r4,#MAXI
    blt 2b
 
100:                                  @ standard end of the program 
    mov r0, #0                        @ return code
    mov r7, #EXIT                     @ request to exit program
    svc #0                            @ perform the system call
 
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsZoneConv:            .int sZoneConv
iAdriTabCoef:             .int iTabCoef
iAdrszMessResPrime:       .int szMessResPrime
/***************************************************/
/*     display coefficients                        */
/***************************************************/
// r0 contains a number
displayCoef:
    push {r1-r6,lr}             @ save  registers 
    mov r2,r0
    ldr r1,iAdrsZoneConv        @ 
    bl conversion10             @ call decimal conversion
    add r1,r0
    mov r5,#0
    strb r5,[r1]
    ldr r0,iAdrszMessResult
    ldr r1,iAdrsZoneConv        @ insert value conversion in message
    bl strInsertAtCharInc
    bl affichageMess
    ldr r3,iAdriTabCoef
1:
    ldr r0,[r3,r2,lsl #2]
    ldr r1,iAdrsZoneConv        @ 
    bl conversion10S            @ call decimal conversion
2:                              @ removing spaces
    ldrb r6,[r1]
    cmp r6,#' '
    addeq r1,#1
    beq 2b
 
    ldr r0,iAdrszMessResult1
    bl strInsertAtCharInc
    mov r4,r0
    mov r0,r2
    ldr r1,iAdrsZoneConv        @ else display odd message
    bl conversion10             @ call decimal conversion
    add r1,r0
    mov r5,#0
    strb r5,[r1]
    mov r0,r4
    ldr r1,iAdrsZoneConv        @ insert value conversion in message
    bl strInsertAtCharInc
    bl affichageMess
    subs r2,r2,#1
    bge 1b
 
    ldr r0,iAdrszCarriageReturn
    bl affichageMess
100:
    pop {r1-r6,lr}             @ restaur registers
    bx lr                      @ return
iAdrszMessResult:    .int szMessResult
iAdrszMessResult1:   .int szMessResult1
/***************************************************/
/*     compute coefficient               */
/***************************************************/
// r0 contains a number
computeCoef:
    push {r1-r6,lr}             @ save  registers 
    ldr r1,iAdriTabCoef         @ address coefficient array
    mov r2,#1
    str r2,[r1]                 @ store 1 to coeff [0]
    mov r3,#0                   @ indice 1
1:
    add r4,r3,#1
    mov r5,#1
    str r5,[r1,r4,lsl #2]
    mov r6,r3                   @ indice 2 = indice 1
2:
    cmp r6,#0                   @ zero ? -> end loop
    ble 3f
    sub r4,r6,#1
    ldr r5,[r1,r4,lsl #2]
    ldr r4,[r1,r6,lsl #2]
    sub r5,r5,r4
    str r5,[r1,r6,lsl #2]
    sub r6,r6,#1
    b 2b
3:
    ldr r2,[r1]                 @ inversion coeff [0]
    neg r2,r2
    str r2,[r1]
    add r3,r3,#1
    cmp r3,r0
    blt 1b
 
100:
    pop {r1-r6,lr}             @ restaur registers
    bx lr                      @ return
/***************************************************/
/*     verify number is prime              */
/***************************************************/
// r0 contains a number
isPrime:
    push {r1-r5,lr}             @ save  registers 
    bl computeCoef
    ldr r4,iAdriTabCoef         @ address coefficient array
    ldr r2,[r4]
    add r2,r2,#1
    str r2,[r4]
    ldr r2,[r4,r0,lsl #2]
    sub r2,r2,#1
    str r2,[r4,r0,lsl #2]
    mov r5,r0                  @ number start
    mov r1,r0                  @ divisor
1:
    ldr r0,[r4,r5,lsl #2]      @ load one coeff
    cmp r0,#0                  @ if negative inversion
    neglt r0,r0
    bl division                @ because this routine is number positive only
    cmp r3,#0                  @ remainder = zéro ?
    movne r0,#0                @  if <> no prime
    bne 100f
    subs r5,r5,#1              @ next coef
    bgt 1b
    mov r0,#1                  @ prime
 
100:
    pop {r1-r5,lr}             @ restaur registers
    bx lr                      @ return
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
 