une idée à 2 balles

Bonjour à tous

Je me disais comme ça l'autre jour, y a-t-il des gens qui cherchent à montrer qu'on ne pourra jamais tester la primalité de n plus rapidement qu'un certain temps dépendant de n (en gros une minimisation absolue du temps de factorisation)

Je me disais ça parce que, ça fait tellement longtemps que les recherches sur un test aussi rapide qu'on le souhaite pour la primalité d'un entier restent infructueuses, qu'il serait peut-être intéressant de chercher à montrer qu'on ne pourra aller plus vite que : tant d'opérations pour n.

Bon évidement c'est loin d'être plus évident, mais ça a peut-être plus de chances de marcher.

Les spécialistes de la théorie des nombres diront certainement si c'est envisageable ou si ce n'est que du vent ;)

t-mouss

Réponses

  • C'est pas idiot comme question. Je ne suis pas en mesure d'y répondre, mais je suivrai l'évolution de ce topic avec intérêt.
  • Je doute qu'on puisse faire une telle affirmation de façon utile. Et ceux qui croyaient qu'aucun test polynomial n'étaient possible ont été cruellement déçus il y a deux ans. Mais j'espère être moi aussi détrompé.
  • oui j'ai entendu parler de ce test....

    mais justement la question est : peut-on aller aussi loin qu'on le souhaite ? sera t-on bloqué par qqchose similaire à la puissance du continu (inutile de chercher un ensemble de cardinal strictement compris entre celui de $\N$ et celui de $\R$)

    t-mouss
  • je pense que c'est mal barré pour trouver un algo en temps constant déjà
    en temps log aussi
    en temps linéaire bon ça se discute...
  • Juste au passage la question que tu poses t-mouss et qui fait sens est celle de la complexité de l'algo grosso modo du nombre d'opérations en fonction de n car si on parle de temps (seconde) il faut spécifier la puissance de calcul dont on dispose en effet si tu fait 10 opérations secondes avec une machine X et 100 000 avec une autres un même algorithme (et donc de même complexité) s'exécutera plus vite sur une machine que sur l'autre si mes souvenirs sont bon l'algo dont parle Gérard a pour complexité dans sa première version un polynôme de degré 13.

    François
  • bonjour

    oui bien sur smallux, je ne l'ai pas précisé car pour moi la question étant purement mathématique, seul le cout de calcul absolue (ie nombre d'opérations élémentaire à effectuer) est important...

    sur qu'avec un ordi quantique de 100 Qbits le pb serait bien plus simple (quoique)

    pour l'algo polynomial il me semble effectivement qu'un groupe de chercheurs indiens à trouver un algo dont la complexité est un polynome de degré 13. Il me semble (mais c loin d'etre sur) que c'est descendu à un degré 7, mais je divague peut-être (il est affreusement tot !)

    t-mouss
  • La complexité d'un algorithme se définit par 3 choses:
    - la taille du problème:
    Exemple:
    primalité = nbre de décimales de n= ln(n)
    Newton: = nbre de décimales exactes = -ln(erreur commise)
    pgcd= ah... pas simple, on prend max(m,n)

    - ce que l'on compte:
    c= nombre d'opérations élémentaires (primalité) d'itérations (Newton), de comparaison (tri). On peut aussi parler de complexité spatiale (taille mémoire).

    - La relation entre les deux: l'égalité n'est pas intéressante, on cherche un ordre de grandeur exact (noté $\theta(v_n)$ i.e $u_n=\theta(v_n)$ ssi $u_n=O(v_n)$ et $v_n=O(u_n)$

    Le temps en lui même n'est pas intéressant. Par contre effectivement, la complexité change d'ordre de grandeur si on passe sur une machine massivement parallèle idéale (autant de processeurs qu'on veut) ou une machine quantique (là ça se complique).
    Il y a la complexité dans le meilleur cas (pgcd(n,n+1) par exemple), moyenne et pire cas. Cette dernière est la plus interessante.

    Souvent au lieu de chercher la complexité dans le pire cas, il est intéressant de chercher le plus petit cas à complexité donnée (c'est comme ça qu'on montre que l'algorithme d'Euclide est en ln(n)). Ici, il faudrait trouver l'entier le plus petit demandant un nombre d'opérations donné pour être factorisé.
  • Avec une machine massivement parallèle idéale, la primalité de n se trouve en un temps 1 (avec n processeurs !!!). Il suffit de diviser n par tous les entiers plus petits, un par processeur.
    Je blagues un peu su la notion de machine massivement parallèle idéale.

    Cordialement
Connectez-vous ou Inscrivez-vous pour répondre.