How to resolve the algorithm Miller–Rabin primality test step by step in the ARM Assembly programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Miller–Rabin primality test step by step in the ARM Assembly programming language
Table of Contents
Problem Statement
The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime or not. The algorithm, as modified by Michael O. Rabin to avoid the generalized Riemann hypothesis, is a probabilistic algorithm. The pseudocode, from Wikipedia is:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Miller–Rabin primality test step by step in the ARM Assembly programming language
Source code in the arm programming language
/* ARM assembly Raspberry PI */
/* program testmiller.s */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes */
/************************************/
.include "../constantes.inc"
.equ NBDIVISORS, 2000
//.include "../../ficmacros32.inc" @ use for developper debugging
/*******************************************/
/* Initialized data */
/*******************************************/
.data
szMessStartPgm: .asciz "Program 32 bits start \n"
szMessEndPgm: .asciz "Program normal end.\n"
szMessErrorArea: .asciz "\033[31mError : area divisors too small.\n"
szMessPrime: .asciz " is prime !!!.\n"
szMessNotPrime: .asciz " is not prime !!!.\n"
szCarriageReturn: .asciz "\n"
.align 4
iGraine: .int 123456
/*******************************************/
/* UnInitialized data */
/*******************************************/
.bss
.align 4
sZoneConv: .skip 24
/*******************************************/
/* code section */
/*******************************************/
.text
.global main
main: @ program start
ldr r0,iAdrszMessStartPgm @ display start message
bl affichageMess
ldr r4,iStart @ start number
ldr r5,iLimit @ end number
tst r4,#1
addeq r4,#1 @ start with odd number
1:
mov r0,r4
ldr r1,iAdrsZoneConv
bl conversion10 @ decimal conversion
ldr r0,iAdrsZoneConv
bl affichageMess
mov r0,r4
bl isPrimeMiller @ test miller rabin
cmp r0,#0
beq 2f
ldr r0,iAdrszMessPrime
bl affichageMess
b 3f
2:
ldr r0,iAdrszMessNotPrime
bl affichageMess
3:
add r4,r4,#2
cmp r4,r5
ble 1b
ldr r0,iAdrszMessEndPgm @ display end message
bl affichageMess
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc 0 @ perform system call
iAdrszMessStartPgm: .int szMessStartPgm
iAdrszMessEndPgm: .int szMessEndPgm
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsZoneConv: .int sZoneConv
iAdrszMessPrime: .int szMessPrime
iAdrszMessNotPrime: .int szMessNotPrime
iStart: .int 4294967270
iLimit: .int 4294967295
/***************************************************/
/* check if a number is prime test miller rabin */
/***************************************************/
/* r0 contains the number */
/* r0 return 1 if prime 0 else */
@2147483647
@4294967297
@131071
isPrimeMiller:
push {r1-r6,lr} @ save registers
cmp r0,#1 @ control 0 or 1
movls r0,#0
bls 100f
cmp r0,#2 @ control = 2
moveq r0,#1
beq 100f
tst r0,#1
moveq r0,#0 @ even
beq 100f
mov r1,#5 @ loop number
bl testMiller
100:
pop {r1-r6,pc}
/***************************************************/
/* test miller rabin algorithme wikipedia */
/* unsigned */
/***************************************************/
/* r0 contains number */
/* r1 contains parameter */
/* r0 return 1 if prime 0 if composite */
testMiller:
push {r1-r9,lr} @ save registers
mov r4,r0 @ N
mov r7,r1 @ loop maxi
sub r3,r0,#1 @ D
mov r2,#2
mov r6,#0 @ S
1: @ compute D * 2 power S
lsr r3,#1 @ D= D/2
add r6,r6,#1 @ increment S
tst r3,#1 @ D even ?
beq 1b
2:
mov r8,#0 @ loop counter
sub r5,r0,#3
3:
mov r0,r5
bl genereraleas
add r0,r0,#2 @ alea (entre 2 et n-1)
mov r1,r3 @ exposant = D
mov r2,r4 @ modulo N
bl moduloPuR32
cmp r0,#1
beq 5f
sub r1,r4,#1 @ n -1
cmp r0,r1
beq 5f
sub r9,r6,#1 @ S - 1
4:
mov r2,r0
umull r0,r1,r2,r0 @ compute square
mov r2,r4 @ and compute modulo N
bl division32R2023
mov r0,r2
cmp r0,#1
moveq r0,#0 @ composite
beq 100f
sub r1,r4,#1 @ n -1
cmp r0,r1
beq 5f
subs r9,r9,#1
bge 4b
mov r0,#0 @ composite
b 100f
5:
add r8,r8,#1
cmp r8,r7
blt 3b
mov r0,#1 @ prime
100:
pop {r1-r9,pc}
/********************************************************/
/* Calcul modulo de b puissance e modulo m */
/* Exemple 4 puissance 13 modulo 497 = 445 */
/* */
/********************************************************/
/* r0 nombre */
/* r1 exposant */
/* r2 modulo */
/* r0 return result */
moduloPuR32:
push {r1-r6,lr} @ save registers
cmp r0,#0 @ control <> zero
beq 100f
cmp r2,#0 @ control <> zero
beq 100f
1:
mov r4,r2 @ save modulo
mov r5,r1 @ save exposant
mov r6,r0 @ save base
mov r3,#1 @ start result
mov r1,#0 @ division r0,r1 by r2
bl division32R2023
mov r6,r2 @ base <- remainder
2:
tst r5,#1 @ exposant even or odd
beq 3f
umull r0,r1,r6,r3 @ multiplication base
mov r2,r4 @ and compute modulo N
bl division32R2023
mov r3,r2 @ result <- remainder
3:
umull r0,r1,r6,r6 @ compute base square
mov r2,r4 @ and compute modulo N
bl division32R2023
mov r6,r2 @ base <- remainder
lsr r5,#1 @ left shift 1 bit
cmp r5,#0 @ end ?
bne 2b
mov r0,r3
100:
pop {r1-r6,pc}
/***************************************************/
/* division number 64 bits in 2 registers by number 32 bits */
/* unsigned */
/***************************************************/
/* r0 contains lower part dividende */
/* r1 contains upper part dividende */
/* r2 contains divisor */
/* r0 return lower part quotient */
/* r1 return upper part quotient */
/* r2 return remainder */
division32R2023:
push {r3-r6,lr} @ save registers
mov r4,r2 @ save divisor
mov r5,#0 @ init upper part divisor
mov r2,r0 @ save dividende
mov r3,r1
mov r0,#0 @ init result
mov r1,#0
mov r6,#0 @ init shift counter
1: @ loop shift divisor
cmp r5,#0 @ upper divisor <0
blt 2f
cmp r5,r3
cmpeq r4,r2
bhs 2f @ new divisor > dividende
lsl r5,#1 @ shift left one bit upper divisor
lsls r4,#1 @ shift left one bit lower divisor
orrcs r5,r5,#1 @ move bit 31 lower on upper
add r6,r6,#1 @ increment shift counter
b 1b
2: @ loop 2
lsl r1,#1 @ shift left one bit upper quotient
lsls r0,#1 @ shift left one bit lower quotient
orrcs r1,#1 @ move bit 31 lower on upper
cmp r5,r3 @ compare divisor and dividende
cmpeq r4,r2
bhi 3f
subs r2,r2,r4 @ < sub divisor from dividende lower
sbc r3,r3,r5 @ and upper
orr r0,r0,#1 @ move 1 on quotient
3:
lsr r4,r4,#1 @ shift right one bit upper divisor
lsrs r5,#1 @ and lower
orrcs r4,#0x80000000 @ move bit 0 upper to 31 bit lower
subs r6,#1 @ decrement shift counter
bge 2b @ if > 0 loop 2
100:
pop {r3-r6,pc}
/***************************************************/
/* Generation random number */
/***************************************************/
/* r0 contains limit */
genereraleas:
push {r1-r4,lr} @ save registers
ldr r4,iAdriGraine
ldr r2,[r4]
ldr r3,iNbDep1
mul r2,r3,r2
ldr r3,iNbDep1
add r2,r2,r3
str r2,[r4] @ save seed for next call
cmp r0,#0
beq 100f
mov r1,r0 @ divisor
mov r0,r2 @ dividende
bl division
mov r0,r3 @ résult = remainder
100: @ end function
pop {r1-r4,pc} @ restaur registers
iAdriGraine: .int iGraine
iNbDep1: .int 0x343FD
iNbDep2: .int 0x269EC3
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
You may also check:How to resolve the algorithm Long multiplication step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Bézier curves/Intersections step by step in the Phix programming language
You may also check:How to resolve the algorithm Mutual recursion step by step in the Sather programming language
You may also check:How to resolve the algorithm Comments step by step in the Rockstar programming language
You may also check:How to resolve the algorithm Haversine formula step by step in the FunL programming language