Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

test de primalité de fermat et nombres de carmicael sous SCILAB

Posté par
sneb
22-09-09 à 09:19

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


Si quelqu'un a une idée de l'origine du phénomène???

Posté par
jandri Correcteur
re : test de primalité de fermat et nombres de carmicael sous SC 23-09-09 à 21:29

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".

Posté par
sneb
re : test de primalité de fermat et nombres de carmicael sous SC 25-09-09 à 12:48

oooh oui c'est logique merci jandri



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !