Nombre premier ou composé

Commenter

Contenu du snippet

fonction renvoyant la primalité d'un nombre
test de primalité ---> Miller-Bach-Rabin (1985)
+ fonction de calcul de a^n (modulo p)
+ conversion de n en binaire

Source / Exemple : 


'----------------------------------------------------------------------------------------------------------------
'       Philippe Laugerat   03/2013
'----------------------------------------------------------------------------------------------------------------
'       test de primalité   ---> Miller-Bach-Rabin (1985)
'
'       1. On calcule k et m tq  n -1=2^k*m où m est impair.
'       2. On choisit plusieurs valeurs de a comprises entre 1 et n-1.
'       3. On evalue b = a^m mod n.
'       4. Si b = 1 (modulo n), alors n est premier.
'       5. For i = 0 to k - 1 do
'       6.    Si b = -1 (modulo n), alors n est premier sinon b = b^2 mod n.
'       7. Dans les autres cas, n est composé.
'
'       tests :
'       tous les nombres <= 10^9 (premiers et composés) sont trouvés correctement avec une précision de 3
'       sauf 4 qui sont traités comme des cas particuliers
'       non testé au delà
'       par défaut précision = 3 pour n < 10^9, précision = 6(? valeur empirique) sinon
'
'                   1                        fait planter le programme
'                   2                        résultat faux avec filtre pour nombres pairs
'            25326001 = 2251 x 11251         résultat correct avec précision = 4
'           161304001 = 7333 x 21997         résultat correct avec précision = 4
'
'       utilise les fonctions   Mod_AN          Calcul de a^n modulo m
'                               Conv_Binaire    Conversion d'entier (long) en binaire (string)
'----------------------------------------------------------------------------------------------------------------
Function EstPremier(n As Long, Optional precision As Integer = -1) As Boolean

    Dim m As Long, k As Integer, a As Long, b As Long, i As Integer, pas As Long
    
                                                        ' cas particuliers (ou pour accélérer)
    If n = 2 Then EstPremier = True: Exit Function
    If n <= 1 Or n = 25326001 Or n = 161304001 Or n Mod 2 = 0 Then EstPremier = False: Exit Function
    For i = 3 To 101 Step 2
        If n Mod i = 0 Then EstPremier = False: Exit Function
    Next i
                                                        ' précision = nb de tests effectués
    If precision < 1 Then
        If n < 10 ^ 9 Then precision = 3 Else precision = 6                     ' par défaut
    End If
    a = 2
    pas = (n - 2) / precision
    If pas = 0 Then pas = 1
                                                        ' calcul de m et k tels que n-1 = 2^k * m
    m = n - 1
    k = 0
    While m Mod 2 = 0
        m = m / 2
        k = k + 1
    Wend
    
    While a <= n - 1
    
        DoEvents
    
        b = CDec(Mod_AN(a, m, n))                     ' a^m modulo n
        
        If b <> 1 Then
            If k <> 1 Then
                i = 1
                While b <> n - 1
                    b = CDec(Mod_AN(b, 2, n))         ' b^2 modulo m
                    i = i + 1
                    If k < i Then EstPremier = False: Exit Function
                Wend
            Else
                If b <> n - 1 Then EstPremier = False: Exit Function
            End If
        End If
        
        a = a + pas
        If a Mod 2 Then a = a + 1
        
    Wend
    
    EstPremier = True
    
End Function

'----------------------------------------------------------------------------------------------------------------
'       Calcul de a^n modulo m
'----------------------------------------------------------------------------------------------------------------
Function Mod_AN(a As Long, n As Long, m As Long) As Long

    Dim nbin As String
    Dim w As Variant, res As Variant, i As Integer
    
    nbin = Conv_Binaire(n)
    
    res = CDec(1)
    
    For i = 1 To Len(nbin)
        If Val(Mid(nbin, i, 1)) = "0" Then w = CDec(1) Else w = CDec(a)
        res = res * res
        res = res * w
        'res = res Mod m
        w = Int(res / m)
        w = w * m
        res = res - w
        
    Next i

    Mod_AN = res

End Function

'----------------------------------------------------------------------------------------------------------------
'       conversion d'entier (long) en binaire (string)
'----------------------------------------------------------------------------------------------------------------
Function Conv_Binaire(n As Long) As String

    Dim wn As Long, res As String
    
    res = ""
    wn = n
    
    Do
        If wn Mod 2 = 1 Then
            res = "1" + res
            wn = wn - 1
        Else
            res = "0" + res
        End If
        wn = wn / 2
    Loop Until wn = 0
    
    Conv_Binaire = res
    
End Function

A voir également

S'inscrire maintenant

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.

Du même auteur (cs_apexinfo)