Comme annonc\u00e9 dans mon dernier article, concernant l’algorithme de recherche des nombres premiers, nous allons nous pencher sur diff\u00e9rents tests de primalit\u00e9 d’un point de vue plus math\u00e9matique. N\u00e9anmoins, cela devrait rester abordable, nul besoin de la connaissance des espaces vectoriels pour comprendre :D.<\/p>\n\n\n\n
M\u00e9thode na\u00efve:<\/span><\/p>\n\n\n\n Il suffit de diviser le nombre n dont on veut tester la primalit\u00e9 par tous les nombres de 2 \u00e0 \u221an, car si n = p * q et dans ce cas, on a: p <= \u221an et q<= \u221an. En effet, supposons que p >= q > \u221an; p > \u221an, q > \u221an; p*q > \u221an -> absurde car n = p*q. On peut encore am\u00e9liorer le test et ne tester que les nombres impairs une fois que la division par 2 a \u00e9chou\u00e9. La complexit\u00e9 de ce test est exp( 1\/2 * log n ).<\/p>\n\n\n\n Test de Fermat:<\/span><\/p>\n\n\n\n Rappel: Si n est premier et si a < n, alors a^(n-1) \u2261 1 mod n.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Cons\u00e9quences: Test de Lucas-Lehmer:<\/span><\/p>\n\n\n\n Si p est premier, le nombre de Mersenne Mp d’indice p est d\u00e9fini par: Mp = 2^p\u00a0 –\u00a0 1 .\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 On d\u00e9finit une suite Sn par S2 = 4 et Sn = (S(n-1))\u00b2 – 2. \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0 Alors, Mp est premier ssi Mp divise Sp, c’est-\u00e0-dire: Sp \u2261 0 mod p.<\/p>\n","protected":false},"excerpt":{"rendered":" Comme annonc\u00e9 dans mon dernier article, concernant l’algorithme de recherche des nombres premiers, nous allons nous pencher sur diff\u00e9rents tests de primalit\u00e9 d’un point de vue plus math\u00e9matique. N\u00e9anmoins, cela devrait rester abordable, nul besoin de la connaissance des espaces vectoriels pour comprendre :D. M\u00e9thode na\u00efve: Il suffit de diviser le nombre n dont on … Continuer la lecture de « Nombre premier: test de primalit\u00e9 »<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-114","post","type-post","status-publish","format-standard","hentry","category-divers"],"_links":{"self":[{"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/posts\/114","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=114"}],"version-history":[{"count":2,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/posts\/114\/revisions"}],"predecessor-version":[{"id":4062,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/posts\/114\/revisions\/4062"}],"wp:attachment":[{"href":"https:\/\/www.unicoda.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=114"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=114"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=114"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
Soit a < n,\u00a0 Si a ^(n-1) \u2260 1 mod n alors n n’est pas premier. \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Ce test \u00e9limine mais ne confirme pas. Il est possible de d\u00e9terminer si le nombre n’est pas premier. La r\u00e9ciproque est fausse.<\/p>\n\n\n\n