Le Forum de l'Alliance Francophone

Nouvelles:

Auteur Sujet: NFS@Home  (Lu 94707 fois)

0 Membres et 1 Invité sur ce sujet

Hors ligne Aillas

  • Boinc'eur Junior
  • **
  • Messages: 74
  •   
le: 05 September 2009 à 09:02

Infos Utiles:

Résumé :

     NFS@Home est un projet de recherche pour faire du criblage lattice dans le domaine de la factorisation de grands entiers. A l'école, vous avez gagné votre première expérience en brisant des entiers en facteurs premiers, tels que 15 = 3 * 5 ou 35 = 5 * 7. NFS@Home est une continuation de cette expérience, seulement avec des nombres entiers qui ont des centaines de chiffres. La plupart des dernières grandes factorisations ont été faites principalement par des clusters dans les universités. Avec NFS@Home, vous pouvez vous aussi participer à l'art de la factorisation.

     La factorisation d'entier est intéressante d'une perspective mathématique mais également pratique. Mathématiquement, par exemple, le calcul de fonctions multiplicatives dans la théorie des nombres pour un nombre donné, requiert les facteurs du nombre. De plus, la factorisation de nombres particuliers peut aider dans la preuve qu'un nombre qui leurs est associé est premier. Dans la pratique, beaucoup d'algorithmes à clé publique, incluant l’algorithme RSA, se basent sur le fait que le module public ne peut pas être factorisé. Si c'était le cas, la clé privée pourrait facilement être calculée. Jusqu'à récemment, RSA-512, qui utilise un module de 512bits (155 chiffres), était couramment utilisé mais peut maintenant facilement être déchiffré.

     Les nombres que nous factorisons sont choisis dans le projet Cunningham. Débuté en 1925, c'est l'un des plus vieux projets encore en cours en théorie des nombres. La troisième édition du livre, publié par the American Mathematical Society en 2002, est disponible en téléchargement gratuit. Tous les résultats obtenus depuis, ceux de NFS@HOME également, sont disponibles sur le site du projet Cunningham .


Applications CPU :

  • 14e Lattice Sieve (jusqu'à 0.5GB de RAM par WU)
           Disponible pour Windows (32bits), Linux (32 et 64bits), Mac (32bits et 64bits) et FreeBSD 64 bits.

  • 15e Lattice Sieve (jusqu'à 0.5GB de RAM par WU)
           Disponible pour Windows (32bits), Linux (32 et 64bits), Mac (32bits et 64bits) et FreeBSD 64 bits.

  • 16e Lattice Sieve (jusqu'à 1GB de RAM par WU)
           Disponible pour Windows (32bits), Linux (32 et 64bits), Mac (32bits et 64bits) et  FreeBSD 64 bits.

*Pour Windows 64bits, des WUs 32bits seront envoyées.

  • 16e Lattice Sieve V5 (jusqu'à 1GB de RAM par WU)
           Disponible actuellement uniquement pour Linux (32 et 64bits) et FreeBSD  64bits.

Crédits par tâches:
lasieved - 36
lasievee - 44
lasievef - 65
lasieve5f - 65

Les calculs les plus importants reçoivent le plus de crédits. Particulièrement pour 16e (lasievef+lasieve5f), les crédits récompensent aussi l'utilisation d'une grande quantité de mémoire.

Les applications utilisées par chaque sous-projets?

lasieved - Oddperfect, n^n+(n+1)^(n+1), Fibonacci, Lucas, Cunningham, Cullen et Woodall pour des difficultés SNFS en dessous de 250.
lasievee - Cunningham, Oddperfect et d'autres pour des difficultés SNFS entre 250 et environ 280.
lasievef - utilisation d'applications de pointes pour des factorisations très difficiles, pour des difficultés SNFS supérieur à 280.
lasieve5f -  utilisation d'applications de pointes pour des factorisations très difficiles, pour des difficultés SNFS supérieur à 280.




Applications GPU :

     La question a été posée sur le forum, l'administrateur a répondu qu'il était potentiellement possible de porter l'application sur GPU, cependant cela n'était pas faisable actuellement sans une recherche plus poussée, donc pour le moment le projet reste uniquement disponible pour CPU.



Dernière Info :

Le 02/06/2012

Citer
64-bit Mac OS X app released
A 64-bit Mac OS X app has been released. It uses less memory and is much faster than the older 32-bit app for Mac. Note that this was built with Xcode 4.0, and requires Mac OS X 10.6 Snow Leopard or greater. It will not run with 10.5 Leopard.

Citer
Application 64-bit Mac OS X disponible
Une application 64-bit Mac OS X est maintenant disponible. Elle utilise moins de mémoire et est bien plus rapide que la vieille version 32-bit de l'application pour Mac. Veuillez noter que cette application a été créée avec Xcode 4.0, et nécessite Mac OS X 10.6 Snow Leopard ou plus récent. Elle ne fonctionnera pas avec 10.5 Leopard.



mise à jour 14 décembre 2012 par cedricdd.
« Modifié: 14 December 2012 à 18:45 par cedricdd »



Hors ligne Netrider

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 1810
  •   
    • Equipe De La Science
    • E-mail
Réponse #1 le: 05 September 2009 à 09:10
Jy suis , merci, j'ai pas de results pour l'instant  :miam:

Edit > fonctionne sous vista 64 B ici
« Modifié: 05 September 2009 à 09:15 par Netrider »



Hors ligne Aillas

  • Boinc'eur Junior
  • **
  • Messages: 74
  •   
Réponse #2 le: 05 September 2009 à 09:12
Je viens juste de récupérer ma première WU sous Linux. On verra ce que cela donne.



Hors ligne Dimi [edls]

  • Boinc'eur Confirmé
  • ***
  • Messages: 234
Réponse #3 le: 05 September 2009 à 09:16
J'espère que il seras pas trop repetitif, que il y aura une vraie simulation ou qu'ils refassent un porshe 2000
  :marcp:

Sinon c'est original comme projet :)

 

If you think you can won the world...
You can won the world... I won the word!


Hors ligne Netrider

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 1810
  •   
    • Equipe De La Science
    • E-mail
Réponse #4 le: 05 September 2009 à 09:40
UOTD  :D :sun:

35 minutes la wu pour 14 points sur un Q9650
« Modifié: 05 September 2009 à 09:45 par Netrider »



Hors ligne louchio

  • Boinc'eur Respectable
  • ****
  • Messages: 609
  •   
Réponse #5 le: 05 September 2009 à 13:52
mais dans les faits cela fait quoi comme recherche ce projet



Hors ligne Aillas

  • Boinc'eur Junior
  • **
  • Messages: 74
  •   
Réponse #6 le: 05 September 2009 à 14:46
Pas trop le temps là. Je vais essayer de retrouver des liens sur le net qui expliqueront mieux que moi.
En gros, ils cherchent à factoriser des nombres entier très grands.




Hors ligne Netrider

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 1810
  •   
    • Equipe De La Science
    • E-mail
Réponse #7 le: 05 September 2009 à 17:40
Je comprends pas pourquoi sur le site on ne nous vois pas, notre compte est bien présent mais dans les stats du site il ni a que deux personnes, louche  :??:

De plus j'ai trouvé leur forum mais en externe

http://www.mersenneforum.org/showthread.php?p=188690#post188690
« Modifié: 05 September 2009 à 17:49 par Netrider »



Hors ligne Netrider

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 1810
  •   
    • Equipe De La Science
    • E-mail
Réponse #8 le: 06 September 2009 à 19:02
Bon bein tout fonctionne à présent l'AF y est enregistrée, il ni a plus qu'a venir me tenir compagnie  :/

http://escatter11.fullerton.edu/nfs/index.php

Projet mathématique dans le sillage de PrimGrid

A déplacer donc  :jap:



Hors ligne xipehuz

  • Animateur fanatique
  • Boinc'eur devant l'éternel
  • *****
  • Messages: 1672
  •   
    • Les Xipéhuz
Réponse #9 le: 06 September 2009 à 22:03
Une seule UT partie en erreur sur 7 calculées, le projet à l'aire de fonctionner correctement.

Je prends les compliments comme des reproches d'hypocrites (Palinka)


Hors ligne Netrider

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 1810
  •   
    • Equipe De La Science
    • E-mail
Réponse #10 le: 06 September 2009 à 23:26
Nos amis germains sonts arrivés en force sur ce projet, je tiendrait pas longtemps la premiere place de l'AF  :gno:



Hors ligne Netrider

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 1810
  •   
    • Equipe De La Science
    • E-mail
Réponse #11 le: 08 September 2009 à 13:47
Les stats du projet sont disponibles pour les stastisticiens ennes

J'ai remarqué que quand je crunchait avant de m'accrocher  l'AF mes points d'avant nont pas été injectés dans l'équipe, heu je sait plus ce qu'il en est avec ca, bref ca serait bien de comparer avec les stats SETIBZH

Merci :smak:
/

http://escatter11.fullerton.edu/nfs/stats/
« Modifié: 08 September 2009 à 13:52 par Netrider »



Hors ligne la frite

  • Boinc'eur Confirmé
  • ***
  • Messages: 314
  •   
Réponse #12 le: 08 September 2009 à 15:06
Salut je viens de calculer qques unités et je suis deja UotD!! :)

Juste une 'tite question si par hasard tu sais: (sinon je posterai sur leur fofo)
en ce moment il essaye de factoriser 5^353+1 et un autre nombre, mais prquoi ces 2 nombres là précisement?? :D



Hors ligne Netrider

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 1810
  •   
    • Equipe De La Science
    • E-mail
Réponse #13 le: 08 September 2009 à 17:27
j'ai lu un truc en anglais je ne sait plus ou mais je ne l'ai pas traduit et j'ai eut du mal a comprendre la lecture technique dans la langue de schakespire ( Le frangin de britney ?  :lol: ) une premiere vague et en cours de finition et la il passent à la seconde.



Hors ligne bcoz

  • Boinc'eur Junior
  • **
  • Messages: 83
Réponse #14 le: 08 September 2009 à 18:50
en ce moment il essaye de factoriser 5^353+1 et un autre nombre, mais prquoi ces 2 nombres là précisement??

Pourquoi précisément ces deux là, je ne sais pas, mais tous les deux sont déjà factorisés et leurs facteurs connus et publiés (dans les tables de Cunningham, dispo sur le net). J'imagine qu'il souhaitait tester une puissance de 2 pas trop grande pour son premier essai, et une puissance de 5 un peu plus costaude pour le deuxième test.
Avec ce genre de nombres, il va déjà y avoir une matrice de plusieurs millions d'éléments à simplifier et résoudre.



Hors ligne la frite

  • Boinc'eur Confirmé
  • ***
  • Messages: 314
  •   
Réponse #15 le: 08 September 2009 à 20:35
:hello: bcoz :) merci de l'info je n'avais pas pensé que ces deux nombres pouvaient être deja factorisés. J'ai posé la même question sur leur forum, sûrement l'admin me répondra du coup un peu aussi sur l'avenir du projet après ces deux tests. Par contre je sais tjrs pas à quoi cela sert il de factoriser des big numbers. a+



Hors ligne bcoz

  • Boinc'eur Junior
  • **
  • Messages: 83
Réponse #16 le: 08 September 2009 à 22:01
:hello: bcoz :) merci de l'info je n'avais pas pensé que ces deux nombres pouvaient être deja factorisés. J'ai posé la même question sur leur forum, sûrement l'admin me répondra du coup un peu aussi sur l'avenir du projet après ces deux tests. Par contre je sais tjrs pas à quoi cela sert il de factoriser des big numbers. a+
Pas évident de répondre à ta question. Il y a un grand intérêt à trouver un algorithme de factorisation de grands entier pour un tas de raisons dont notamment la cryptographie. Etablir des tables de facteurs comme la liste de Cunningham dont je parlais plus haut est probablement moins intéressant en soi, mais un peu comme les listes de grands nombres premiers, ça peut toujours servir, et c'est un moyen de continuer à tester et améliorer les algos.

L'algorithme NFS utilisé par ce projet est le plus efficace connu à ce jour pour des nombres quelconques. Il est assez difficile de l’expliquer simplement. Le descriptif de wikipédia est pas mal, mais assez touffu : http://fr.wikipedia.org/wiki/Crible_g%C3%A9n%C3%A9ral_de_corps_de_nombres_(GNFS) . Le principe de congruence des carrés est plus facilement compréhensible et le principe est en gros le même : http://fr.wikipedia.org/wiki/Crible_quadratique .

L’ordre de grandeur des records de factorisation est très loin des records de nombres premiers. Pour des nombres quelconques je crois que le record est de l’ordre de 200 chiffres (challenge rsa de l’année dernière, il me semble) et de quelques centaines pour des nombres ayant des formes particulières facilitant la factorisation ou avec des indices sur leur construction. Alors que le record actuel de grand nombre premier est de 1 300 000 chiffres, et que l’on trouve presque quotidiennement (notamment avec PrimeGrid) des premiers de quelques centaines de millier de chiffres.

A+




Hors ligne la frite

  • Boinc'eur Confirmé
  • ***
  • Messages: 314
  •   
Réponse #17 le: 09 September 2009 à 15:49
Super ta réponse! merciii :) j'ai suivi les liens sur wikipédia, légérement compliqué :D mais interessant quand même ;)

Au fait l'admin du projet m'a rép:

Citer
My interest lies in the continued development of open source, publicly available tools for large integer factorization. Over the past couple of years, the capability of open source tools, in particular the lattice sieve of the GGNFS suite and the program msieve, have dramatically improved. My collaborators and I have factored quite a few large numbers using these tools.

Integer factorization is interesting both mathematical and practical perspectives. Mathematically, for instance, the calculation of multiplicative functions in number theory for a particular number require the factors of the number. Likewise, the integer factorization of particular numbers can aid in the proof that an associated number is prime. Practically, many public key algorithms, including the RSA algorithm, rely on the fact that the publicly available modulus cannot be factored. If it is factored, the private key can be easily calculated. Until quite recently, RSA-512, which uses a 512-bit modulus (155 digits), was used. As recently demonstrated by factoring the Texas Instruments calculator keys, these are no longer secure.

For most recent large factorizations, the work has been done primarily by large clusters at universities. There are two other public efforts, NFSNet and MersenneForum, in both of which I have participated, but the software used by NFSNet doesn't incorporate the latest developments and participation in the MersenneForum effort requires manual reservation and submission of work. I have been toying with the idea of trying a BOINC project for a while now to make it easy for the public to participate in state-of-the-art factorizations, and I found the time to do so. My interest in this project is to see how far we can push the envelope and perhaps become competitive with the larger university projects running on clusters, and perhaps even collaborating on a really large factorization.

The numbers are chosen from the Cunningham project. The project is named after Allan Joseph Champneys Cunningham, who published the first version of the factor tables together with Herbert J. Woodall in 1925. This project is one of the oldest continuously ongoing projects in computational number theory, and is currently maintained by Sam Wagstaff at Purdue University. The third edition of the book, published by the American Mathematical Society in 2002, is available as a free download. All results obtained since the publication of the third edition are available on the Cunningham project website.

Concerning target size, I started out somewhat "small" (small meaning that I can do it on our cluster in a few days), but it also took the contributors to this project only a few days as well. For our second project, I chose a target somewhat larger. I will continue to slowly increase the size. The real limit is the memory requirement. The current project requires a bit less than 512 MB of memory. As the size of the target increases, that will also increase somewhat. I will be keeping a close eye on that as we move forward.

J'ai pas trop le tmps de le traduire là, et puis je suis pas sûr que ce soit une grande priorité :D

Hop a+



Hors ligne bcoz

  • Boinc'eur Junior
  • **
  • Messages: 83
Réponse #18 le: 09 September 2009 à 17:33
Grilled, je mets quand même ma traduction, un peu plus lisible que la trad automatique  :ange:
Citer
Mon intérêt réside dans le développement d’outils open source et librement disponibles pour la factorisation de grands entiers. Ces dernières années les capacités des outils open source ont augmenté spectaculairement, particulièrement pour le criblage GNFS et le programme msieve. Mes collaborateurs et moi avons factorisé pas mal de grands nombres avec ces outils.

La factorisation d’entiers est intéressante à la fois mathématiquement et pour des raisons pratiques. Mathématiquement, par exemple, le calcul de fonctions multiplicatives en théorie des nombres pour un nombre particulier requière les facteurs de ce nombre. De la même façon la factorisation de certains nombres peut aider à prouver qu’un nombre associé est premier. Pratiquement, beaucoup d’algorithmes à clé publique, y compris RSA, reposent sur le fait que a clé publique ne peut être factorisée. Si elle est factorisée, la clé privée peut être facilement calculée. Jusqu’à récemment, RSA-512 qui utilise une clé de 512 bits (155 chiffres) était utilisé. Comme cela a été démontré par le calcul de la clé des calculettes Texas Instruments, on ne peut plus le considérer sûr.


La plupart des factorisations récentes de grands nombres ont été réalisées par de grands clusters d’universités. Il y a deux autres projets publics, NFSNet et MersenenForum, auxquels j’ai participé, mais NFSNet n’utilise pas les derniers développements et la participation  au projet MersenneForum demande des réservations et soumissions manuelles du travail. Cela fait maintenant un moment que l’idée de faire un projet BOINC me titille, pour rendre facilement accessible au public la participation à un projet de factorisation compétitif. Un des intérêts du projet est de voir jusqu’ou nous pourrons pousser l’enveloppe, et peut-être devenir compétitif avec les grands projets universitaires tournant sur clusters, et peut-être même collaborer sur des factorisations vraiment grandes.

Les nombres sont choisis depuis le Cunningham project. Ce projet est nommé d’après Allan Joseph Champneys Cunningham, qui a publié la première version de la table de facteurs avec Herbert J. Woodall en 1925.  Ce projet est l’un des plus anciens toujours actifs de la théorie des nombres, et est en ce moment maintenu par Sam Wagstaff de l’université de Purdue. La troisième édition de la liste, publiée par l’American Mathematical Society in 2002 est disponible en téléchargement. Tous les résultats obtenus depuis cette publication sont disponibles sur le site du projet.

Concernant la taille des cibles, j’ai commence par quelque chose de relativement “petit” (petit signifiant que je peux le calculer en quelques jours sur notre cluster), mais cela à pris également quelques jours aux contributeurs. Pour notre second test, j’ai choisi une cible notablement plus grande. Je vais continuer à augmenter doucement la taille. La vraie limite est le besoin en mémoire. Le calcul actuel nécessite un peu moins de 512 Mo de mémoire. Au fur et à mesure de l’augmentation de la taille des cibles, le besoin mémoire va continuer à augmenter. Je surveillerai attentivement cela au cours de notre progression.
« Modifié: 09 September 2009 à 17:35 par bcoz »



Hors ligne jm@rc

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 2880
  •   
    • Les RoadRunners sur Boinc
Réponse #19 le: 09 September 2009 à 17:54
c'est donc un projet intéressant au niveau des mathématiques mais pour lequel nous aurons besoin d'une quantité de RAM assez importante à terme?



Hors ligne al@ON

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 11703
  •   
    • MySpace al@ON
Réponse #20 le: 09 September 2009 à 18:35

Merci bcoz pour toutes tes explications sur ce projet et pour la trad. :jap:... bien essayé Netrider. ;)

Je m'inscrirais à NFS@Home après le RAID. :coffeetime:


Hors ligne la frite

  • Boinc'eur Confirmé
  • ***
  • Messages: 314
  •   
Réponse #21 le: 09 September 2009 à 20:33
Wouah quel bon boulot merci pour la trad! ;)



Hors ligne bcoz

  • Boinc'eur Junior
  • **
  • Messages: 83
Réponse #22 le: 09 September 2009 à 22:53
c'est donc un projet intéressant au niveau des mathématiques mais pour lequel nous aurons besoin d'une quantité de RAM assez importante à terme?
Exactement

A la demande unanime d’un MP, j’essaye une explication encore plus simple :
D’abord l’arithmétique modulaire : Il s’agit de choisir un nombre maximum après lequel tu retournes à zéro. Par exemple si ton maximum est quatre, tu comptera 0,1,2,3,O,1,2,3,.… c’est comme quand tu comptes les heures, arrivé à 23h59, tu retourne à zéro. Le nombre maximum est appelé la base. On dit que l’on compte modulo cette base. Dans mon exemple on compte modulo 4 et on peut écrire des choses comme 3+2=1 modulo 4 (comme trois heures après 22heures, il est 1 heure).

Si la base est bien choisie (il faut que ce soit un nombre premier), toutes les opérations habituelles de l’arithmétique restent valables, et leurs propriétés également (commutativité, associativité, etc…). En fait une arithmétique modulo n permet de constituer un sous ensemble de nombres qui est un modèle réduit de l’ensemble des entiers naturels et qui en partage presque toutes les propriétés. Sous certaines conditions des théorèmes démontrés dans le modèle réduit sont aussi valables dans le « vrai » ensemble des nombres. C’est la raison du succès énorme de cette approche.

Parmi les propriétés intéressantes, il y a la congruence des carrés : si deux carrés sont congruents (c'est-à-dire égaux modulo la base), alors ils ont probablement un facteur commun qui est un diviseur de la base. C’est le principe des cribles quadratiques. On cherche des carrés congruents dans des bases premières grandes, mais plus petites que le nombre à factoriser, puis on applique des méthodes qui permettent par approche successives d’arriver à un diviseur du nombre cible.

Voilà, j’espère que ça éclairera un peu les pas trop matheux.



Hors ligne al@ON

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 11703
  •   
    • MySpace al@ON
Réponse #23 le: 09 September 2009 à 23:12
Voilà, j’espère que ça éclairera un peu les pas trop matheux.

Totalement abstrait pour moi... pour ne pas dire abscons. :desole:  :D


Hors ligne JeromeC

  • CàA
  • Boinc'eur devant l'éternel
  • *****
  • Messages: 31061
  •   
Réponse #24 le: 09 September 2009 à 23:35
Fiouuuu j'ai bien fait d'arrêter les maths après le bac, je serais déjà devenu fou sinon...

Comment ça je suis déjà fou ???  :pt1cable:

A quoi bon prendre la vie au sérieux, puisque de toute façon nous n’en sortirons pas vivants ? (Alphonse Allais)