FASM – Prime Number Tester

This program uses Fermats Primality Test to test whether an input number is prime or not. It was written in x86 assembly language using the Flat Assembler (FASM).

Fermats Primality Test

For a number p to be considered prime, it must pass the following tests for some integer a:

GCD(a,p) = 1

a^p-1 mod p = 1

This test is not perfect. So called base-a pseudoprimes will pass for certain values of a. However these values are rare and can be eliminated by testing against multiple values of a. There is also a class of numbers known as Carmichael Numbers which are not prime, but which will pass the above tests for all possible values of a. However, the probability of encountering Carmichael Numbers is very low.

Usage

Enter the value to be tested in either decimal or hexadecimal form. Then press the [Test Decimal] or [Test Hexadecimal] button. These buttons can be pressed multiple times for the same input to test against multiple values of a.

The x86 Source Code

To grab this code, select it with the mouse and copy it. It can then be pasted directly into the FASM IDE.

; ------------------------------------------------------------------------------------- format PE GUI 4.0 entry start include 'win32a.inc' ; ------------------------------------------------------------------------------------- IDD_THE_DIALOG = 102 IDC_INPUT = 1000 IDC_OUTPUT = 1001 IDC_BTN_TEST_DEC = 1002 IDC_BTN_TEST_HEX = 1003 ; ------------------------------------------------------------------------------------- HEX_LEN = 400 DBL_HEX_LEN = 2*HEX_LEN ; ------------------------------------------------------------------------------------- section '.code' code readable executable start: invoke GetModuleHandle,0 invoke DialogBoxParam,eax,IDD_THE_DIALOG,0,DialogProc,0 exit: invoke ExitProcess,0 ; ------------------------------------------------------------------------------------- proc DialogProc uses esi edi ebx,hwnddlg,msg,wparam,lparam cmp [msg],WM_INITDIALOG je .wminitdialog cmp [msg],WM_COMMAND je .wmcommand cmp [msg],WM_CLOSE je .wmclose xor eax,eax jmp .quit .wminitdialog: invoke SetDlgItemText,[hwnddlg],IDC_INPUT,"" invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,"" jmp .done .wmcommand: cmp [wparam], BN_CLICKED shl 16 + IDC_BTN_TEST_DEC je .TEST_DEC cmp [wparam], BN_CLICKED shl 16 + IDC_BTN_TEST_HEX je .TEST_HEX jmp .done .TEST_DEC: invoke GetDlgItemText,[hwnddlg],IDC_INPUT,bfDisplay,1200 stdcall GetTestPrimeDecimal invoke SetDlgItemText,[hwnddlg],IDC_INPUT,bfDisplay stdcall Test_Prime stdcall PrintResult invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay jmp .done .TEST_HEX: invoke GetDlgItemText,[hwnddlg],IDC_INPUT,bfDisplay,1200 stdcall GetTestPrime stdcall PrintTestPrime invoke SetDlgItemText,[hwnddlg],IDC_INPUT,bfDisplay stdcall Test_Prime stdcall PrintResult invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay jmp .done .wmclose: invoke EndDialog,[hwnddlg],0 .done: mov eax,1 .quit: ret endp ; ------------------------------------------------------------------------------------- macro PRINT_CRLF { mov [edi],byte 13 inc edi mov [edi],byte 10 inc edi } ; ------------------------------------------------------------------------------------- proc GetTestPrime ; get the input value stdcall FilterNonHex stdcall HexStrToNumber ret endp ; ------------------------------------------------------------------------------------- proc GetTestPrimeDecimal ; get the decimal input value stdcall FilterNonDec stdcall DecStrToNumber ret endp ; ------------------------------------------------------------------------------------- proc PrintTestPrime ; print the test prime lea edi,[bfDisplay] lea esi,[TestPrime] stdcall PrintHexValue mov [edi],byte 0 ret endp ; ------------------------------------------------------------------------------------- proc PrintResult ; print the results lea edi,[bfDisplay] ; print the random base value lea esi,[szMsg_1] stdcall AddStringToEDI PRINT_CRLF PRINT_CRLF lea esi,[BaseBf] stdcall PrintHexValue PRINT_CRLF PRINT_CRLF ; print result of GCD test lea esi,[szMsg_2] stdcall AddStringToEDI lea esi,[szPassed] cmp [GCD_Passed],byte 1 je .GCD lea esi,[szFailed] .GCD: stdcall AddStringToEDI PRINT_CRLF PRINT_CRLF ; print result of mod exp test lea esi,[szMsg_3] stdcall AddStringToEDI lea esi,[szPassed] cmp [MEXP_Passed],byte 1 je .MEXP lea esi,[szFailed] .MEXP: stdcall AddStringToEDI PRINT_CRLF PRINT_CRLF ; null terminate bfDisplay mov [edi],byte 0 ret endp ; ------------------------------------------------------------------------------------- proc PrintHexValue uses ecx eax ; ESI and EDI set outside of this procedure locals count db 0 endl ; find the first non zero dword in the hex value ; starting from the high dword mov cx,HEX_LEN-4 add esi,HEX_LEN-4 .FIND: mov eax,[esi] cmp eax,0 jne .PRINT sub esi,4 sub cx,4 jcxz .PRINT jmp .FIND .PRINT: mov eax,[esi] ; dword to 8 digits stdcall DWordToStr jcxz .DONE sub cx,4 sub esi,4 inc [count] ; add a CRLF to the output string after every 8 dwords cmp [count],byte 8 je .ADD_CRLF jmp .PRINT .ADD_CRLF: mov [count],byte 0 PRINT_CRLF jmp .PRINT .DONE: ret endp ; ------------------------------------------------------------------------------------- proc WordToStr uses edx ; print a word (2 bytes) to a string ; word passed in AX ; EDI set outside of this function mov dx,ax mov al,ah stdcall ByteToDigits mov [edi],ah inc edi mov [edi],al inc edi mov al,dl stdcall ByteToDigits mov [edi],ah inc edi mov [edi],al inc edi ret endp ; ------------------------------------------------------------------------------------- proc DWordToStr ; print a dword (4 bytes) to a string ; word passed in EAX ; EDI set outside of this function locals tmp dw 0 endl mov word [tmp],ax shr eax,16 stdcall WordToStr mov ax,word [tmp] stdcall WordToStr ; add a space mov [edi],byte 32 inc edi ret endp ; ------------------------------------------------------------------------------------- proc HexDigitToValue ; convert a hex digit to a 4 bit value ; input in AL - output in AL ; is AL in the range: 48 - 57 (0 - 9) ? cmp al,48 jl .NOT_HEX cmp al,57 jg .A_Z sub al,48 jmp .DONE .A_Z: ; is AL in the range: 65 - 70 (A - B) ? cmp al,65 jl .NOT_HEX cmp al,70 jg .a_z sub al,55 jmp .DONE .a_z: ; is AL in the range: 97 - 102 (a - b) ? cmp al,97 jl .NOT_HEX cmp al,102 jg .NOT_HEX sub al,87 jmp .DONE .NOT_HEX: ; set EAX to 0xffff if input is not a valid hex digit mov eax,0xffff .DONE: ret endp ; ------------------------------------------------------------------------------------- proc ByteToDigits ; convert 1 byte to 2 hex digits ; input in AL - output in AX ; copy AL to AH mov ah,al ; AH: get the upper 4 bits of the byte shr ah,4 ; nibble to hex digit add ah,48 cmp ah,57 jle .NEXT add ah,7 .NEXT: ; AL: get the lower 4 bits of the byte and al,0xf ; nibble to hex digit add al,48 cmp al,57 jle .DONE add al,7 .DONE: ; output is in AX ret endp ; ------------------------------------------------------------------------------------- proc HexStrToNumber uses esi edi ecx ; convert the hex string in bfDisplay to a hex value lea esi,[bfDisplay] lea edi,[TestPrime] stdcall ClearTestPrime ; count the digits in bfDisplay and save to AX stdcall CountDigits ; check if bfDisplay is empty cmp ax,0 je .DONE ; calculate the offset in bytes from the start of EDI ; based on the number of digits in bfDisplay (given by AX) xor ecx,ecx mov cx,ax shr cx,1 test ax,1 jnz .ODD .EVEN: ; bfDisplay contains an even number of hex digits ; offset = (nDigits/2) - 1 dec cx add edi,ecx jmp .GET_DIGITS .ODD: ; bfDisplay contains an odd number of hex digits ; offset = nDigits/2 ; convert the first digit add edi,ecx mov al,[esi] stdcall HexDigitToValue mov [edi],al inc esi dec edi dec cx cmp cx,0 jl .DONE .GET_DIGITS: ; convert 2 hex digits to 1 byte mov al,[esi] stdcall HexDigitToValue shl al,4 mov [edi],al inc esi mov al,[esi] stdcall HexDigitToValue or [edi],al inc esi dec cx cmp cx,0 jl .DONE dec edi jmp .GET_DIGITS .DONE: ret endp ; ------------------------------------------------------------------------------------- proc CountDigits uses esi ecx ; count the number of hex digits in the bfDisplay string mov ax,0 xor ecx,ecx lea esi,[bfDisplay] .COUNT: mov dl,[esi] cmp dl,0 je .DONE inc cx inc esi jmp .COUNT .DONE: ; return the digit count in AX mov ax,cx ret endp ; ------------------------------------------------------------------------------------- proc FilterNonHex uses esi edi ecx ; filter out any non hex digit characters from bfDisplay lea esi,[bfDisplay] lea edi,[bfDisplay] xor ecx,ecx .FILTER: mov al,[esi] ; 0 = null terminator cmp al,0 je .DONE cmp al,48 jl .NOT_HEX cmp al,57 jle .COPY cmp al,65 jl .NOT_HEX cmp al,70 jle .COPY cmp al,97 jl .NOT_HEX cmp al,102 jg .NOT_HEX .COPY: mov [edi],al inc edi inc ecx cmp ecx,800 jge .DONE .NOT_HEX: inc esi jmp .FILTER .DONE: ; null terminate the new string mov [edi],byte 0 ret endp ; ------------------------------------------------------------------------------------- proc DecStrToNumber uses esi edi ecx ; convert the hex string in bfDisplay to a hex value locals ndigits dw 0 endl lea esi,[bfDisplay] lea edi,[TestPrime] stdcall ClearTestPrime xor ecx,ecx .GET_DIGITS: mov dl,[esi+ecx] cmp dl,0 ; exit when the null terminator is found je .DONE stdcall TestPrimex10 sub dl,48 stdcall AddDecimalDigit inc word [ndigits] ; read a maximum of 963 decimal digits cmp [ndigits],word 963 je .DONE inc cx jmp .GET_DIGITS .DONE: ret endp ; ------------------------------------------------------------------------------------- proc FilterNonDec uses esi edi ecx ; filter out any non decimal digit characters from bfDisplay lea esi,[bfDisplay] lea edi,[bfDisplay] xor ecx,ecx .FILTER: mov al,[esi] ; 0 = null terminator cmp al,0 je .DONE cmp al,48 jl .NOT_DEC cmp al,57 jg .NOT_DEC .COPY: mov [edi],al inc edi inc ecx cmp ecx,963 jge .DONE .NOT_DEC: inc esi jmp .FILTER .DONE: ; null terminate the new string mov [edi],byte 0 ret endp ; ------------------------------------------------------------------------------------- proc AddDecimalDigit uses edi ecx ; add a decimal digit to the TestPrime value ; digit is passed in DL lea edi,[TestPrime] add [edi],dl jnc .DONE xor ecx,ecx mov cx,1 .ADD_C: add [edi+ecx],byte 1 jnc .DONE inc cx cmp cx,HEX_LEN jl .ADD_C .DONE: ret endp ; ------------------------------------------------------------------------------------- proc TestPrimex10 uses esi edi ecx ; multiply the TestPrime buffer by 10 lea esi,[TestPrime] lea edi,[TempBf] ; copy TestPrime to TempBf xor ecx,ecx .COPY: mov al,[esi+ecx] mov [edi+ecx],al inc cx cmp cx,HEX_LEN jl .COPY ; shift TempBf by 3 add edi,HEX_LEN-4 mov cx,HEX_LEN-4 .SHL_3: mov eax,dword [edi-4] shld dword [edi],eax,3 sub edi,4 sub cx,4 cmp cx,0 jg .SHL_3 shl dword [edi],3 ; shift TestPrime by 1 lea edi,[TestPrime] add edi,HEX_LEN-4 mov cx,HEX_LEN-4 .SHL_1: mov eax,dword [edi-4] shld dword [edi],eax,1 sub edi,4 sub cx,4 cmp cx,0 jg .SHL_1 shl dword [edi],1 ; add TempBf to TestPrime lea esi,[TempBf] lea edi,[TestPrime] xor ecx,ecx ; save CF from iteration to iteration ; init CF = 0 clc ; push flags register to the stack pushf .ADD: mov eax,dword [esi] ; get the flags register from the stack popf ; [EDI] = [EDI] + [ESI] + CF adc dword [edi],eax ; save the flags register to the stack, for the next iteration pushf ; these affect the CF, which is why it has to be saved to the stack add esi,4 add edi,4 add cx,4 ; cmp also affects the CF cmp cx,HEX_LEN jl .ADD ; clean up the stack popf ret endp ; ------------------------------------------------------------------------------------- proc ClearTestPrime uses edi ecx ; zero the test prime lea edi,[TestPrime] xor ecx,ecx .CLEAR: mov [edi+ecx],byte 0 inc cx cmp cx,400 jl .CLEAR ret endp ; ------------------------------------------------------------------------------------- proc Test_Prime uses esi edi ; test the candidate lea esi,[TestPrime] ; copy test prime to ModBf stdcall CopyToModBf ; copy test prime to ExpBf and decrement stdcall CopyToExpBf lea edi,[ExpBf] stdcall Decrement ; set BaseBf to a random value stdcall GetRandomBase ; the GCD test stdcall Calc_GCD stdcall Check_GCD_Passed ; the mod_exp test stdcall Mod_Exp stdcall Check_MEXP_Passed ret endp ; ------------------------------------------------------------------------------------- proc GetRandomBase uses esi edi ecx ; zero the Base lea edi,[BaseBf] xor ecx,ecx .ZERO: mov [edi+ecx],byte 0 inc cx cmp cx,HEX_LEN jl .ZERO .SEED: ; read the time stamp counter (into EDX:EAX) rdtsc ; use RNG Linear Congruential Generator ; X(n+1) = (aX(n) + c) mod m ; a = 0x19660D, c = 0x3C6EF35F, m = 0x100000000 ; X(0) = EAX - from rdtsc xor ecx,ecx .RAND: mov edx,dword 0x19660D ; multiply EAX by EDX mul edx ; result in EDX:EAX add eax,0x3C6EF35F ; copy to BaseBf mov [edi+ecx],eax add cx,4 cmp cx,HEX_LEN jl .RAND ; set BaseBf = BaseBf mod TestPrime lea esi,[BaseBf] stdcall CopyToProductBf lea esi,[TestPrime] stdcall CopyToShiftBf stdcall Modulus lea edi,[BaseBf] stdcall CopyFromProductBf stdcall CheckBaseBf ret endp ; ------------------------------------------------------------------------------------- proc CheckBaseBf uses edi ecx ; if BaseBf is less than 2, set it to 2 lea edi,[BaseBf] xor ecx,ecx mov cx,HEX_LEN-1 .TEST: cmp [edi+ecx],byte 0 jne .DONE dec cx cmp cx,0 jg .TEST cmp [edi],byte 2 jge .DONE mov [edi],byte 2 .DONE: ret endp ; ------------------------------------------------------------------------------------- proc CalcSum uses ecx ; Add two double sized hex numbers ; ESI and EDI are set outside of this procedure mov cx,0 ; save CF from iteration to iteration ; init CF = 0 clc ; push flags register to the stack pushf .SUM: mov eax,dword [esi] ; get the flags register from the stack popf ; [EDI] = [EDI] + [ESI] + CF adc dword [edi],eax ; save the flags register to the stack, for the next iteration pushf ; these affect the CF, which is why it has to be saved to the stack add esi,4 add edi,4 add cx,4 ; cmp also affects the CF cmp cx,DBL_HEX_LEN jl .SUM ; clean up the stack popf ret endp ; ------------------------------------------------------------------------------------- proc CalcDiff uses ecx ; Calc difference between two double sized hex numbers ; diff = dest - src ; ESI and EDI are set outside of this procedure mov cx,0 ; compute diff as: diff = dest + ~src + 1 ; the 1 is introduced by initialising CF to 1 ; save CF from iteration to iteration ; init CF = 1 stc ; push flags register to the stack pushf .SUB: mov eax,dword [esi] ; ~src here: not eax ; get the flags register from the stack popf ; [EDI] = [EDI] + ~[ESI] + CF adc dword [edi],eax ; save the flags register to the stack, for the next iteration pushf ; these affect the CF, which is why it has to be saved to the stack add esi,4 add edi,4 add cx,4 ; cmp also affects the CF cmp cx,DBL_HEX_LEN jl .SUB ; clean up the stack popf ret endp ; ------------------------------------------------------------------------------------- proc ShiftLeft uses ecx ; Shift dest number left by 1 bit ; EDI is set outside of this procedure ; start from the high order double word in the dest add edi,DBL_HEX_LEN-4 mov cx,DBL_HEX_LEN-4 .SHIFT: mov eax,dword [edi-4] shld dword [edi],eax,1 sub edi,4 sub cx,4 cmp cx,0 jg .SHIFT shl dword [edi],1 ret endp ; ------------------------------------------------------------------------------------- proc ShiftRight uses ecx ; Shift dest number right by 1 bit ; EDI is set outside of this procedure mov cx,0 .SHIFT: mov eax,dword [edi+4] shrd dword [edi],eax,1 add edi,4 add cx,4 cmp cx,DBL_HEX_LEN-4 jl .SHIFT shr dword [edi],1 ret endp ; ------------------------------------------------------------------------------------- proc Multiply uses edi ecx ; calculate ProductBf = ESI * ShiftBf ; ESI is set outside of this procedure locals nBit db 0 endl ; zero ProductBf stdcall ZeroProductBf ; ESI is a hex value of length HEX_LEN ; Algorithm: ; first find the byte in ESI containing the high order bit ; then starting from this byte, iterate through the bits in ESI ; start from the high order bit down to the low order bit ; for each iteration: ; (1) left shift ProductBf by 1 bit ; (2) test the bit ; (3) if the bit is set, add ShiftBf to ProductBf mov cx,HEX_LEN ; start from end of ESI (the highest byte) add esi,HEX_LEN-1 .FIND_HOB: cmp byte [esi],0 jne .FOUND dec esi dec cx cmp cx,0 je .QUIT jmp .FIND_HOB .FOUND: ; ESI now points to the byte that has the high order bit ; cx contains the byte number (index into A) mov [nBit],byte 7 ; load the byte at address ESI into BL for testing mov bl,byte [esi] .FIND_BIT: test bl,0x80 jnz .HO_BIT shl bl,1 dec [nBit] cmp [nBit],byte 0 jl .QUIT jmp .FIND_BIT .HO_BIT: ; the high order bit has been found ; initialise ProductBf stdcall AddShiftBfToProductBf .NEXT_BIT: ; get the next bit shl bl,1 dec [nBit] cmp [nBit],byte 0 jl .NEXT_BYTE jmp .SHIFT .NEXT_BYTE: ; get the next byte dec esi dec cx ; no more bytes when cx = 0 cmp cx,0 jle .QUIT mov [nBit],byte 7 mov bl,byte [esi] .SHIFT: ; shift ProductBf 1 bit to the left lea edi,[ProductBf] stdcall ShiftLeft ; test the current bit to see if an addition is required test bl,0x80 jz .NEXT_BIT .ADD: ; add to ProductBf stdcall AddShiftBfToProductBf jmp .NEXT_BIT .QUIT: ret endp ; ------------------------------------------------------------------------------------- proc AddShiftBfToProductBf uses esi edi ecx ; add ShiftBf to ProductBf lea esi,[ShiftBf] lea edi,[ProductBf] stdcall CalcSum ret endp ; ------------------------------------------------------------------------------------- proc Modulus uses edi esi eax ecx ; calculate ProductBf mod ShiftBf ; ProductBf is of length DBL_HEX_LEN ; ShiftBf is of length DBL_HEX_LEN ; length of value in ShiftBf is up to HEX_LEN ; the remainder is left in ProductBf ; length of remainder is less than or equal to HEX_LEN ; if ShiftBf is zero, do nothing stdcall IsShiftBfZero cmp al,1 je .QUIT ; if ProductBf is less than ShiftBf, do nothing stdcall IsProductBfLessThanShiftBf cmp al,1 je .QUIT ; left shift ShiftBf to align the high order bits with ProductBf locals hob_PBf dw 0 hob_SBf dw 0 shift dw 0 endl ; find the high order bit in ProductBf lea eax,[ProductBf] stdcall FindHighOrderBit ; check if the high order bit was found cmp eax,0xffffffff je .QUIT mov word [hob_PBf],ax ; find the high order bit in ShiftBf lea eax,[ShiftBf] stdcall FindHighOrderBit ; check if the high order bit was found cmp eax,0xffffffff je .QUIT mov word [hob_SBf],ax ; compute how much to shift ShiftBf by mov ax,[hob_PBf] sub ax,[hob_SBf] mov word [shift],ax ; do the shift lea eax,[ShiftBf] xor edx,edx mov dx,word [shift] stdcall BigLeftShift ; the high order bits of ProductBf and ShiftBf are now aligned ; Algorithm: ; for (shift + 1) bits in ProductBf starting from the high order bit: ; (1) determine if ProductBf is less than ShiftBf ; (2) if false, subtract ShiftBf from ProductBf ; (3) right shift ShiftBf by 1 bit ; (4) repeat from (1) mov cx,word [shift] .CALC_MOD: lea eax,[ProductBf] lea edx,[ShiftBf] stdcall IsLessThan test al,1 jnz .SHIFT lea edi,[ProductBf] lea esi,[ShiftBf] stdcall CalcDiff .SHIFT: ; want to retain the original value of ShiftBf ; so when cx reaches 0, quit before the final shift cmp cx,0 jle .QUIT ; right shift ShiftBf lea edi,[ShiftBf] stdcall ShiftRight dec cx jmp .CALC_MOD ; the result is now in A .QUIT: ret endp ; ------------------------------------------------------------------------------------- proc BigLeftShift uses esi edi ecx ; left shift a double hex value by more than 1 bit ; address is passed in EAX ; size of shift passed in EDX mov edi,eax mov esi,eax locals nBytes dw 0 nBits db 0 addr dd ? endl ; save the address for later mov dword [addr],eax ; size of shift = 8 * nBytes + nBits ; get nBits mov al,dl and al,7 mov byte [nBits],al ; get nBytes shr dx,3 mov word [nBytes],dx cmp word [nBytes],0 je .BITS cmp word [nBytes],DBL_HEX_LEN jge .ZERO_HEX ; copy up the bytes in the hex value by nBytes add edi,DBL_HEX_LEN-1 add esi,DBL_HEX_LEN-1 sub si,word [nBytes] mov cx,DBL_HEX_LEN sub cx,word [nBytes] ; copy up (DBL_HEX_LEN - nBytes) bytes .COPY_UP: mov al,[esi] mov [edi],al dec esi dec edi dec cx cmp cx,0 jg .COPY_UP mov cx,word [nBytes] ; fill the rest of the hex array with zero bytes .FILL_0: mov [edi],byte 0 dec edi dec cx cmp cx,0 jg .FILL_0 ; all done if nBits is zero cmp byte [nBits],0 je .DONE .BITS: ; set edi back to the high order dword in the hex value mov edi,dword [addr] add edi,DBL_HEX_LEN-4 mov cx,DBL_HEX_LEN-4 .SHIFT_BITS: mov eax,[edi-4] push cx mov cl,byte [nBits] shld dword [edi],eax,cl pop cx sub edi,4 sub cx,4 cmp cx,0 jg .SHIFT_BITS mov cl,byte [nBits] shl dword [edi],cl jmp .DONE .ZERO_HEX: ; shift is greater than the size of the hex value, just set to zero stdcall ZeroDoubleHexBuffer .DONE: ret endp ; ------------------------------------------------------------------------------------- proc FindHighOrderBit uses esi ecx ; scan a double hex length value for the high order bit ; return an index number giving the position of the high order bit ; address passed in EAX ; index returned in EAX mov esi,eax ; start from the high order byte add esi,DBL_HEX_LEN-1 mov cx,DBL_HEX_LEN mov eax,DBL_HEX_LEN-1 ; scan byte by byte for the first non-zero byte .SCAN: cmp byte [esi],0 jne .FOUND dec cx cmp cx,0 ; not found if cx = 0, so quit jle .NOT_FOUND dec esi dec eax jmp .SCAN .FOUND: ; multiply EAX by 8 shl eax,3 mov ebx,7 mov dl,byte [esi] .FIND_BIT: test dl,0x80 jnz .FINISH shl dl,1 dec bl cmp bl,0 jl .NOT_FOUND jmp .FIND_BIT .FINISH: ; add the bit position to get the final index value add eax,ebx jmp .DONE .NOT_FOUND: mov eax,0xffffffff .DONE: ret endp ; ------------------------------------------------------------------------------------- proc IsLessThan uses esi edi ecx ; is A less than B ? ; A and B are treated as unsigned values ; address of A passed in EAX ; address of B passed in EDX mov edi,eax mov esi,edx ; start from the high order bytes add esi,DBL_HEX_LEN-4 add edi,DBL_HEX_LEN-4 mov cx,0 ; result is returned in AL xor al,al .CHECK_LT: mov edx,dword [edi] cmp edx,dword [esi] jb .LESS_THAN jnbe .QUIT add cx,4 cmp cx,DBL_HEX_LEN jge .QUIT sub esi,4 sub edi,4 jmp .CHECK_LT ; AL = true if less than .LESS_THAN: mov al,1 .QUIT: ret endp ; ------------------------------------------------------------------------------------- proc Mod_Exp uses esi edi ; compute Mod_Exp = pow(A,B) mod C ; A is in BaseBf ; B is in ExpBf ; C is in ModBf ; result in ProductBf locals nBit db 0 index dw 0 bits db 0 endl stdcall ZeroProductBf ; if C is zero, do nothing stdcall IsModBfZero cmp al,1 je .QUIT ; init ProductBf to 1 lea edi,[ProductBf] mov [edi],byte 1 ; if B is zero, do nothing stdcall IsExpBfZero cmp al,1 je .QUIT ; ProductBf is now 1 .START: ; find the first non zero byte in ExpBf lea esi,[ExpBf] xor ecx,ecx mov cx,HEX_LEN-1 .FIND: cmp [esi+ecx],byte 0 jne .FOUND dec cx cmp cx,0 jge .FIND ; if the loop exits here, ExpBf is zero jmp .QUIT .FOUND: ; save the index mov [index],cx ; save the byte mov al,byte [esi+ecx] mov [bits],al ; set the bit index mov [nBit],byte 8 ; start processing .SQUARE: ; always square, whether the bit is 0 or 1 ; square the value in ProductBf stdcall CopyProductBfToShiftBf stdcall CopyProductBfToTempBf stdcall ZeroProductBf lea esi,[TempBf] stdcall Multiply stdcall CopyModBfToShiftBf stdcall Modulus .TEST: ; only multiply if the bit is 1 ; decrement the bit index dec [nBit] ; test the bit in [bits] shl byte [bits],1 jnc .NEXT_BIT .MULTIPLY: ; multiply ProductBf by BaseBf stdcall CopyProductBfToShiftBf stdcall ZeroProductBf lea esi,[BaseBf] stdcall Multiply stdcall CopyModBfToShiftBf stdcall Modulus .NEXT_BIT: ; if nBit = 0, will need to get the next byte cmp [nBit],byte 0 jg .SQUARE .NEXT_BYTE: ; get the next byte ; if index = 0, there is no next byte, so quit cmp [index],word 0 je .QUIT dec word [index] mov [nBit],byte 8 ; make sure ESI points to ExpBf lea esi,[ExpBf] xor ecx,ecx mov cx,[index] mov al,byte [esi+ecx] mov [bits],al jmp .SQUARE .QUIT: ret endp ; ------------------------------------------------------------------------------------- proc CopyToBaseBf uses edi ecx ; copy ESI to BaseBf ; ESI is set outside of this procedure lea edi,[BaseBf] xor ecx,ecx .COPY: mov dl,[esi+ecx] mov [edi+ecx],dl inc cx cmp cx,HEX_LEN jl .COPY ret endp ; ------------------------------------------------------------------------------------- proc CopyToExpBf uses edi ecx ; copy ESI to ExpBf ; ESI is set outside of this procedure lea edi,[ExpBf] xor ecx,ecx .COPY: mov dl,[esi+ecx] mov [edi+ecx],dl inc cx cmp cx,HEX_LEN jl .COPY ret endp ; ------------------------------------------------------------------------------------- proc CopyToModBf uses edi ecx ; copy ESI to ModBf ; ESI is set outside of this procedure lea edi,[ModBf] xor ecx,ecx .COPY: mov dl,[esi+ecx] mov [edi+ecx],dl inc cx cmp cx,HEX_LEN jl .COPY ret endp ; ------------------------------------------------------------------------------------- proc Calc_GCD uses esi edi ecx ; calc GCD of TestPrime with BaseBf lea esi,[TestPrime] stdcall CopyToProductBf lea esi,[BaseBf] stdcall CopyToShiftBf .GCD: stdcall Modulus stdcall XchgProductBfShiftBf stdcall IsShiftBfZero cmp al,1 je .DONE jmp .GCD .DONE: ret endp ; ------------------------------------------------------------------------------------- proc XchgProductBfShiftBf uses esi edi ecx ; swap the values in ProductBf and ShiftBf lea esi,[ProductBf] lea edi,[ShiftBf] xor ecx,ecx .SWAP: mov dl,[esi+ecx] mov bl,[edi+ecx] mov [edi+ecx],dl mov [esi+ecx],bl inc cx cmp cx,DBL_HEX_LEN jl .SWAP ret endp ; ------------------------------------------------------------------------------------- proc ZeroDoubleHexBuffer uses ecx ; zero the double hex value in memory mov cx,0 .ZERO: mov [edi],byte 0 inc edi inc cx cmp cx,DBL_HEX_LEN jne .ZERO ret endp ; ------------------------------------------------------------------------------------- proc IsHexZero uses ecx ; is a hex number of length HEX_LEN equal to zero ? ; EDI is set outside of this procedure ; EDI is not modifed by this procedure xor ecx,ecx .TEST: cmp [edi+ecx],byte 0 jne .NON_ZERO inc cx cmp cx,HEX_LEN jl .TEST ; if the loop exits here, the value is zero mov al,1 jmp .DONE .NON_ZERO: xor eax,eax .DONE: ret endp ; ------------------------------------------------------------------------------------- proc IsDblHexZero uses ecx ; is a double hex number of length DBL_HEX_LEN equal to zero ? ; EDI is set outside of this procedure ; EDI is not modifed by this procedure xor ecx,ecx .TEST: cmp [edi+ecx],byte 0 jne .NON_ZERO inc cx cmp cx,DBL_HEX_LEN jl .TEST ; if the loop exits here, the value is zero mov al,1 jmp .DONE .NON_ZERO: xor eax,eax .DONE: ret endp ; ------------------------------------------------------------------------------------- proc IsExpBfZero uses edi ; is ExpBf equal to zero ? lea edi,[ExpBf] stdcall IsHexZero ret endp ; ------------------------------------------------------------------------------------- proc IsModBfZero uses edi ; is ModBf equal to zero ? lea edi,[ModBf] stdcall IsHexZero ret endp ; ------------------------------------------------------------------------------------- proc CopyProductBfToShiftBf uses esi edi ecx ; copy ProductBf to ShiftBf lea esi,[ProductBf] lea edi,[ShiftBf] xor ecx,ecx .COPY: mov dl,[esi+ecx] mov [edi+ecx],dl inc cx cmp cx,DBL_HEX_LEN jl .COPY ret endp ; ------------------------------------------------------------------------------------- proc CopyProductBfToTempBf uses esi edi ecx ; copy ProductBf to TempBf lea esi,[ProductBf] lea edi,[TempBf] xor ecx,ecx .COPY: mov dl,[esi+ecx] mov [edi+ecx],dl inc cx cmp cx,HEX_LEN jl .COPY ret endp ; ------------------------------------------------------------------------------------- proc ZeroShiftBf uses edi ecx ; zero the shift buffer lea edi,[ShiftBf] xor ecx,ecx .CLEAR: mov [edi+ecx],byte 0 inc cx cmp cx,DBL_HEX_LEN jl .CLEAR ret endp ; ------------------------------------------------------------------------------------- proc CopyModBfToShiftBf uses esi ; copy ModBf to ShiftBf lea esi,[ModBf] stdcall CopyToShiftBf ret endp ; ------------------------------------------------------------------------------------- proc CopyBaseBfToProductBf uses esi ; copy BaseBf to ProductBf lea esi,[BaseBf] stdcall CopyToProductBf ret endp ; ------------------------------------------------------------------------------------- proc CopyToShiftBf uses edi ecx ; copy ESI to ShiftBf ; ESI is of length HEX_LEN ; ESI is set outside of this procedure lea edi,[ShiftBf] xor ecx,ecx .COPY: mov dl,[esi+ecx] mov [edi+ecx],dl inc cx cmp cx,HEX_LEN jl .COPY .ZERO: ; zero the upper bytes of ShiftBf mov [edi+ecx],byte 0 inc cx cmp cx,DBL_HEX_LEN jl .ZERO ret endp ; ------------------------------------------------------------------------------------- proc ZeroProductBf uses edi ecx ; zero the product buffer lea edi,[ProductBf] xor ecx,ecx .CLEAR: mov [edi+ecx],byte 0 inc cx cmp cx,DBL_HEX_LEN jl .CLEAR ret endp ; ------------------------------------------------------------------------------------- proc CopyToProductBf uses edi ecx ; copy ESI to ProductBf ; ESI is of length HEX_LEN ; ESI is set outside of this procedure lea edi,[ProductBf] xor ecx,ecx .COPY: mov dl,[esi+ecx] mov [edi+ecx],dl inc cx cmp cx,HEX_LEN jl .COPY .ZERO: ; zero the upper bytes of ProductBf mov [edi+ecx],byte 0 inc cx cmp cx,DBL_HEX_LEN jl .ZERO ret endp ; ------------------------------------------------------------------------------------- proc CopyFromProductBf uses esi ecx ; copy from ProductBf to EDI ; EDI is of length HEX_LEN ; EDI is set outside of this procedure lea esi,[ProductBf] xor ecx,ecx .COPY: mov dl,[esi+ecx] mov [edi+ecx],dl inc cx cmp cx,HEX_LEN jl .COPY ret endp ; ------------------------------------------------------------------------------------- proc IsProductBfLessThanShiftBf uses esi edi ecx ; is ProductBf less than ShiftBf lea esi,[ShiftBf] lea edi,[ProductBf] xor ecx,ecx mov cx,DBL_HEX_LEN-1 .COMPARE: mov dl,[esi+ecx] cmp [edi+ecx],dl jb .LT ja .GTE dec cx cmp cx,0 jge .COMPARE ; if the loop exits here, the values are equal .GTE: xor eax,eax jmp .DONE .LT: mov al,1 .DONE: ret endp ; ------------------------------------------------------------------------------------- proc IsShiftBfZero uses edi ; is ShiftBf zero ? lea edi,[ShiftBf] stdcall IsDblHexZero ret endp ; ------------------------------------------------------------------------------------- proc Decrement uses ecx ; decrement the value in EDI ; EDI is set outside of this procedure sub [edi],byte 1 jnc .DONE xor ecx,ecx mov cx,1 .SUB_B: sub [edi+ecx],byte 1 jnc .DONE inc cx cmp cx,HEX_LEN jl .SUB_B .DONE: ret endp ; ------------------------------------------------------------------------------------- proc AddStringToEDI ; print a string to the EDI buffer ; ESI and EDI are set outside of this procedure .PRINT: mov dl,[esi] cmp dl,0 je .DONE mov [edi],dl inc esi inc edi jmp .PRINT .DONE: ret endp ; ------------------------------------------------------------------------------------- proc Check_GCD_Passed uses esi ecx ; did the test prime pass the GCD test ? lea esi,[ProductBf] xor ecx,ecx mov cx,DBL_HEX_LEN-1 .TEST: cmp [esi+ecx],byte 0 jne .FAILED dec cx cmp cx,0 jg .TEST ; test [esi] cmp [esi],byte 1 jne .FAILED .PASSED: mov [GCD_Passed],byte 1 jmp .DONE .FAILED: mov [GCD_Passed],byte 0 .DONE: ret endp ; ------------------------------------------------------------------------------------- proc Check_MEXP_Passed uses esi ecx ; did the test prime pass the mod exp test ? lea esi,[ProductBf] xor ecx,ecx mov cx,DBL_HEX_LEN-1 .TEST: cmp [esi+ecx],byte 0 jne .FAILED dec cx cmp cx,0 jg .TEST ; test [esi] cmp [esi],byte 1 jne .FAILED .PASSED: mov [MEXP_Passed],byte 1 jmp .DONE .FAILED: mov [MEXP_Passed],byte 0 .DONE: ret endp ; ------------------------------------------------------------------------------------- section '.idata' import data readable writeable library kernel,'KERNEL32.DLL',\ user,'USER32.DLL' import kernel,\ GetModuleHandle,'GetModuleHandleA',\ ExitProcess,'ExitProcess' import user,\ DialogBoxParam,'DialogBoxParamA',\ SetDlgItemText,'SetDlgItemTextA',\ GetDlgItemText,'GetDlgItemTextA',\ EndDialog,'EndDialog' ; ------------------------------------------------------------------------------------- section '.data' readable writeable bfDisplay rb 1200 TestPrime rb 400 ShiftBf rb DBL_HEX_LEN ProductBf rb DBL_HEX_LEN TempBf rb HEX_LEN BaseBf rb HEX_LEN ExpBf rb HEX_LEN ModBf rb HEX_LEN szMsg_1 db "The input number was tested with the random integer:",0 szMsg_2 db "TEST: GCD(a,p) = 1 --> ",0 szMsg_3 db "TEST: a^(p-1) mod p = 1 --> ",0 szFailed db "FAILED",0 szPassed db "PASSED",0 GCD_Passed db 0 MEXP_Passed db 0 ; ------------------------------------------------------------------------------------- section '.rc' resource data readable directory RT_DIALOG,dialogs resource dialogs,IDD_THE_DIALOG,LANG_ENGLISH+SUBLANG_DEFAULT,the_dialog dialog the_dialog,\ 'FASM - Prime Number Test',50,50,360,396,\ DS_MODALFRAME+WS_MINIMIZEBOX+WS_POPUP+WS_VISIBLE+WS_CAPTION+WS_SYSMENU,\ 0,0,"Lucida Console",11 dialogitem 'BUTTON','Input',-1,7,5,346,180,BS_GROUPBOX+WS_VISIBLE,0 dialogitem 'BUTTON',"Output",-1,7,190,346,180,BS_GROUPBOX+WS_VISIBLE,0 dialogitem 'EDIT',0,IDC_INPUT,13,18,335,160,ES_MULTILINE+ES_AUTOVSCROLL+ES_WANTRETURN+WS_VSCROLL+WS_BORDER+WS_VISIBLE,0 dialogitem 'EDIT',0,IDC_OUTPUT,13,203,335,160,ES_MULTILINE+ES_AUTOVSCROLL+ES_WANTRETURN+WS_VSCROLL+WS_BORDER+WS_VISIBLE,0 dialogitem 'BUTTON',"Test Decimal",IDC_BTN_TEST_DEC,7,375,80,14,BS_PUSHBUTTON+WS_VISIBLE,0 dialogitem 'BUTTON',"Test Hexadecimal",IDC_BTN_TEST_HEX,89,375,80,14,BS_PUSHBUTTON+WS_VISIBLE,0 enddialog ; -------------------------------------------------------------------------------------

Advertisement