Miller–Rabin primality test: Difference between revisions
Content added Content deleted
m (Minor reformatting.) |
VincentARM (talk | contribs) (add task to arm assembly raspberry pi) |
||
Line 352: | Line 352: | ||
937 941 947 953 967 971 977 983 991 997 |
937 941 947 953 967 971 977 983 991 997 |
||
</pre> |
</pre> |
||
=={{header|ARM Assembly}}== |
|||
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}} |
|||
<syntaxhighlight lang ARM Assembly> |
|||
/* 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" |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
Program 32 bits start |
|||
4294967271 is not prime !!!. |
|||
4294967273 is not prime !!!. |
|||
4294967275 is not prime !!!. |
|||
4294967277 is not prime !!!. |
|||
4294967279 is prime !!!. |
|||
4294967281 is not prime !!!. |
|||
4294967283 is not prime !!!. |
|||
4294967285 is not prime !!!. |
|||
4294967287 is not prime !!!. |
|||
4294967289 is not prime !!!. |
|||
4294967291 is prime !!!. |
|||
4294967293 is not prime !!!. |
|||
4294967295 is not prime !!!. |
|||
Program normal end. |
|||
</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
ahk forum: [http://www.autohotkey.com/forum/post-276712.html#276712 discussion] |
ahk forum: [http://www.autohotkey.com/forum/post-276712.html#276712 discussion] |