Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques AutreForum traitant des mathématiques, un peu moins scolaires AlgorithmiqueForum consacré aux algorithme [tout]Lister tous les topics de mathématiques
Niveau algorithmique
test de primalité de fermat et nombres de carmicael sous SCILAB
Posté par sneb
Bonjour à tous,
j'ai écrit un test de primalité de fermat avec scilab et à ma grande surprise il détecte que les nombres de carmicael ne sont pas premiers (alors que d'après les sources -wikipedia,...-, ils devraient le mettre en défaut, être identifiés comme premier sans l'être...)
Voici le code:
Citation :
// TEST DE PRIMALITE DE FERMAT
// pourquoi ce test renvoie false su les nombres de Carmichael?
function [test] = primfermat(n)
// en argument un entier supérieur à 7
// renvoie true si composé, false si probable premier
if ~((n>7)&(ceil(n)==n)); disp("argument mal défini"); end
m = 2:7 //les témoins sont 2, 3, ..., 7
p=puissmatmodn(m,n-1,n); //on calcule les puissances n-1 de chaque élément de m modulo n
if p == ones(1,6) //si tout est égal à 1 dans le calcul précédent, n est probable premier
test = %T
else
test = %F
end
endfunction
// FONCTION EVITANT LES GRANDS NOMBRES DANS LE CALCUL DES PUISSANCES D'UNE MATRICE
function [y] = puissmatmodn(mat,p,n)
// en argument un vecteur, la puissance, et le modulo
y=mat
for i=1: (p-1) // c'est ":" puis "(" pas
^^'''
y=modulo(y.*mat,n)
end
endfunction
// TEST DE PRIMALITE DE FERMAT
// pourquoi ce test renvoie false su les nombres de Carmichael?
function [test] = primfermat(n)
// en argument un entier supérieur à 7
// renvoie true si composé, false si probable premier
if ~((n>7)&(ceil(n)==n)); disp("argument mal défini"); end
m = 2:7 //les témoins sont 2, 3, ..., 7
p=puissmatmodn(m,n-1,n); //on calcule les puissances n-1 de chaque élément de m modulo n
if p == ones(1,6) //si tout est égal à 1 dans le calcul précédent, n est probable premier
test = %T
else
test = %F
end
endfunction
// FONCTION EVITANT LES GRANDS NOMBRES DANS LE CALCUL DES PUISSANCES D'UNE MATRICE
function [y] = puissmatmodn(mat,p,n)
// en argument un vecteur, la puissance, et le modulo
y=mat
for i=1: (p-1) // c'est ":" puis "(" pas
^^'''y=modulo(y.*mat,n)
end
endfunction
Si quelqu'un a une idée de l'origine du phénomène???
Bonjour,
Si un nombre de Carmichaël possède p=3,5 ou 7 comme facteur premier le test renverra "composé" car pn-1 modulo n ne pourra pas être égal à 1 (pn-1-k*p est divisible par p).
En revanche pour n=75361=11*13*17*31 le test renvoie "premier".
Annuler
connectez vous