Tonelli-Shanks algorithm: Difference between revisions
Content added Content deleted
(add task to aarch64 assembly raspberry pi) |
(add task to arm assembly raspberry pi or android 32 bits) |
||
Line 524: | Line 524: | ||
Program normal end. |
Program normal end. |
||
</pre> |
</pre> |
||
=={{header|ARM Assembly}}== |
|||
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}} |
|||
<lang ARM Assembly> |
|||
/* ARM assembly Raspberry PI or android 32 bits */ |
|||
/* program tonshan.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" |
|||
/*******************************************/ |
|||
/* Initialized data */ |
|||
/*******************************************/ |
|||
.data |
|||
szMessStartPgm: .asciz "Program 32 bits start \n" |
|||
szMessEndPgm: .asciz "Program normal end.\n" |
|||
szMessError: .asciz "\033[31mError !!!\n" |
|||
szMessErrGen: .asciz "Error end program.\n" |
|||
szMessOverflow: .asciz "Overflow function modulo.\n" |
|||
szMessNoSolution: .asciz "No solution.\n" |
|||
szCarriageReturn: .asciz "\n" |
|||
/* datas message display */ |
|||
szMessEntry: .asciz "Number : @ modulo : @ ==> " |
|||
szMessResult: .asciz "Racine 1 : @ Racine 2 : @ \n" |
|||
iNumberN: .int 1030 |
|||
iNumberP: .int 10009 |
|||
iNumberN1: .int 1032 |
|||
iNumberP1: .int 10009 |
|||
iNumberN2: .int 44402 |
|||
iNumberP2: .int 100049 |
|||
/*******************************************/ |
|||
/* UnInitialized data */ |
|||
/*******************************************/ |
|||
.bss |
|||
.align 4 |
|||
sZoneConv: .skip 24 |
|||
/*******************************************/ |
|||
/* code section */ |
|||
/*******************************************/ |
|||
.text |
|||
.global main |
|||
main: // program start |
|||
ldr r0,iAdrszMessStartPgm // display start message |
|||
bl affichageMess |
|||
mov r0,#10 |
|||
mov r1,#13 |
|||
bl displayEntry // display entry number |
|||
bl computeTonSha // compute roots |
|||
bl displayResult // display roots |
|||
mov r0,#56 |
|||
mov r1,#101 |
|||
bl displayEntry |
|||
bl computeTonSha |
|||
bl displayResult |
|||
ldr r4,iAdriNumberN |
|||
ldr r0,[r4] |
|||
ldr r4,iAdriNumberP |
|||
ldr r1,[r4] |
|||
bl displayEntry |
|||
bl computeTonSha |
|||
bl displayResult |
|||
ldr r4,iAdriNumberN1 |
|||
ldr r0,[r4] |
|||
ldr r4,iAdriNumberP1 |
|||
ldr r1,[r4] |
|||
bl displayEntry |
|||
bl computeTonSha |
|||
bcs 1f |
|||
bl displayResult |
|||
1: |
|||
ldr r4,iAdriNumberN2 |
|||
ldr r0,[r4] |
|||
ldr r4,iAdriNumberP2 |
|||
ldr r1,[r4] |
|||
bl displayEntry |
|||
bl computeTonSha |
|||
bl displayResult |
|||
ldr r0,iAdrszMessEndPgm // display end message |
|||
bl affichageMess |
|||
b 100f |
|||
99: // display error message |
|||
ldr r0,iAdrszMessError |
|||
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 |
|||
iAdrszMessError: .int szMessError |
|||
iAdrszMessNoSolution: .int szMessNoSolution |
|||
iAdrszCarriageReturn: .int szCarriageReturn |
|||
iAdriNumberN: .int iNumberN |
|||
iAdriNumberP: .int iNumberP |
|||
iAdriNumberN1: .int iNumberN1 |
|||
iAdriNumberP1: .int iNumberP1 |
|||
iAdriNumberN2: .int iNumberN2 |
|||
iAdriNumberP2: .int iNumberP2 |
|||
iAdrszMessResult: .int szMessResult |
|||
iAdrsZoneConv: .int sZoneConv |
|||
/******************************************************************/ |
|||
/* algorithm Tonelli–Shanks */ |
|||
/******************************************************************/ |
|||
/* r0 contains number */ |
|||
/* r1 contains modulus */ |
|||
/* r0 return root 1 */ |
|||
/* r1 return root 2 */ |
|||
computeTonSha: |
|||
push {r2-r12,lr} |
|||
mov r9,r0 // save number |
|||
mov r10,r1 // save modulo p |
|||
mov r2,r10 |
|||
sub r1,r2,#1 |
|||
lsr r1,r1,#1 |
|||
bl moduloPuR32 |
|||
cmp r0,#1 |
|||
bne 20f |
|||
sub r5,r10,#1 |
|||
mov r6,#1 // s |
|||
1: |
|||
lsr r5,r5,#1 // div by 2 |
|||
tst r5,#1 // even ? |
|||
addeq r6,#1 |
|||
beq 1b // and loop |
|||
// r5 = q |
|||
cmp r6,#1 // s = 1 ? |
|||
bne 3f |
|||
add r1,r10,#1 // compute root 1 |
|||
lsr r1,r1,#2 // p + 1 / 4 |
|||
mov r0,r9 // n |
|||
mov r2,r10 // p |
|||
bl moduloPuR32 |
|||
neg r1,r0 // compute root 2 = - root 1 |
|||
b 100f // and end |
|||
3: |
|||
mov r7,#3 // z |
|||
4: |
|||
mov r0,r7 |
|||
mov r2,r10 // p |
|||
sub r1,r2,#1 |
|||
lsr r1,r1,#1 // power = p - 1 / 2 |
|||
bl moduloPuR32 |
|||
cmp r0,#1 |
|||
addeq r7,#2 |
|||
beq 4b |
|||
cmp r0,#0 |
|||
addeq r7,#2 |
|||
beq 4b |
|||
mov r0,r7 // z |
|||
mov r1,r5 // q |
|||
mov r2,r10 // p |
|||
bl moduloPuR32 |
|||
mov r12,r0 // c = z pow q mod p |
|||
add r1,r5,#1 // = q +1 |
|||
lsr r1,r1,#1 // div 2 |
|||
mov r0,r9 // n |
|||
mov r2,r10 // p |
|||
bl moduloPuR32 |
|||
mov r4,r0 // r = n puis (q+1)/2 mod p |
|||
mov r0,r9 // n |
|||
mov r1,r5 // = q |
|||
mov r2,r10 // p |
|||
bl moduloPuR32 |
|||
mov r5,r0 // reuse r5 = t = n pow q mod p |
|||
8: // begin loop |
|||
cmp r5,#1 |
|||
beq 10f |
|||
mov r0,r5 // t |
|||
mov r1,r6 // m |
|||
mov r2,r10 // p |
|||
bl searchI // search i for t puis 2 puis i = 1 mod p |
|||
cmp r0,#-1 // not find -> no solution |
|||
beq 20f |
|||
mov r9,r0 // i |
|||
sub r8,r6,r0 // compute b |
|||
sub r8,r8,#1 // m - i - 1 |
|||
mov r1,#1 |
|||
lsl r1,r1,r8 |
|||
mov r0,r12 |
|||
mov r2,r10 // p |
|||
bl moduloPuR32 |
|||
mov r7,r0 // b = c puis 2 puis 2 puis m-i-1 à verifier |
|||
umull r0,r1,r7,r4 // r = r * b mod p |
|||
mov r2,r10 |
|||
bl division32R |
|||
mov r4,r2 // r mod p |
|||
umull r0,r1,r7,r7 |
|||
mov r2,r10 |
|||
bl division32R |
|||
mov r12,r2 // c mod p |
|||
umull r0,r1,r5,r12 |
|||
mov r2,r10 |
|||
bl division32R |
|||
mov r5,r2 // t mod p |
|||
mov r6,r9 // m = i |
|||
b 8b |
|||
9: |
|||
10: |
|||
mov r0,r4 // r0 return root 1 |
|||
sub r1,r10,r0 // r1 return root 2 |
|||
cmn r0,#0 // carry à zero roots ok |
|||
b 100f |
|||
20: |
|||
ldr r0,iAdrszMessNoSolution |
|||
bl affichageMess |
|||
mov r0,#0 |
|||
mov r1,#0 |
|||
cmp r0,#0 // carry to 1 No solution |
|||
100: |
|||
pop {r2-r12,lr} // restaur registers |
|||
bx lr // return |
|||
/******************************************************************/ |
|||
/* search i */ |
|||
/******************************************************************/ |
|||
// r0 contains t |
|||
// r1 contains maxi |
|||
// r2 contains modulo |
|||
// r0 return i |
|||
searchI: |
|||
push {r1-r6,lr} |
|||
mov r4,r0 // t |
|||
mov r6,r1 // m |
|||
mov r3,#1 // i |
|||
1: |
|||
mov r5,#1 |
|||
lsl r5,r5,r3 // compute 2 power i |
|||
mov r0,r4 |
|||
mov r1,r5 |
|||
bl moduloPuR32 // compute t pow 2 pow i mod p |
|||
cmp r0,#1 // = 1 ? |
|||
beq 3f // yes it is ok |
|||
add r3,r3,#1 // next i |
|||
cmp r3,r6 |
|||
blt 1b // loop |
|||
mov r0,#-1 // not find |
|||
b 100f |
|||
3: |
|||
mov r0,r3 // return i |
|||
100: |
|||
pop {r1-r6,lr} // restaur registers |
|||
bx lr // return |
|||
/******************************************************************/ |
|||
/* display numbers */ |
|||
/******************************************************************/ |
|||
/* r0 contains number */ |
|||
/* r1 contains modulo */ |
|||
displayEntry: |
|||
push {r0-r3,lr} |
|||
mov r2,r1 // root 2 |
|||
ldr r1,iAdrsZoneConv // convert root 1 in r0 |
|||
bl conversion10S // convert ascii string |
|||
ldr r0,iAdrszMessEntry |
|||
ldr r1,iAdrsZoneConv |
|||
bl strInsertAtCharInc // and put in message |
|||
mov r3,r0 |
|||
mov r0,r2 // racine 2 |
|||
ldr r1,iAdrsZoneConv |
|||
bl conversion10S // convert ascii string |
|||
mov r0,r3 |
|||
ldr r1,iAdrsZoneConv |
|||
bl strInsertAtCharInc // and put in message |
|||
bl affichageMess |
|||
100: |
|||
pop {r0-r3,lr} // restaur registers |
|||
bx lr // return |
|||
iAdrszMessEntry: .int szMessEntry |
|||
/******************************************************************/ |
|||
/* display roots */ |
|||
/******************************************************************/ |
|||
/* r0 contains root 1 */ |
|||
/* r1 contains root 2 */ |
|||
displayResult: |
|||
push {r1-r3,lr} |
|||
mov r2,r1 // root 2 |
|||
ldr r1,iAdrsZoneConv // convert root 1 in r0 |
|||
bl conversion10S // convert ascii string |
|||
ldr r0,iAdrszMessResult |
|||
ldr r1,iAdrsZoneConv |
|||
bl strInsertAtCharInc // and put in message |
|||
mov r3,r0 |
|||
mov r0,r2 // racine 2 |
|||
ldr r1,iAdrsZoneConv |
|||
bl conversion10S // convert ascii string |
|||
mov r0,r3 |
|||
ldr r1,iAdrsZoneConv |
|||
bl strInsertAtCharInc // and put in message |
|||
bl affichageMess |
|||
100: |
|||
pop {r1-r3,lr} // restaur registers |
|||
bx lr // return |
|||
/********************************************************/ |
|||
/* 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-r7,lr} @ save registers |
|||
cmp r0,#0 @ verif <> zero |
|||
beq 90f |
|||
cmp r1,#0 @ verif <> zero |
|||
moveq r0,#0 |
|||
beq 90f |
|||
cmp r2,#0 @ verif <> zero |
|||
moveq r0,#0 |
|||
beq 90f @ |
|||
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 de r0,r1 par r2 |
|||
bl division32R |
|||
mov r6,r2 @ base <- remainder |
|||
2: |
|||
tst r5,#1 @ exposant even or odd |
|||
beq 3f |
|||
umull r0,r1,r6,r3 |
|||
mov r2,r4 |
|||
bl division32R |
|||
mov r3,r2 @ result <- remainder |
|||
3: |
|||
umull r0,r1,r6,r6 |
|||
mov r2,r4 |
|||
bl division32R |
|||
mov r6,r2 @ base <- remainder |
|||
lsr r5,#1 @ left shift 1 bit |
|||
cmp r5,#0 @ end ? |
|||
bne 2b |
|||
mov r0,r3 |
|||
90: |
|||
cmn r0,#0 @ no error |
|||
100: @ fin standard de la fonction |
|||
pop {r1-r7,lr} @ restaur des registres |
|||
bx lr @ retour de la fonction en utilisant lr |
|||
/***************************************************/ |
|||
/* division number 64 bits in 2 registers by number 32 bits */ |
|||
/***************************************************/ |
|||
/* 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 */ |
|||
division32R: |
|||
push {r3-r9,lr} @ save registers |
|||
mov r6,#0 @ init upper upper part remainder !! |
|||
mov r7,r1 @ init upper part remainder with upper part dividende |
|||
mov r8,r0 @ init lower part remainder with lower part dividende |
|||
mov r9,#0 @ upper part quotient |
|||
mov r4,#0 @ lower part quotient |
|||
mov r5,#32 @ bits number |
|||
1: @ begin loop |
|||
lsl r6,#1 @ shift upper upper part remainder |
|||
lsls r7,#1 @ shift upper part remainder |
|||
orrcs r6,#1 |
|||
lsls r8,#1 @ shift lower part remainder |
|||
orrcs r7,#1 |
|||
lsls r4,#1 @ shift lower part quotient |
|||
lsl r9,#1 @ shift upper part quotient |
|||
orrcs r9,#1 |
|||
@ divisor sustract upper part remainder |
|||
subs r7,r2 |
|||
sbcs r6,#0 @ and substract carry |
|||
bmi 2f @ négative ? |
|||
@ positive or equal |
|||
orr r4,#1 @ 1 -> right bit quotient |
|||
b 3f |
|||
2: @ negative |
|||
orr r4,#0 @ 0 -> right bit quotient |
|||
adds r7,r2 @ and restaur remainder |
|||
adc r6,#0 |
|||
3: |
|||
subs r5,#1 @ decrement bit size |
|||
bgt 1b @ end ? |
|||
mov r0,r4 @ lower part quotient |
|||
mov r1,r9 @ upper part quotient |
|||
mov r2,r7 @ remainder |
|||
100: @ function end |
|||
pop {r3-r9,lr} @ restaur registers |
|||
bx lr |
|||
/***************************************************/ |
|||
/* ROUTINES INCLUDE */ |
|||
/***************************************************/ |
|||
.include "../affichage.inc" |
|||
</lang> |
|||
{{Output}} |
|||
<pre> |
|||
Program 32 bits start |
|||
Number : +10 modulo : +13 ==> Racine 1 : +7 Racine 2 : +6 |
|||
Number : +56 modulo : +101 ==> Racine 1 : +37 Racine 2 : +64 |
|||
Number : +1030 modulo : +10009 ==> Racine 1 : +1632 Racine 2 : +8377 |
|||
Number : +1032 modulo : +10009 ==> No solution. |
|||
Number : +44402 modulo : +100049 ==> Racine 1 : +30468 Racine 2 : +69581 |
|||
Program normal end. |
|||
</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
{{trans|C#}} |
{{trans|C#}} |