Forum de Mathématiques: Maths-Forum

vous avez totalement raison je me suis mélangé les pinceaux, merci pour ces précisions !

À quoi sert d'avoir les trois M_i ? Notre professeur nous a donné les mêmes indications pour une multitude de questions, les trois M_i étaient à utiliser avec le théorème des restes Chinois et un e = 3. Pour cette question il suffit d'en avoir un seul, et à chaque itération de tester si notre m^e e...

Je vois, merci.
Mais il est bien polynomial ?

Je suppose que le fait que RSA ne peut pas être décrypté de cette sorte et que ce serait en O(log(k)^log(k)) et ce qui n'est pas polynomial, c'est bien cela ?

ah oui en effet !
Je n'ai pas été futé de réutiliser la lettre k ensuite, cela m'a perdu.

Enfin si mon algo est polynomial en log(k), il l'est aussi en log(n) puisque (et inversement ?) O(log(n)) = O(log(k^2)) = O(log(k) + log(k)) = O(log(k)) où suis-je dans l'erreur ?

Je ne vois pas trop pourquoi k serait la moitié de log 2 de n.
Pour moi on sait juste que k <= log 2 de n, non ?

tout à fait, je fais un abus de langage entre n et log(n) : J'ai une piste qui m'a l'air satisfaisante : On sait que l'exponentiation modulaire a une compléxitée de O(n) et nous dans notre cas si on testait tous les m possibles, nous serions en O(n^3), donc si on teste tous les m, nous sommes en O(n...

J'ai une piste qui m'a l'air satisfaisante : On sait que l'exponentiation modulaire a une compléxitée de O(n) et nous dans notre cas si on testait tous les m possibles, nous serions en O(n^3), donc si on teste tous les m, nous sommes en O(n^4) en temps. En mémoire, nous sommes en O(1) si je ne m'abu...

Bonjour, Etant en étude d'informatique, nous étudions RSA et surtout ces failles. Le problème qui me bloque est le suivant : Soient n_1, n_2, n_3, e, M_1, M_2, M_3 \in R avec : n_i = p_i*q_i{ les p_i et q_i sont des nombres premiers de k bits, e \in \{1,2,...,n-1\} et e premiers avec \phi(n_i...

Je vous remercie énormément !

C'est clair pour Greedy. Ça demande plus de réflexion pour WP. Tu peux commencer par voir pourquoi, si WP n'a pas encore colorié le sommet s et qu'on en arrive à la couleur d, il ne va pas colorier le sommet s avec la couleur d. Bonjour, Je crois avoir compris avec cette indication : Supposons que ...

Le sommet s est de couleur c si c est la première couleur tel qu'il n'y a aucun voisin de s de couleur c parmi les sommets précédant s. Montre que ça vaut à la fois pour Greedy et pour WP. Bonjour, Je vois très bien que, pour Greedy, si les n premiers sommets ont été coloré, alors le n+1 ème sommet...

Si tu pars de la même liste de sommets et de la même liste de couleurs pour les deux algorithmes, c'est normal que tu trouves le même résultat. Tu peux le démontrer par récurrence sur l'ordre dans la liste des sommets. Tu as à voir que si tous les sommets avant s ont reçu la même couleur par WP et ...

Si tu pars de la même liste de sommets et de la même liste de couleurs pour les deux algorithmes, c'est normal que tu trouves le même résultat. Tu peux le démontrer par récurrence sur l'ordre dans la liste des sommets. Tu as à voir que si tous les sommets avant s ont reçu la même couleur par WP et ...

Les algos WP et Greedy sont assez long, je les mettrais que si nécessaire mais voici comment je les appelle : int sum = 0; ArrayList<Integer> sortList = new QuickSort2(SortEnumerator.RANDOM).sortList; long n = 0; WellshPowell2 wp = new WellshPowell2((ArrayList<Integer>) sortList.clone()); GreedyColo...

Bonsoir, Normalement, si tu importes correctement ta librairie "Math" -> import math ou import from math import * , tu devrais avoir la fonction "isclose()". Si tu as importé ta libraire math de la première façon, il faudra faire : math.isclose(a, b) Sinon, il faudra faire : iscl...

Bonjour, Pour un cours de graphe, il nous est demandé d'implémenter des algorithmes de colorations et de les tester avec des graphes différents et des ordres différents (croissant, décroissant, aléatoire : selon le degré). Il nous est demandé d'implémenter certains algorithmes, tels que WelshPowell ...