Il y a qq temps, Phil Carmody avait réussit à convertir le code de DeCSS en un nombre premier (nombre divisible que par 1 et lui-même).
Il revient, toujours plus fort, avec un nombre premier exécutable en tentant de répondre à la passionnante question : est-ce tous les programmes sont <<exprimables>> sous forme d'un nombre premier exécutable ?
A titre d'exemple scientifique, il travaille sur le nombre premier qui représente DeCSS ... mais que va dire la MPAA ?
Aller plus loin
- First illegal prime number (46 clics)
- an executable prime number (33 clics)
- the register (9 clics)
- tutorial CSS (8 clics)
# Très joli
Posté par vrm (site web personnel) . Évalué à 1.
leur tête au bout d'un pique :D
(attention j'ai mis un ':D')
[^] # Re: Très joli
Posté par Eudoxe . Évalué à 3.
Par exemple le nombre de Champernown (?) : 0.1234567891011121314...
et peut-être pi (et d'autres).
Donc ce nombre contient aussi cette valeur de DeCSS, par conséquent un nombre-univers est illégal pour le MPAA. :)
--
CQFD
# Le même et qui fasse des divx
Posté par Jiquem . Évalué à 1.
[^] # Re: Le même et qui fasse des divx
Posté par Anonyme . Évalué à 1.
[^] # Re: Le même et qui fasse des divx
Posté par Vanhu . Évalué à 0.
J'ai une hypothese la dessus: il y aurait eu un bug à la fin du calcul, et la bonne réponse est en fait 43....
Mais bon, pas facile à prouver...
[^] # Re: Le même et qui fasse des divx
Posté par Larry Cow . Évalué à 1.
Non mais, hérétique va!
[^] # Re: Le même et qui fasse des divx
Posté par Jiquem . Évalué à 1.
# Ah les brevets
Posté par Gauthier (Mastodon) . Évalué à 10.
A suivre...
[^] # Re: Ah les brevets
Posté par Anonyme . Évalué à 5.
Cela donnerait lieu à un procès si Renault voulait créer une R306, mais si Heknkel voulait créer une lessive 306, ou des chouches 306, je ne sais pas si Peugeot pourrait y faire grand chose.
Le problème qui a vu le jour avec Illustrator & KIllustrator est presque pareil: cela voudrait dire que si quelqu'un crérait un KWindows ou un GPhotoshop, il pourrait se prendre un procès dans la face, étant donné ques les produits portant presque le même nom sont dans le même secteur d'activité.
GNutella, par contre, a pas grand chose a craindre.
La chose est différente pour les brevets, vu que, je crois, on ne peut pas (encore) breveter un nombre, voire un nom.
[^] # Re: Ah les brevets
Posté par kadreg . Évalué à 2.
C'est deja arrivé. La Porsche 911 devait a l'origine s'appeler 901, et a du être rebaptisé suite à une remarque de Peugeot (ca s'est fait a l'amiable). A noter qu'il n'y a jamais eut de Peugeot 901.
[^] # Re: Ah les brevets
Posté par Anonyme . Évalué à 1.
Ah ben non, c'était la 905. J'ai fait une recherche sur le site de peugeot, rien sur la 901. Va comprendre Charles...
[^] # Re: Ah les brevets
Posté par Axel R. (site web personnel) . Évalué à 0.
Axel - 584
[^] # Re: Ah les brevets
Posté par kadreg . Évalué à 1.
[^] # Re: Ah les brevets
Posté par Arnaud (site web personnel) . Évalué à 1.
pourquoi intel à laisser tomber la dénomination des x86 alors ?
[^] # Re: Ah les brevets
Posté par Anonyme . Évalué à -1.
--
Chuchi
[^] # Re: Ah les brevets
Posté par Axel R. (site web personnel) . Évalué à 1.
Axel - 584
[^] # Re: Ah les brevets
Posté par Anonyme . Évalué à 1.
Cela dit, je ne sais pas s'ils ont eu des problèmes avec GNU, mais d'après la logique de la chose, ils auraient dû, sauf si le projet fait partie officielle du projet GNU.
Car si je me souviens bien (j'ai des problèmes de mémoire :o) ), si un programme schmool ne fait pas partie de GNU, il ne peut pas s'appeler GNUdschmool.
[^] # Re: Ah les brevets
Posté par Anonyme . Évalué à 1.
EVENTUELLE action future.
Avez-vous noté le copyright suivant le slogan
Maxigaffe (pardon... µsoft!)"mais que ferez-vous demain?"
rien ne vous interdit de le dire. Mais si µsoft estime que cela porte atteinte à son image, il peut vous attaquer et très probablement gagner!
A partir de là, cela se transforme en épée de Damoclès bien déplaisante (surtout quand son tranchant s'abat sur vous!)
L'absurdité du système culmine avec les noms de marque qui cherchent à interdire à un citoyen lambda d'utiliser le sien du fait de l'homonymie (voir les nombreux cas de sociétés "de quartier" tenues par la justice de changer de raison sociale parce qu'une Major homonyme avait trouvé via le net qu'un "concurrent" détenait déjà le nom de domaine -bien que quelques affaires aient démontré l'existance de la dite société avant la création de la Major-!)
Ah dites donc! si l'inventeur de la roue avait déposé un brevet, pauvres de nous!
# Un nouvel algo de compression ?
Posté par jigso . Évalué à 4.
Supposons qu'un binaire ne soit pas un nombre premier, on pourrait en faire la décomposition en nombres premiers.
Avec un peu de chance cette décomposition sera plus petite que le nombre initial.
On pourrait même utiliser le rang des nombres premiers avec une table pour gagner encore un peu.
[^] # Re: Un nouvel algo de compression ?
Posté par Jaimé Ragnagna (site web personnel) . Évalué à 1.
C'est pas sur le fait que cette décomposition est très difficile que reposent les méthodes de cryptographie actuelle (enfin, j'ai plus vraiment de souvenirs hein ...)
Alors bon, si ta compression doit mettre des siecles a se faire, euh ... Je doute de la validité de ton idée.
Par contre, la décompression elle serai rapide.
Corrigez moi si j'ai dis une betise ... C'est après tout fort possible.
[^] # Re: Un nouvel algo de compression ?
Posté par Olivier Dupuis . Évalué à 3.
>très difficile que reposent les méthodes de
>cryptographie actuelle (enfin, j'ai plus vraiment
>de souvenirs hein ...)
C'est exactement là-dessus que se base la sécurté de la méthode RSA. Ta mémoire est bonne.
La clef publique est le produit de deux nombres premiers "grands". Et actuellement on ne dispose pas de méthode "rapide" pour décomposer un nombre.
En gros, rien de tellement mieux que d'essayer de diviser le nombre par les nombres premiers inférieurs à son carré.
Le second problème vient du fait qu'à moins de connaître exactement tous ces dits nombres premiers inférieurs à sa racine carrée, on en est souvent réduit à tester 2, 3 et 5 puis 7+2*k.
Au final, si le nombre est "grand", l'algorithme de décomposition est en n^(1/2) avec n la valeur du nombre a décomposer.
Le temps de calcul augmente beaucoup trop vite avec la taille du nombre.
(J'espère juste ne pas m'être trompé dans ces calculs...)
[^] # RSA != factorisation
Posté par pappy (site web personnel) . Évalué à 2.
RSA repose sur la factorisation, ce qui fait que si on trouve un algorithme polynomial pour factoriser, RSA est cassé.
MAIS on ne sait pas si il y a besoin de factoriser pour casser RSA.
Par exemple, il existe des nombres premiers particuliers (je ne me souviens plus de leur nom) qu'il faut absolument éviter de choisir quand tu génères tes clés sans quoi tu peux casser RSA sans avoir à factoriser.
Par ailleurs, il existe d'autres algorithmes, bien plus performants que ceux dont tu parles pour factorise (tester tous les nombres premiers inférieurs à sqrt(n)) : le crible quadratique et le crible algébrique.
Tu trouveras ds référecnes sur cette page :
http://www.lix.polytechnique.fr/Labo/Francois.Morain/Crypto/crypto.(...)
[^] # Re: Un nouvel algo de compression ?
Posté par GP Le (site web personnel) . Évalué à 0.
Un programme doit etre precis au bit pres. Sinon, il ne s'execute pas correctement. C'est un melange d'une grande recherche et d'une bonne chance que d'avoir ecrit DECSS sous forme d'un nombre premier.
[^] # Re: Un nouvel algo de compression ?
Posté par Foxy (site web personnel) . Évalué à 6.
L'idée est intéressante mais complétement irréalisable. En effet, tout personne ayant fait un tant soit peu de math ;-) sait que le problème de décomposition d'un nombre entier en facteurs entiers est un problème très difficile (en langage correct, on dit "NP-complet").
Autrement dit, la décomposition en facteurs premiers est bien trop consommatrice de ressources pour être effectuée dans un temps raisonnable.
L'algorithme de crypto à clé publique RSA est d'ailleurs basé sur ce principe.
"On pourrait même utiliser le rang des nombres premiers avec une table pour gagner encore un peu."
Cette idée est déjà mise en place dans les algos de ce type mais ne permet pas de gagner beaucoup d'efficacité. (Voir un bon bouquin de crypto pour plus de détails).
[^] # Re: Un nouvel algo de compression ?
Posté par jigso . Évalué à 1.
Certes, mais je pense qu'en découpant le binaire en morceaux relativement petit, ça devrait être faisable.
Qqu'un connait-il les ordres de grandeur de factorisation de nombres, mettons, de 10 chiffres, 50, 100 ?
[^] # Re: Un nouvel algo de compression ?
Posté par Olivier Dupuis . Évalué à 0.
Voir pour plus d'info sur la complexité de ce problème et des résultat en temps de calcul :
http://dept-info.labri.u-bordeaux.fr/~betrema/deug/poly/premiers.ht(...)
(très grossièrement, un problème est dit NP-complet si on ne sait pas montrer qu'il est au mieux exponentiel ou polynomial ; actuellement, on ne dispose que d'algorithme exponentiel pour les résoudre et comme ils sont dans une même classe d'équivalence, dès q'un tombe, tout le reste suit).
[^] # Re: Un nouvel algo de compression ?
Posté par Foxy (site web personnel) . Évalué à 1.
Un algo est dit "P-complet" si son temps de résolution varie comme un polynome de la taille des entrées.
Et va relire l'URL que tu donnes : la factorisation d'un nombre entier est "NP-complet".
Tu confonds tout : ce n'est pas parce que l'algorithme d'Euclide (celui que tu as décrit) fait sqrt(n) opérations qu'il n'est pas NP-complet.
Extrait de l'URL :
- "si par exemple n = pq est le produit de deux nombres premiers voisins, l'algorithme a une complexité exponentielle en fonction du nombre de chiffres nécessaires pour écrire n."
- "si n s'écrit avec k chiffres en base b, la complexité de cet algorithme est proportionnelle à bk/2, et est donc exponentielle en fonction de k. "
Un DEA d'informatique théorique, ça sert parfois avant de dire n'importe quoi ;-)
[^] # Re: Un nouvel algo de compression ?
Posté par Olivier Dupuis . Évalué à -1.
Ce que dit le texte en référence, c'est que la difficulté augmente exponentiellement (avec une puissance > 1) en fonction DU NOMBRE DE CHIFFRES NECESSAIRES pour décrire n :
Pour n = 100, 3 chiffres seulement sont nécessaires.
Si tu décris le problème en étudiant l'exposant dans une base donnée, tu passes d'un problème de taille n en exp(n).
Au fait, j'ai beau relire le texte, je n'arrive pas à trouver où ils prétendent que c'est NP-difficile. Ce qu'il faut comprendre, c'est qu'il est facile actuellement d'augmenter le nombre de chiffres pour décrire un nombre : on multiplie par 1000 le nombre (de 3 l'exposant en base 10), on augmente de facto le temps de calcul par 30... Ce qui finit vite pas devenir gros.
Pour finir, j'ai un DEA d'info et j'ai suivi des cours de complexité algorithmique et je bosse actuellement sur des problème NP-difficiles si pas plus. Ce qui ne m'empêche pas de dire des bétises :)
[^] # Re: Un nouvel algo de compression ?
Posté par Gaël Le Mignot . Évalué à 0.
P signifie Polynomial: il existe un algorithme qui resout le problême en un temps polynomial dans le pire cas.
NP ne signifie pas non polynomial mais Non-deterministic Polynomial. Cela signifie qu'il est possible en temps polynomial de tester si un candidat X est ou n'est pas solution du problème.
Un problème P est un problème NP tout comme un carré est un rectangle.
En géneral, on parle de problème NP-complet pour désigner les problèmes de complexité exponentielle , car il existe un théorème (le théorème de Cook) qui indique que certains problemes NP (dits NP-complet) sont équivalents, et qui si on peut en résoudre un de manière polynomiale, alors on peut résoudre les autres aussi.
Pour plus d'informations, voir le rapport que l'un des mes camarades a fait:
http://www.epita.fr:8000/~barada_n(...)
[^] # Re: Un nouvel algo de compression ?
Posté par Anonyme . Évalué à -1.
Effectivement, c'est même impossible, puisque le principe du nombre premier, c'est que tu ne peux pas le décomposer en facteurs entiers ;)
[^] # Re: Un nouvel algo de compression ?
Posté par Christophe GRAND (site web personnel) . Évalué à 10.
Ton binaire représente un nombre N. Il a donc besoin de log2(N) bits pour être représenté.
(log2(x)=ln(x)/ln(2))
ok ?
Mettons que ce nombre se décompose en XY.
or log2(N)=log2(XY)=log2(X)+log2(Y)
donc on a rien gagné : le nombre de bits nécessaire pour représenter les facteurs est le même que le nombre de bits nécessaires pour représenter le produit.
Et comme c'est un code à longueur variable, il faut des bits de stop et tout et tout.
Non, désolé, ça ne marchera jamais !
[^] # Re: Un nouvel algo de compression ?
Posté par jigso . Évalué à 5.
Ça pourrait marcher si certains facteurs sont présents plusieurs fois, mais ça fera pas lourd au final comme compression.
De façon plus génerale, est-ce que la "description" d'un nombre sous forme d'une formule "calculable" occupe le même ordre de grandeur de bit que le nombre ?
Je serais tenté de dire non, 123^4 prend moins de place que 228886641. Mais trouver la "bonne" formule est certainement une gageure dans le cas général...
Pour finir, connaissez-vous "le plus petit nombre non descriptible en moins de douze mots" ?
Gasp, mais cette description en compte 11 !
...
[^] # Re: Un nouvel algo de compression ?
Posté par Anonyme . Évalué à 0.
Théoriquement c'est la panacée, techniquement, on attendra après Moore encore longtemps ...
(*) orthographe ?
[^] # Re: Un nouvel algo de compression ?
Posté par Anonyme . Évalué à 2.
(grosso modo) Ils ont servis à démontrer que si on formalisait les mathématiques (et quelle que soit la formalisation), le système formel serait incomplet (= il existe des vérités indémontrables) et/ou inconsistant (= on peut démontrer une chose et son contraire)
Les nombres de Gödel sont en fait une représentation de chaque symbole du système formel.
Pour plus de renseignements, cherchez des infos sur le "Théorème de Gödel"
[^] # Re: Un nouvel algo de compression ?
Posté par Nicolas Vabo . Évalué à 0.
Bien sûr la compression peut demander du temps, mais certain nombres plus grands que d'autres peuvent être factorisés en moins longtemps, par exemple 2^500 se factorise plus rapidement que 3*5*132546798785412123453.
Pour gagner du temps, pourquoi ne pas découper le fichier en plusieurs plus petits ?
C'est vraiment faisable, faudrait essayer.
Un volontaire ?
[^] # Re: Un nouvel algo de compression ?
Posté par Jar Jar Binks (site web personnel) . Évalué à 2.
Exemple simple, tu veux compresser le nombre 100.
100=5²×2²
Il te faut donc coder un 5 et trois 2 (en plus des informations sur la façon de les agencer), soit dans le meilleur des cas 3 bits pour le 5 et 2 bits pour chaque 2, soit 9 bits. Or, 8 bits suffisent pour coder 100.
De façon générale, un algorithme de compression sans pertes (compactage ?) doit se baser sur les propriétés des données à compresser. Par exemple, un fichier texte contient plus de e que de ®. Mais de façon générale, un tel algorithme est une bijection. L'ensemble d'arrivée (l'ensemble des programmes compactés) et l'ensemble de départ (l'ensemble des programmes non compactés) doivent faire la même taille. En moyenne, un programme compacté, s'il est constitué d'octets aléatoires, fera donc la même taille qu'un programme qui ne l'est pas. Simplement, comme les programmes ont certaines propriétés, on arrive à faire pencher la balance d'un côté plutôt que de l'autre.
Juste mes deux centimes d'euros.
# ouatisdat ?
Posté par Anonyme . Évalué à 4.
Je sais ce que c'est qu'un executable
Mais je sais pas ce que ca veut dire un nombre premier executable (si je fait un shell script executable de 13 octets, c'est un nombre premier executable ? )
;-)
[^] # Re: ouatisdat ?
Posté par GP Le (site web personnel) . Évalué à 2.
On peut faire la meme chose en transforme un fichier bianire zip en nombre !
[^] # Re: ouatisdat ?
Posté par Frederic PY . Évalué à 3.
[^] # Re: ouatisdat ?
Posté par Anonyme . Évalué à 0.
Alors pourquoi parle-t-on de tels nombres ? En quoi le fait que ce nombre soit premier change qqch au niveau de la légalité de la copie ?
[^] # Re: ouatisdat ?
Posté par Larry Cow . Évalué à 1.
# To <> or not to <>
Posté par Anonyme . Évalué à -3.
Question intéressante!
A votre avois, ils sont <> ou ils sont pas <> ?
Et les modéros qui relisent, ils boivent de la <> ou de la >< ?
[^] # Les <>, ca R<>><E
Posté par Anonyme . Évalué à -2.
[^] # Re: To <> or not to <>
Posté par Vivi (site web personnel) . Évalué à 1.
Dans mon langage favori, <> ça veut dire "différent de" : apparemment, c'est pas ça ici ...
[^] # Re: To <> or not to <>
Posté par Cru Kilu . Évalué à -2.
[^] # Re: To <> or not to <>
Posté par Christophe GRAND (site web personnel) . Évalué à 0.
[^] # Re: To <> or not to <>
Posté par Anonyme . Évalué à 0.
la phrase aurait pu etre ecrite en toute lettres quand meme (de plus il manque un 'que', non ?), ca ne demande pas un effort si considerable ^_^
k`
# Et Pi ?
Posté par Neryel . Évalué à 0.
[^] # Re: Et Pi ?
Posté par Jar Jar Binks (site web personnel) . Évalué à 1.
Et d'ailleurs, il me semble que cette propriété de \pi n'a pas encore été démontrée.
[^] # Re: Et Pi ?
Posté par Wawet76 . Évalué à 2.
contre-exemple : Tu prends pi et tu retire toutes les occurrences de la chaine "123". Ca donne un nombre avec un nombre infini de décimales, sans boucle, et sans que 123 y soit inclus.
[^] # Re: Et Pi ?
Posté par Olivier Jeannet . Évalué à 1.
Ton contre-exemple ne marche pas pour ton histoire de "123" car si Pi contient la séquence "1 123 2 123 3" (j'ai mis des blancs pour la lisibilité), une fois que tu as retiré les "123" il en reste une.
Ceci dit, je crois que quand on étudie statistiquement Pi, on trouve une équiprobabilité de tous les motifs possibles, ce qui laisse à penser (pour moi) qu'on a une probabilité non nulle d'y trouver à peu près n'importe quelle suite de chiffres.
# Mouais....
Posté par Graveen . Évalué à 1.
La creativité peut s'exporter de nombreuses manières, mais ce n'est que la représentation d'une idée que l'on cible.
Parce qu'aprés tout, une contrefacon audio, ce n'est qu'une suite de bits, hein, il y a mathématiquement une probabilité pour que je reproduise accidentellement cette série, non ?
Alors le fait que ce soit un nombre (premier et/ou executable)(ou non d'ailleurs) qui represente un concept importe peu, le point important est qu'il y a ...hum... volonté de "diffusion". Et c'est ca que le RIAA cible. Donc je pense que son auteur peut malheureusement, en toute logique, être victime de poursuites.
[^] # Re: Mouais....
Posté par Anonyme . Évalué à 4.
Avant, on pensait qu'un grand nombre de personnes tapant n'importe quoi sur leur clavier finiraient par ecrire les oeuvres complete de shakespeare.
Depuis la tribune, on sait que c'est faux.
[^] # A mourir de rire!
Posté par Gauthier (Mastodon) . Évalué à 2.
Depuis la tribune, on sait que c'est faux.
Il ne faut pas avoir peur d'être rigolo. Le mauvais éléve qui raconte des blagues au fond de la classe, ne devrait pas avoir peur de le dire devant tous le monde.
J'ai plus de point pour scorer mais demain je mets +1. (zut demain c'est samedi je bosse pas)
# Question
Posté par Antoine Labour . Évalué à 1.
[^] # Re: Question
Posté par Wawet76 . Évalué à 2.
Est-ce que le serveurs de clés publiques vérifient l'unicité des clefs qu'on leur donne en pature ?
(oui, je sais que c'est hautement improbable. Vous n'avez jamais entendu parler des générateurs d'improbabilités ?)
[^] # Re: Question
Posté par kadreg . Évalué à -1.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.