Test de lucas lehmer
Description
Ce programme permet de trouver les nombres de Mersenne premier c'est à dire de la forme 2^p-1 avec p premier.
J'utilise le test de Lucas Lehmer: on definit la suite d'entiers u(n+1)=u(n)*u(n)-2, u(0)=4
alors 2^p-1 est premier si et seulement si u(p-2) est divisible par 2^p-1.
La fonction TestLucas, renvoie 1 si le nombre de Mersenne est premier et 0 si il est composé.
J'utilise le test de Lucas Lehmer: on definit la suite d'entiers u(n+1)=u(n)*u(n)-2, u(0)=4
alors 2^p-1 est premier si et seulement si u(p-2) est divisible par 2^p-1.
La fonction TestLucas, renvoie 1 si le nombre de Mersenne est premier et 0 si il est composé.
Source / Exemple :
; test de Lucas Lehmer
; recherche des nombres premiers de la forme 2^n-1
; compilation avec masm32 (console)
.486 ; create 32 bit code
.model flat, stdcall ; 32 bit memory model
option casemap :none ; case sensitive
include \masm32\include\windows.inc ; always first
include \masm32\include\gdi32.inc
include \masm32\include\user32.inc
include \masm32\include\kernel32.inc
includelib \masm32\lib\gdi32.lib
includelib \masm32\lib\user32.lib
includelib \masm32\lib\kernel32.lib
StdOut PROTO :DWORD
TestPremier PROTO :DWORD
TestLucas PROTO :DWORD
.data
outHandle dd 0
p0 dd 3
A dd 0
B dd 0
max dd 2000 ;valeur maximale a tester
strFormat db "%7d ",0
strTempsCalcul db 13,10,"Temps de calcul %d ms",13,10,0
strInit db "2^n-1 est premier pour n=",13,10,0
strMemErr db "pas assez de memoire",0
strSortie db 32 dup (0)
.code
start:
invoke GetStdHandle,STD_OUTPUT_HANDLE
mov outHandle,eax
invoke GetTickCount
push eax
mov ebx,max
add ebx,31
shr ebx,3
and ebx,-4
push ebx
invoke GlobalAlloc,GMEM_FIXED,ebx
pop ebx
or eax,eax
jz err
mov A,eax
shl ebx,1
invoke GlobalAlloc,GMEM_FIXED,ebx
or eax,eax
jz err
mov B,eax
invoke StdOut,offset strInit
suivant:
invoke TestPremier,p0
or eax,eax
jz main1
push esi
push edi
invoke TestLucas,p0
pop edi
pop esi
or eax,eax
jz main1
invoke wsprintf,offset strSortie,offset strFormat,p0
invoke StdOut,offset strSortie
main1:
add p0,2
mov eax,max
cmp p0,eax
jb suivant
; on a fini
invoke GetTickCount
pop ebx
sub eax,ebx
invoke wsprintf,offset strSortie,offset strTempsCalcul,eax
invoke StdOut,offset strSortie
invoke ExitProcess,0
err: invoke StdOut,offset strMemErr
invoke ExitProcess,0
StdOut proc chaine: DWORD
sub esp,4
mov ecx,chaine
xor ebx,ebx
SO1:
mov al,[ebx+ecx]
inc ebx
or al,al
jnz SO1
dec ebx
lea ecx,[ebp-4]
invoke WriteConsole,outHandle,chaine,ebx,ecx,0
ret
StdOut endp
TestPremier proc p: DWORD
cmp p,4
jb TP2
mov ebx,1
TP1: add ebx,2
xor edx,edx
mov eax,p
div ebx
or edx,edx
jz compose
cmp ebx,eax
jb TP1
TP2: mov eax,1
ret
compose:
xor eax,eax
ret
TestPremier endp
TestLucas proc p: DWORD
p3 equ [ebp-4] ;Taille de A en octets
p2 equ [ebp-8]
p1 equ [ebp-12]
n equ [ebp-16]
cld
sub esp,16
mov eax,p
sub eax,2
mov n,eax
pushad
mov eax,p
add eax,31
shr eax,3
and eax,-4
mov p3,eax
mov ecx,p
and ecx,31
mov p1,ecx
mov eax,1
shl eax,cl
mov p2,eax
; A=4
mov edi,A
mov eax,4
stosd
mov ecx,p3
shr ecx,2
dec ecx
jz pas
xor eax,eax
rep stosd
pas:
; B = A*A
mov ecx,p3
shr ecx,1
xor eax,eax
mov edi,B
rep stosd
mov edi,A
mov ecx,edi
add ecx,p3
l1: mov esi,edi
add esi,4
cmp esi,ecx
jnb l2b
mov ebx,esi
sub ebx,A
shl ebx,1
sub ebx,4
add ebx,B
l0: lodsd
mul dword ptr [edi]
add [ebx],eax
adc [ebx+4],edx
jnb l2
push ebx
l3: add ebx,4
inc dword ptr [ebx+4]
jz l3
pop ebx
l2: add ebx,4
cmp esi,ecx
jb l0
add edi,4
jmp l1
l2b: push ecx
mov esi,B
mov ecx,p3
shr ecx,1
mov edi,esi
l2c: lodsd
rcl eax,1
stosd
loop l2c
pop ecx
mov esi,A
mov edi,B
xor ebx,ebx
l2d: lodsd
mul eax
shr ebx,1
adc [edi],eax
adc [edi+4],edx
rcl ebx,1
add edi,8
cmp esi,ecx
jb l2d
; B = B - 2
mov ebx,2
mov edi,B
cmp [edi],ebx
jnb l4b
xor eax,eax
mov ecx,p3
shl ecx,1
sub ecx,4
add edi,4
repe scasb
jnz l4
l5: mov eax,p2
mov edi,B
add edi,p3
add [edi-4],eax
inc ebx
l4: mov edi,B
l4b: sub [edi],ebx
jnb l7
l6: add edi,4
dec dword ptr [edi]
cmp dword ptr [edi],-1
jz l6
;A = B mod 2^p -1
l7:
mov ecx,p1
mov esi,B
add esi,p3
sub esi,4
mov edi,A
lodsd
mov edx,edi
add edx,p3
l10:
mov ebx,eax
lodsd
shrd ebx,eax,cl
mov [edi],ebx
add edi,4
cmp edi,edx
jb l10
mov ecx,p2
dec ecx
sub esi,p3
and [esi-4],ecx
mov esi,B
mov edi,A
mov ecx,p3
shr ecx,2
clc
l11:
lodsd
adc eax,[edi]
stosd
loop l11
sub eax,p2
jb l12
mov [edi-4],eax
mov esi,A
sub esi,4
l13: add esi,4
inc dword ptr [esi]
jz l13
l12:
dec dword ptr n
jnz pas
;test si le reste est nul
mov edi,A
mov ecx,p3
shr ecx,2
dec ecx
jz l21
mov eax,-1
repe scasd
jnz l20
l21:
mov eax,p2
dec eax
scasd
jz premier
l20:
mov ecx,p3
mov edi,A
xor eax,eax
repe scasb
jz premier
popad
mov eax,0
ret
premier:
popad
mov eax,1
ret
TestLucas endp
end start
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.